In this paper, we augment online algorithms for the knapsack problem using the total weight information. The conventional optimal online algorithm achieves the ln(U/L)+1 competitive ratio where L and U are the upper and lower bounds of the value-to-weight ratio. However, it does not consider that decision makers can know the total weight information or obtain it through machine-learned predictions. To fill this gap, we first propose the Known Weight Algorithm (KWA) which uses the exact total weight information to achieve a competitive ratio of W((U-L)/(eL))+1, where W denotes the Lambert-W function. We prove that it is optimal and tight. After that, we extend KWA to the Predicted Weight Algorithm (PWA), a learning-augmented online algorithm that uses predicted total weight. We show the consistency and robustness of PWA, and prove that its competitive ratio degrades gracefully as the prediction error grows. Finally, we introduce the Limited Volume Algorithm (LWA), which achieves a better competitive ratio than ln(U/L)+1 when the total weight is less than twice the capacity.

IoT (Internet of Things) cameras have widely been deployed over the last few years. These cameras are often with limited hardware so that they can only capture noisy videos in low resolution. In this work, we propose the joint video denoising and super-resolution network for IoT cameras, which consists of the noise-robust moving-attention (NRMA) module and the noise-eliminated upsampling (NEU) module. In NRMA, we adopt a coarse-to-fine approach by first extracting the coarse flow and then refining through bi-directional feature propagation among adjacent frames. In NEU, we further utilize inner-frame features for noise-elimination and upsampling. Through this approach, we avoid the negative effects brought by applying denoising and super-resolution in tandem, and enhance the reconstruction of moving objects by the embedded attention layers in NRMA. We conduct our experiments on both synthetic datasets, which utilize existing data with additive white Gaussian noise (AWGN), and a realistic dataset captured using a pair of IoT and professional cameras. Our extensive experimental results demonstrate that our proposed method significantly reduces noise and enhances detail in both types of datasets. Notably, our approach outperforms the state-of-the-art benchmark (RealBasicVSR) by an average of 5.24 dB on the existing datasets (with noise level σ = 20) and by 0.95 dB on the realistic dataset in terms of PSNR.

As the demand for faster and more reliable content delivery escalates, Content Delivery Networks (CDNs) face significant challenges in managing content placement across their increasingly complex, multi-tiered structures to balance performance, complexity, and scalability, while addressing the transient nature of data and the unpredictability of internet traffic. Addressing these challenges, this study introduces a novel multi-tier CDN caching strategy that navigates spatial and temporal trade-offs in cache placement, considering the cache placement cost diminishes with the content lifetime, and the uncertainty of future data demands. We design a distributed online algorithm that evaluates each incoming request and places new caches when the total content delivery cost exceeds a threshold. Our competitive analysis shows a tight and optimal$\mathtt {Tiers}+1$competitive ratio. Additionally, our algorithm has low complexity by passing$O(\mathtt {Tiers})$number of reference messages for each request, which enhances its practical applicability. Empirical validation through numerical simulations and trace-driven experiments confirms the superiority of our approach to existing benchmarks in real-world CDN settings.

In this paper, we propose and analyze HierAdMo, a three-tier adaptive momentum accelerated client-edge-cloud Federated Learning (FL) algorithm. HierAdMo combines the momentum acceleration on both worker and edge levels. However, simply combining these two levels of momenta may lead to disagreement between them, negatively influencing convergence performance. To this end, we embed an online adaptive method that scales down the momentum when disagreement occurs. We provide mathematical proof for the convergence of HierAdMo for non-i.i.d. data and the tighter convergence upper bound compared with a version of HierAdMo without adaptation (HierAdMo-R). Finally, extensive experiments based on real-world datasets are conducted, verifying that HierAdMo outperforms existing mainstream benchmarks and achieves the optimal or near-optimal convergence performance compared with HierAdMo-R under a wide range of settings.

Real-time video surveillance cameras have been widely deployed over the last few years. In case of incidents such as natural disasters, it provides vital guidance in real time to aid the rescue operations. However, the quality of the captured video is far from satisfactory due to the limited camera hardware and low network bandwidth. Noise is often observed especially at night and the resolution is low. To this end, we are motivated to retrieve the nighttime surveillance video through calibrated denoising and super-resolution. We only use the preceding and current frames, but not the future frames. Thus, we avoid the additional delay of waiting for future frames, which is not suitable for real-time video applications. We design the pipeline semantically beneficial for both denoising and super-resolution, and achieve high rendering quality, especially for real-world noise. Moreover, we propose a novel calibration method for collecting paired noisy and clean observations in the real world, which provides more effective training data. We conduct experiments using the real-world dataset collected under low-light conditions, and benchmark with state-of-the-art video denoising and super-resolution methods. Results show that our method achieves significant performance gain while introducing small delay compared with the benchmarks, suitable for real-time videos.

Abstract We present a novel online decision-making solution, where the optimal path of a given decision tree is dynamically found based on the contextual bandits analysis. At each round, the learner finds a path in the decision tree by making a sequence of decisions following the tree structure and receives an outcome when a terminal node is reached. At each decision node, the environment information is observed to hint on which child node to visit, resulting in a better outcome. The objective is to learn the context-specific optimal decision for each decision node to maximize the accumulated outcome. In this paper, we propose Dynamic Path Identifier (DPI), a learning algorithm where the contextual bandit is applied to every decision node, and the observed outcome is used as the reward of the previous decisions of the same round. The technical difficulty of DPI is the high exploration challenge caused by the width (i.e., the number of paths) of the tree as well as the large context space. We mathematically prove that DPI’s regret per round approached zero as the number of the rounds approaches infinity. We also prove that the regret is not a function of the number of paths in the tree. Numerical evaluations are provided to complement the theoretical analysis.

We study the multi-machine task scheduling problem in an integrated serverless edge and cloud computing system, where tasks can be scheduled locally on edge processors or offloaded to cloud servers, with the objective of minimizing the makespan, i.e., the total time to finish all tasks. The system is semi-online, where the edge processing delays of the tasks are known as priori, but the cloud processing delays remain unknown due to the uncertainty introduced by uploading and loading delay (loading the software environment). The problem is NP-hard in nature, and therefore we resort to approximation schemes and propose a novel algorithm named multi-machine with restart scheduling (MRS). MRS utilizes task restart, where a task that is cancelled will be restarted later when its processing time exceeds the threshold, and the threshold can be adaptively adjusted. We derive an competitive ratio for MRS so that its worst-case gap from the optimal solution is bounded. We also implement the MRS scheduler in a real-world system, which schedules a diverse set of Deep Neural Network (DNN) inference tasks. It shows that MRS achieves significant reduction in makespan compared to existing benchmark schemes.

Video surveillance cameras have been extensively deployed over the last few years. In case of incidents such as natural disaster rescue, it provides vital guidance in real-time. However, due to the limited camera hardware and network bandwidth, noise are observed especially at night and the resolution is low. To tackle these two issues, we design and implement EADV, an Edge-Assisted Deep Video denoising and super-resolution system for real-time surveillance at night. We demonstrate the video quality enhancement using a camera, a displayer, and an edge server. The low-quality video captured by the camera is enhanced by the server and shown on the displayer. The enhanced real-time video is smooth and the performance uplift is observable.

There is growing interest in applying distributed machine learning to edge computing, formingfederated edge learning. Federated edge learning faces non-i.i.d. and heterogeneous data, and the communication between edge workers, possibly through distant locations and with unstable wireless networks, is more costly than their local computational overhead. In this work, we propose${{\sf DONE}}$, a distributed approximate Newton-type algorithm with fast convergence rate for communication-efficient federated edge learning. First, with strongly convex and smooth loss functions,${{\sf DONE}}$approximates the Newton direction in a distributed manner using the classical Richardson iteration on each edge worker. Second, we prove that${{\sf DONE}}$has linear-quadratic convergence and analyze its communication complexities. Finally, the experimental results with non-i.i.d. and heterogeneous data show that${{\sf DONE}}$attains a comparable performance to Newton's method. Notably,${{\sf DONE}}$requires fewer communication iterations compared to distributed gradient descent and outperforms DANE, FEDL, and GIANT, state-of-the-art approaches, in the case of non-quadratic loss functions.

We present a novel learning framework that utilizes the early exit of Deep Neural Network (DNN), a device-only solution that reduces the latency of inference by sacrificing a reasonable degree of accuracy. Choosing the optimal exit point is challenging as the delay and the accuracy of each exit point are random and cannot be known in advance. The problem is further complicated as the overall duration of the processing is also unknown. To this end, we propose Learning Early Exit (LEE), an online learning scheme based on multi-armed bandits analysis. LEE efficiently learns the optimal exit point for mobile-based DNN inference while simultaneously balancing the exploration-exploitation trade-off. LEE differs from the standard bandit analyses in two ways: the reward of choosing each exit point addresses the confidence-latency trade-off, and the time duration between each action is random (i.e., the latency of each action is random). LEE addresses the aforementioned challenges and it achieves asymptotically optimal performance. We implement a real-world system with a real-time testbed that can be deployed in a driving system. DNN models with multiple exit points are trained and deployed in the testbed so that the performance of LEE and benchmark schemes can be tested and compared. The result denotes that LEE substantially outperforms the benchmark schemes.

Complete Event Trend (CET) detection over large-scale event streams is important and challenging in various applications such as financial services, real-time business analysis, and supply chain management. A potential large number of partial intermediate results during complex event matching can raise prohibitively high memory cost for the processing system. The state-of-the-art scheme leverages compact graph encoding, which represents the common sub-sequences of different complex events using a common sub-graph to achieve space efficiency for storing the intermediate results. However, we show that such a design raises unacceptable computation cost for the graph traversal needed whenever a new event comes. To address this problem, in this paper, we propose a novel attribute-based indexing (ABI) graph model to represent the relationship between events. By classifying the predicates and constructing the graph based on both the comparators in the predicates and the attribute values of the events, we achieve parallel event stream processing and efficient graph construction. Our design significantly reduces the total computation cost of graph construction from O(n2) to O(nlog(m)), where n is the number of events and m is the number of the attribute vertices. We further design several efficient traversal-based algorithms to extract CETs from the graph. We implement our design and conduct comprehensive experiments to evaluate the performance of this design. The results show that our design wins a couple of orders of magnitude back from state-of-the-art schemes.

Graphics Processing Units (GPUs) have evolved as powerful co-processors for the CNN training. Many new features have been introduced into GPUs such as concurrent kernel execution and hyper-Q technology. It is challenging to orchestrate concurrency for CNN (convolutional neural networks) training on GPUs since it may introduce synchronization overhead and poor resource utilization. Unlike previous research which mainly focuses on single layer or coarse-grained optimization, we introduce a critical-path based, asynchronous parallelization mechanism, and propose the optimization technique for the CNN training that takes into account global network architecture and GPU resource usage together. The proposed methods can effectively overlap the synchronization and the computation in different streams. As a result, the training process of CNN is accelerated. We have integrated our methods into Caffe. The experimental results show that the Caffe integrated with our methods can achieve 1.30X performance speedup on average compared with Caffe+cuDNN, and even higher performance speedup can be achieved for deeper, wider, and more complicated networks.

Recent advances in deep neural networks (DNNs) have substantially improved the accuracy of intelligent applications. One effective scheme known as DNN partition further improves the speed of the inference by partitioning the DNN to a mobile device and its connected edge server to jointly process the inference. However, one of the challenges is how to maintain the service during handovers to avoid interruptions. Inspired by the recently developed early exit technique, where the DNN inference can be accelerated by leaving at an earlier exit point, we propose eDeepSave, a promising solution to save a large portion of video frames that cannot be handled during handovers. eDeepSave comprises three subschemes: (1) save the partially completed frames that are affected when the handover begins. (2) determine which frames we should save during a handover to maximize the number of saved frames. (3) repartition the last arriving frame before the end of the handover with a provable performance bound so that the frames after the handover can be processed without experiencing congestion. We build up a real-world prototype for the field experiments and extensive simulations, showing that eDeepSave can save up to 100% of the affected frames during handover.

Up-to-date results in data stream analytics are difficult to obtain because the data are in rapid sequence and can be accessed only once. Due to the exactly-once delivery nature of streaming data, online processing is quite unstable. To guarantee comprehensive and accurate results, aggregating historical data is essential when processing streaming data. In this paper, we propose a hash-based hybrid cache model, namely,HCache, for fast data analytics covering real-time streaming data and historical data. TheHCachemodel integrates the online cache and batch cache for hybrid online and batch processing and uses a hash structure to accelerate storage. When executing analytic tasks, the batch cache and online cache are accessed in parallel. Computed streaming data are stored in the online cache, which returns qualified results based on one-time visiting. The most recently visited historical data are stored in the batch cache, and they are also used to correct errors in the online cache. Efficient replacement strategies are used to keep the caches within a relatively stable size. To coordinate the online cache with the batch cache, an LRU-based selection strategy is designed to achieve comprehensive results. Experimental results show that theHCachemodel can quickly and efficiently execute analytic tasks with little additional overhead; moreoverHCacheis more stable and effective at data storage, access and query with less memory utilization than other models.

Federated Learning (FL) is a fast-developing distributed machine learning technique involving the participation of a massive number of user devices. While FL has benefits of data privacy and the abundance of user-generated data, its challenges of heterogeneity across users’ data and devices complicate algorithm design and convergence analysis. To tackle these challenges, we propose an algorithm that exploits proximal stochastic variance reduced gradient methods for non-convex FL. The proposed algorithm consists of two nested loops, which allow user devices to update their local models approximately up to an accuracy threshold (inner loop) before sending these local models to the server for global model update (outer loop). We characterize the convergence conditions for both local and global model updates and extract various insights from these conditions via the algorithm’s parameter control. We also propose how to optimize these parameters such that the training time of FL is minimized. Experimental results not only validate the theoretical convergence but also show that the proposed algorithm outperforms existing Stochastic Gradient Descent-based methods in terms of convergence speed in FL setting.

Although GPUs have emerged as the mainstream for the acceleration of convolutional neural network (CNN) training processes, they usually have limited physical memory, meaning that it is hard to train large-scale CNN models. Many methods for memory optimization have been proposed to decrease the memory consumption of CNNs and to mitigate the increasing scale of these networks; however, this optimization comes at the cost of an obvious drop in time performance. We propose a new memory optimization strategy named Layup that realizes both better memory efficiency and better time performance. First, a fast layer-type-specific method for memory optimization is presented, based on the new finding that a single memory optimization often shows dramatic differences in time performance for different types of layers. Second, a new memory reuse method is presented in which greater attention is paid to multi-type intermediate data such as convolutional workspaces and cuDNN handle data. Experiments show that Layup can significantly increase the scale of extra-deep network models on a single GPU with lower performance loss. It even can train ResNet with 2,504 layers using 12GB memory, outperforming the state-of-the-art work of SuperNeurons with 1,920 layers (batch size = 16).

Network function virtualization (NFV) is a promising solution to realize a variety of network services. By definition, virtual network functions (VNFs) are chained together to realize different services. However, chaining is not an ideal solution as service latency grows linearly with respect to the length of the chain. Motivated by the fact that many VNFs can be parallelized, we investigate parallelism of VNFs for acceleration. The dependency of the VNFs is characterized by a directed acyclic graph (DAG). We aim to deploy the VNFs in the right place and process them in parallel without violating the DAG, to minimize the overall delay. However, directly solving the delay minimization problem is NP-hard, and it may also introduce a large number of duplicated packets to burden the system. To deal with these issues, we propose the Prune and Plant (P&P) scheme with polynomial computational complexity, to reduce the overall delay while limiting the number of duplicated packets. P&P comprises two stages: in the Prune stage, we prune the original DAG into a series-parallel graph (SP-graph), which eliminates NP-hardness while maintaining parallelism of VNFs. In the Plant stage, we find the optimal placement for the VNFs with respect to the SP-graph. By both simulation and prototyping, we demonstrate that P&P significantly outperforms benchmark schemes.

In the bigdata era, many applications are required to perform quick and accurate join operations on large-scale realtime data streams, such as stock trading and online advertisement analysis. To achieve high throughput and low latency, distributed stream join systems explore efficient stream partitioning strategies to execute the complex stream join procedure in parallel. Existing systems mainly deploy two kinds of partitioning strategies, i.e., random partitioning and hash partitioning. Random partitioning strategy partitions one data stream uniformly while broadcasting all the tuples of the other data stream. This simple strategy may incur lots of unnecessary computations for low-selectivity stream join. Hash partitioning strategy maps all the tuples of the two data streams according to their attributes for joining. However, hash partitioning strategy suffers from a serious load imbalance problem caused by the skew distribution of the attributes, which is common in real-world data. The skewed load may seriously affect the system performance. In this paper, we carefully model the load skewness problem in distributed join systems. We explore the key tuples which lead to the heavy load skewness, and propose an efficient key selection algorithm, GreedyFit to find out these key tuples. We design a lightweight tuple migration strategy to solve the load imbalance problem in real-time and implement a new distributed stream join system, FastJoin. Experimental results using real-world data show that FastJoin can significantly improve the system performance in terms of throughput and latency compared to the state-of-the-art stream join systems.

All pairwise computation is defined as performing computation between every pair of the elements in a given dataset. It is often a necessary first step in a number of bioinformatics applications. Many of such applications require multiple terabytes of main memory and take multiple peta floating point operations to complete the computation. Therefore, large HPC clusters are needed to tackle these large-scale computational problems. Conventionally designed parallel algorithms using data partitioning may have a scalability issue, i.e., for a given problem of fixed size the efficiency may decrease if the number of compute nodes is increased (Amdahl's law). In this paper we introduce a new method for parallel algorithm design. Using this method we first design an efficient one-dimensional (1D) ring algorithm and then a two-dimensional (2D) algorithm based on the 1D ring for all pairwise computation. When increasing the compute nodes, instead of reducing the block size, we make multiple copies of the original data blocks in the 1D ring and distribute them across the added compute nodes in the other dimension. By properly organizing the compute nodes the communication overhead can be reduced to a minimum in this two-dimensional setting. Experiments on a Cray XC40 HPC supercomputer show that our new algorithms are very efficient and scalable for large-scale all pairwise computation on large HPC clusters.

Fog computing is a promising solution to provide low-latency and ubiquitously available computation offloading services to widely distributed Internet of Things (IoT) devices with limited computing capabilities. One obstacle, however, is how to seamlessly hand over mobile IoT devices among different fog nodes to avoid service interruption. In this paper, we propose seamless fog (sFog), a new framework supporting efficient congestion control and seamless handover schemes. Intrinsically, sFog improves system performance during handovers (achieved by the handover scheme), and guarantees the performance does not degrade when handovers do not occur (achieved by the congestion control scheme). Through the congestion control scheme, jobs are efficiently offloaded without causing unnecessary system idling; through the handover scheme, jobs are pre-migrated to the target fog node when a handover is about to occur, in order to reduce migration delay. In order to evaluate the performance of sFog, we propose a theoretical framework and establish a real-world prototype. Both the theoretical and experimental results show that sFog achieves substantial delay reductions compared with traditional benchmark handover schemes.

Graph algorithm is pervasive in many applications ranging from targeted advertising to natural language processing. Recently, Asynchronous Graph Processing (AGP) is becoming a promising model to support graph algorithm on large-scale distributed computing platforms because it enables faster convergence speed and lower synchronization cost than the synchronous model for no barrier between iterations. However, existing AGP methods still suffer from poor performance for inefficient vertex state propagation. In this paper, we propose an effective and low-cost forward and backward sweeping execution method to accelerate state propagation for AGP, based on a key observation that states in AGP can be propagated between vertices much faster when the vertices are processed sequentially along the graph path within each round. Through dividing graph into paths and asynchronously processing vertices on each path in an alternative forward and backward way according to their order on this path, vertex states in our approach can be quickly propagated to other vertices and converge in a faster way with only little additional overhead. In order to efficiently support it over distributed platforms, we also propose a scheme to reduce the communication overhead along with a static priority ordering scheme to further improve the convergence speed. Experimental results on a cluster with 1,024 cores show that our approach achieves excellent scalability for large-scale graph algorithms and the overall execution time is reduced by at least 39.8 percent, in comparison with the most cutting-edge methods.

The emerging Internet of Things (IoT) paradigm creates a growing need to analyze a significant amount of data produced by the interconnected IoT devices. Since IoT devices have limited computation capabilities, Fog Computing is a natural complement, to provide distributed, location-aware, and easy-to-access computation resources. In this work, we address the problem of application processing and data offloading in a Fog-integrated IoT ecosystem. By leveraging the Lyapunov optimization technique, we design an online and distributed system control policy called the Distributed Weighted Backpressure (DWB) policy that asymptotically minimizes the cost of IoT devices. A three-way tradeoff among queue backlogs, communication cost, and computation cost is then investigated. Finally, simulation study has been conducted to validate the correctness and usefulness of the proposed DWB policy.

For large-scale graph analysis on a single PC, asynchronous processing methods are known to converge more quickly than the synchronous approach, because of more efficient propagation of vertices state. However, current asynchronous methods are still very suboptimal in propagating state across different graph partitions. This presents a bottleneck for cross-partition state update and slows down the convergence of the processing task. To tackle this problem, we propose a new method, named the HotGraph, to faster graph processing by extracting a backbone structure, called hot graph, that spans all the partitions of the original graph. With this approach, most cross-partition state propagations in traditional solutions now take place within only a few hot graph partitions, thus removing the cross-partition bottleneck. We also develop a partition scheduling algorithm to maximize the hot graph's effectiveness by keeping it in memory and assigning it the highest priority for processing as much as possible. A forward and backward sweeping execution strategy is then proposed to further accelerate the convergence. Experimental results show that HotGraph can reduce the number of vertex state updates processed by 51.5 percent, compared with state-of-the-art schemes. Applying our optimizations further reduces this number by 72.6 percent and the execution time by 80.8 percent.

Exploiting temporal and spatial locality is a way to improve the performance of data compression and deduplication in a storage system. Through our evaluation, we find that content level similarity measures such as similar tags of photos have a certain correlation to data compressibility. Raw images with similar tags can be compressed together to get better storage space savings. Furthermore, storing similar raw images together enables rapid data sorting, searching, and retrieval if the images are stored in a distributed and large-scale environment with reduced fragmentation. In this paper, we present the correlation results between content similarity and data compressibility using a dataset built from Flickr. The system design we proposed has been based on the evaluation and it optimizes storage efficiency for Top-N relevant images with the same tag. On one hand, the storage space is saved. On the other hand, the design may accelerate the query performance for Top-N relevance search.

Dynamic software updating (DSU) enables a program to be patched on the fly without being shutdown. This paper addresses the practicality problem of the recent research on DSU systems, and presents Replus, a new DSU system that balances practicality and functionality. Replus aims to retain backward binary compatibility and support multi-threaded programs. In addition, it does not require customers to have developer-level software knowledge. More importantly, without specific compiler support, Replus can patch programs that are difficult to be updated at runtime, as well as programs that may incur an indefinite delay in DSU. The key technique of our solution is to update the stack elements for the patched program using two new mechanisms:Immediate Stack Updating, which immediately updates the stack of a thread, andtimely stack updating, which only updates the stack frames of the necessary functions without affecting others. Replus also develops anInstruction Level Updatingmechanism, which is more efficient for certain security patches. We used popular server applications as test suites to evaluate the effectiveness of Replus. The experimental results demonstrated that Replus can successfully update all the test suites with negligible impact on application performance.

Data deduplication is used to overcome two issues on Solid State Drives (SSDs). One is price per GB of storage space, and the other is the write limit or disk endurance. By eliminating duplicate data, the deduplication system improves storage efficiency and protects SSD from unnecessary writes. CAFTL [1] is a known solution for deduplication on SSD. We propose a system architecture for inline deduplication based on existing protocol of The Hadoop Distributed File System (HDFS), aiming at addressing performance challenges for primary storage. However, simply applying CAFTL to SSDs in a cluster does not work well. Two routing algorithms are presented and evaluated using selective real-life data sets. Compared to prior work, one routing algorithm (MMHR) may improve the deduplication ratio by 8% at minimal costs while the other (FFFR) can achieve about 30% higher deduplication ratio with tradeoff on chunk level fragmentation. A new research problem of chunk assignment into more than one node for deduplication is also formulated for more studies in this area.

Summary With the development of cloud computing, the demand of high availability for services is growing. Unfortunately, software failures greatly reduce system availability. This paper presents a lightweight software fault‐tolerance system, called SHelp, which can effectively recover programs from many types of software bugs in the cloud environment. With error virtualization techniques, it proposes ‘weighted’ rescue points techniques to effectively survive software failures through bypassing the faulty path. For multiple application instances running on different virtual machine, a three‐level storage hierarchy with several comprehensive cache updating algorithms for rescue points management is adopted to share error handling information. On the one hand, SHelp can reduce the redundancy for multiple application instances; on the other hand, it can more effectively and quickly recover from faults caused by the same bugs. A Linux prototype is implemented on an open‐source virtual machine monitor platform, Xen, and evaluated using four Web server applications that contain various types of bugs. The experimental results show that SHelp can recover server applications from these bugs in just a few seconds with modest performance overhead. Copyright © 2013 John Wiley & Sons, Ltd.

Due to high flexibility and cost-effectiveness, cloud computing is increasingly being explored as an alternative to local clusters by academic and commercial users. Recent research already confirmed the feasibility of running tightly-coupled parallel applications with virtual clusters. However, such types of applications suffer from significant performance degradation, especially as the over-commitment is common in cloud. That is, the number of executable Virtual CPUs (VCPUs) is often larger than that of available Physical CPUs (PCPUs) in the system. The performance degradation is mainly due to the fact that the current virtual machine monitors (VMMs) are unaware of the synchronization requirements of the VMs which are running parallel applications. In this paper, There are two key contributions. (1) We propose an autonomous synchronization-aware VM scheduling (SVS) algorithm, which can effectively mitigate the performance degradation of tightly-coupled parallel applications running atop them in over-committed situation. (2) We integrate the SVS algorithm into Xen VMM scheduler, and rigorously implement a prototype. We evaluate our design on a real cluster environment with NPB benchmark and real-world trace. Experiments show that our solution attains better performance for tightly-coupled parallel applications than the state-of-the-art approaches like Xen's Credit scheduler, balance scheduling, and hybrid scheduling.

Improving energy efficiency of data centers has become increasingly important nowadays due to the significant amounts of power needed to operate these centers. An important method for achieving energy efficiency is server consolidation supported by virtualization. However, server consolidation may incur significant degradation to workload performance due to virtual machine (VM) co-location and migration. How to reduce such performance degradation becomes a critical issue to address. In this paper, we propose a profiling-based server consolidation framework which minimizes the number of physical machines (PMs) used in data centers while maintaining satisfactory performance of various workloads. Inside this framework, we first profile the performance losses of various workloads under two situations: running in co-location and experiencing migrations. We then design two modules: (1) consolidation planning module which, given a set of workloads, minimizes the number of PMs by an integer programming model, and (2) migration planning module which, given a source VM placement scenario and a target VM placement scenario, minimizes the number of VM migrations by a polynomial time algorithm. Also, based on the workload performance profiles, both modules can guarantee the performance losses of various workloads below configurable thresholds. Our experiments for workload profiling are conducted with real data center workloads and our experiments on our two modules validate the integer programming model and the polynomial time algorithm.

The scale of cloud services keeps increasing over time, significantly introducing huge challenges in system manageability and reliability. Designing coordination services in cloud is the right track to solve the above problems. However, existing coordination services (e.g., Chubby and ZooKeeper) only perform well in read-intensive scenario and small ensemble scales. To this end, we propose Giraffe, a scalable distributed coordination service. There are three important contributions in our design. (1) Giraffe organizes coordination servers using interior-node-disjoint trees for better scalability. (2) Giraffe employs a novel Paxos protocol for strong consistency and fault-tolerance. (3) Giraffe supports hierarchical data organization and in-memory storage for high throughput and low latency. We evaluate Giraffe on a high performance computing test-bed. The experimental results show that Giraffe gains much better write performance than ZooKeeper when server ensemble is large. Giraffe is nearly 300% faster than ZooKeeper on update operations when ensemble size is 50 servers. Experiments also show that Giraffe reacts and recovers more quickly than ZooKeeper against node failures.

Due to high flexibility and cost-effectiveness, cloud computing is increasingly being explored as an alternative to local clusters by academic and commercial users. Recent research already confirmed the feasibility of running tightly-coupled parallel applications with virtual clusters. However, such types of applications suffer from significant performance degradation, especially as the overcommitment is common in cloud. That is, the number of executable Virtual CPUs (VCPUs) is often larger than that of available Physical CPUs (PCPUs) in the system. The performance degradation mainly results from that the current Virtual Machine Monitors (VMMs) cannot co-schedule (or coordinate at the same time) the VCPUs that host parallel application threads/processes with synchronization requirements.

Data sampling is a widely used technique in a broad range of machine learning problems. Traditional sampling approaches generally rely on random resampling from a given dataset. However, these approaches do not take into consideration additional information, such as sample quality and usefulness. We recently proposed a data sampling technique, called sample subset optimization (SSO). The SSO technique relies on a cross-validation procedure for identifying and selecting the most useful samples as subsets. In this paper, we describe the application of SSO techniques to imbalanced and ensemble learning problems, respectively. For imbalanced learning, the SSO technique is employed as an under-sampling technique for identifying a subset of highly discriminative samples in the majority class. In ensemble learning, the SSO technique is utilized as a generic ensemble technique where multiple optimized subsets of samples from each class are selected for building an ensemble classifier. We demonstrate the utilities and advantages of the proposed techniques on a variety of bioinformatics applications where class imbalance, small sample size, and noisy data are prevalent.

Space sharing approaches are widely used in job scheduling for HPC systems. The main drawback of these approaches is the blocking of short jobs, which results in low throughput. The research on gang scheduling has shown the potential of time sharing in improving throughput. However, traditional gang scheduling adds jobs for time sharing without selection, which may cause a higher performance degradation of existing running jobs than the performance gain of waiting jobs. Moreover, gang scheduling often adopts a contiguous buddy allocation scheme which has problems of fragmentation and low resource utilization. We design a selective time sharing technique that allows waiting jobs to be co-scheduled with existing running jobs only if the overall throughput can be improved. To alleviate the fragmentation problem, we present a dynamic grouping resource allocation mechanism that relaxes the contiguous allocation requirement imposed on gang scheduling. By integrating these techniques, our new job co-scheduling algorithm is able to simultaneously take system throughput and resource utilization into consideration. The experimental results demonstrate that our approach significantly outperforms both EASY backfilling and traditional gang scheduling in terms of both average turnaround time and bounded slowdown.

Buffer overflow attacks still pose a significant threat to the security and availability of today's computer systems. Although there are a number of solutions proposed to provide adequate protection against buffer overflow attacks, most of existing solutions terminate the vulnerable program when the buffer overflow occurs, effectively rendering the program unavailable. The impact on availability is a serious problem on service-oriented platforms. This paper presents SafeStack, a system that can automatically diagnose and patch stack-based buffer overflow vulnerabilities. The key technique of our solution is to virtualize memory accesses and move the vulnerable buffer into protected memory regions, which provides a fundamental and effective protection against recurrence of the same attack without stopping normal system execution. We developed a prototype on a Linux system, and conducted extensive experiments to evaluate the effectiveness and performance of the system using a range of applications. Our experimental results showed that SafeStack can quickly generate runtime patches to successfully handle the attack's recurrence. Furthermore, SafeStack only incurs acceptable overhead for the patched applications.

In a traditional virtualized cloud environment, using asynchronous I/O in the guest file system and synchronous I/O in the host file system to handle an asynchronous user disk write exhibits several drawbacks, such as performance disturbance among different guests and consistency maintenance across guest failures. To improve these issues, this paper introduces a novel disk I/O model for virtualized cloud system called HypeGear, where the guest file system uses synchronous operations to deal with the guest write request and the host file system performs asynchronous operations to write the data to the hard disk. A prototype system is implemented on the Xen hypervisor and our experimental results verify that this new model has many advantages over the conventional asynchronous-synchronous model. We also evaluate the overhead of asynchronous I/O at host, which is brought by our new model. The result demonstrates that it enforces little cost on host layer.

The cloud computing paradigm is attracting an increased number of complex applications to run in remote data centers. Many complex applications require parallel processing capabilities. Parallel applications of certain nature often show a decreasing utilization of CPU resources as parallelism grows, mainly because of the communication and synchronization among parallel processes. It is challenging but important for a data center to achieve a certain level of utilization of its nodes while maintaining the level of responsiveness of parallel jobs. Existing parallel scheduling mechanisms normally take responsiveness as the top priority and need nontrivial effort to make them work for data centers in the cloud era. In this paper, we propose a priority-based method to consolidate parallel workloads in the cloud. We leverage virtualization technologies to partition the computing capacity of each node into two tiers, the foreground virtual machine (VM) tier (with high CPU priority) and the background VM tier (with low CPU priority). We provide scheduling algorithms for parallel jobs to make efficient use of the two tier VMs to improve the responsiveness of these jobs. Our extensive experiments show that our parallel scheduling algorithm significantly outperforms commonly used algorithms such as extensible argonne scheduling system in a data center setting. The method is practical and effective for consolidating parallel workload in data centers.

The cloud computing paradigm attracts increasing amount of efforts to move high performance parallel applications to run in remote data centres. How to balance the performance requirements of parallel applications and the data centre utilization is essential to the move. Existing parallel scheduling mechanisms normally do not consider workload consolidation for improving server utilization. In this paper, we propose a two-tier architecture to organize virtual machines for workload consolidation. The two-tier virtual machines have different CPU priorities. We give a parallel job scheduling algorithm called Two EASY, which extends EASY algorithm, to take care of the job responsiveness in such an architecture. Our extensive experiments show that TwoEASY significantly outperforms the commonly used EASY algorithm in a datacentre setting. The method is practical and effective for consolidating parallel workload in datacentres.

Applications in many areas are increasingly developed and ported using the Map Reduce framework (more specifically, Hadoop) to exploit (data) parallelism. The application scope of Map Reduce has been extended beyond the original design goal which was large-scale data processing. This extension inherently makes a need for scheduler to explicitly take into account characteristics of job for two main goals of efficient resource use and performance improvement. In this paper, we study Map Reduce scheduling strategies to effectively deal with different workload characteristics CPU intensive and I/O intensive. We present the Workload Characteristic Oriented Scheduler (WCO), which strives for co-locating tasks of possibly different Map Reduce jobs with complementing resource usage characteristics. WCO is characterized by its essentially dynamic and adaptive scheduling decisions using information obtained from its characteristic estimator. Workload characteristics of tasks are primarily estimated by sampling with the help of some static task selection strategies, e.g., Java byte code analysis. Results obtained from extensive experiments using 11 benchmarks in a 4-node local cluster and a 51-node Amazon EC2 cluster show 17% performance improvement on average in terms of throughput in the situation of co-existing diverse workloads.

The paper discusses a resource management method at the cloud tenant level. It concerns efficiently running a profitable service on resources leased from a cloud infrastructure provider. Particularly, the paper focuses on services that handle parallelizable client requests, e.g, such a request can be processed using a MPI or a MapReduce program. The objective is to manage resource use to just satisfy the performance requirements of clients and avoid the common over-provisioning or under-provisioning problem. The proposed resource management method makes initial resource leasing plan based on client request profile and performance targets in service level agreements (SLAs). It then dynamically adjusts resource allocation based on monitoring data. Our extensive experiments show that the method is able to provision and efficiently use resources to just satisfy the SLA targets.

A critical component in mass spectrometry (MS)-based proteomics is an accurate protein identification procedure. Database search algorithms commonly generate a list of peptide-spectrum matches (PSMs). The validity of these PSMs is critical for downstream analysis since proteins that are present in the sample are inferred from those PSMs. A variety of postprocessing algorithms have been proposed to validate and filter PSMs. Among them, the most popular ones include a semi-supervised learning (SSL) approach known as Percolator and an empirical modeling approach known as PeptideProphet. However, they are predominantly designed for commercial database search algorithms, i.e., SEQUEST and MASCOT. Therefore, it is highly desirable to extend and optimize those PSM postprocessing algorithms for open source database search algorithms such as X!Tandem. In this paper, we propose a Self-boosted Percolator for postprocessing X!Tandem search results. We find that the SSL algorithm utilized by Percolator depends heavily on the initial ranking of PSMs. Starting with a poor PSM ranking list may cause Percolator to perform suboptimally. By implementing Percolator in a cascade learning manner, we can progressively improve the performance through multiple boost runs, enabling many more PSM identifications without sacrificing false discovery rate (FDR).

Application profiling is an important technique for efficient resource management. The decision making of scheduling and resource allocation typically takes great advantage of such a technique primarily for improving resource utilization. With the advent of cloud computing as a multitenant virtualized platform, diverse applications are increasingly deployed onto the cloud and they more than often share physical resources. The background load (other applications running on the same physical machine) is therefore an important factor for profiling an application in this cloud computing scenario. In this paper, we present a novel application profiling technique using the canonical correlation analysis (CCA) method, which identifies the relationship between application performance and resource usage. We further devise a performance prediction model based on application profiles generated using CCA. Clearly, our profiling technique with this prediction model has a lot of potentials particularly in virtual machine (VM) placement with performance awareness. Our experimental results demonstrate the capability of our profiling technique and the accuracy of our prediction model.

The recent cloud computing paradigm represents a trend of moving business applications to platforms run by parties located in different administrative domains. A cloud platform is often highly scalable and cost-effective through its pay-as-you-go pricing model. However, being shared by a large number of users, the running of applications in the platform faces higher performance uncertainty compared to a dedicated platform. Existing Service Level Agreements (SLAs) cannot sufficiently address the performance variation issue. In this paper, we use utility theory leveraged from economics and develop a new utility model for measuring customer satisfaction in the cloud. Based on the utility model, we design a mechanism to support utility-based SLAs in order to balance the performance of applications and the cost of running them. We consider an infrastructure-as-a-service type cloud platform (e.g., Amazon EC2), where a business service provider leases virtual machine (VM) instances with spot prices from the cloud and gains revenue by serving its customers. Particularly, we investigate the interaction of service profit and customer satisfaction. In addition, we present two scheduling algorithms that can effectively bid for different types of VM instances to make tradeoffs between profit and customer satisfaction. We conduct extensive simulations based on the performance data of different types of Amazon EC2 instances and their price history. Our experimental results demonstrate that the algorithms perform well across the metrics of profit, customer satisfaction and instance utilization.

This paper addresses a resource selection problem for applications that update data in enterprise grid systems. The problem is insufficiently addressed as most of the existing resource selection approaches in grid environments primarily deal with read-only job. We propose a simple yet efficient algorithm that deals with the complexity of resource selection problem in enterprise grid systems. The problem is formulated as a Multi Criteria Decision Making (MCDM) problem. Our proposed algorithm hides the complexity of resource selection process without neglecting important components that affect job response time. The difficulty on estimating job response time is captured by representing them in terms of different QoS criteria levels at each resource. Our experiments show that the proposed algorithm achieves very good results with good system performance as compared to existing algorithms.

BACKGROUND: Complex diseases are commonly caused by multiple genes and their interactions with each other. Genome-wide association (GWA) studies provide us the opportunity to capture those disease associated genes and gene-gene interactions through panels of SNP markers. However, a proper filtering procedure is critical to reduce the search space prior to the computationally intensive gene-gene interaction identification step. In this study, we show that two commonly used SNP-SNP interaction filtering algorithms, ReliefF and tuned ReliefF (TuRF), are sensitive to the order of the samples in the dataset, giving rise to unstable and suboptimal results. However, we observe that the 'unstable' results from multiple runs of these algorithms can provide valuable information about the dataset. We therefore hypothesize that aggregating results from multiple runs of the algorithm may improve the filtering performance. RESULTS: We propose a simple and effective ensemble approach in which the results from multiple runs of an unstable filter are aggregated based on the general theory of ensemble learning. The ensemble versions of the ReliefF and TuRF algorithms, referred to as ReliefF-E and TuRF-E, are robust to sample order dependency and enable a more informative investigation of data characteristics. Using simulated and real datasets, we demonstrate that both the ensemble of ReliefF and the ensemble of TuRF can generate a much more stable SNP ranking than the original algorithms. Furthermore, the ensemble of TuRF achieved the highest success rate in comparison to many state-of-the-art algorithms as well as traditional χ2-test and odds ratio methods in terms of retaining gene-gene interactions.

A primary driving force of the recent cloud computing paradigm is its inherent cost effectiveness. As in many basic utilities, such as electricity and water, consumers/clients in cloud computing environments are charged based on their service usage, hence the term `pay-per-use'. While this pricing model is very appealing for both service providers and consumers, fluctuating service request volume and conflicting objectives (e.g., profit vs. response time) between providers and consumers hinder its effective application to cloud computing environments. In this paper, we address the problem of service request scheduling in cloud computing systems. We consider a three-tier cloud structure, which consists of infrastructure vendors, service providers and consumers, the latter two parties are particular interest to us. Clearly, scheduling strategies in this scenario should satisfy the objectives of both parties. Our contributions include the development of a pricing model-using processor-sharing-for clouds, the application of this pricing model to composite services with dependency consideration (to the best of our knowledge, the work in this study is the first attempt), and the development of two sets of profit-driven scheduling algorithms.

When multiple instances of an application running on multiple virtual machines, an interesting problem is how to utilize the fault handling result from one application instance to heal the same fault occurred on other sibling instances, and hence to ensure high service availability in a cloud computing environment. This paper presents SHelp, a lightweight runtime system that can survive software failures in the framework of virtual machines. It applies weighted rescue points and error virtualization techniques to effectively make applications by-pass the faulty path. A two-level storage hierarchy is adopted in the rescue point database for applications running on different virtual machines to share error handling information to reduce the redundancy and to more effectively and quickly recover from future faults caused by the same bugs. A Linux prototype is implemented and evaluated using four web server applications that contain various types of bugs. Our experimental results show that SHelp can make server applications to recover from these bugs in just a few seconds with modest performance overhead.

BACKGROUND: It has now become clear that gene-gene interactions and gene-environment interactions are ubiquitous and fundamental mechanisms for the development of complex diseases. Though a considerable effort has been put into developing statistical models and algorithmic strategies for identifying such interactions, the accurate identification of those genetic interactions has been proven to be very challenging. METHODS: In this paper, we propose a new approach for identifying such gene-gene and gene-environment interactions underlying complex diseases. This is a hybrid algorithm and it combines genetic algorithm (GA) and an ensemble of classifiers (called genetic ensemble). Using this approach, the original problem of SNP interaction identification is converted into a data mining problem of combinatorial feature selection. By collecting various single nucleotide polymorphisms (SNP) subsets as well as environmental factors generated in multiple GA runs, patterns of gene-gene and gene-environment interactions can be extracted using a simple combinatorial ranking method. Also considered in this study is the idea of combining identification results obtained from multiple algorithms. A novel formula based on pairwise double fault is designed to quantify the degree of complementarity. CONCLUSIONS: Our simulation study demonstrates that the proposed genetic ensemble algorithm has comparable identification power to Multifactor Dimensionality Reduction (MDR) and is slightly better than Polymorphism Interaction Analysis (PIA), which are the two most popular methods for gene-gene interaction identification. More importantly, the identification results generated by using our genetic ensemble algorithm are highly complementary to those obtained by PIA and MDR. Experimental results from our simulation studies and real world data application also confirm the effectiveness of the proposed genetic ensemble algorithm, as well as the potential benefits of combining identification results from different algorithms.

BACKGROUND: Feature selection techniques are critical to the analysis of high dimensional datasets. This is especially true in gene selection from microarray data which are commonly with extremely high feature-to-sample ratio. In addition to the essential objectives such as to reduce data noise, to reduce data redundancy, to improve sample classification accuracy, and to improve model generalization property, feature selection also helps biologists to focus on the selected genes to further validate their biological hypotheses. RESULTS: In this paper we describe an improved hybrid system for gene selection. It is based on a recently proposed genetic ensemble (GE) system. To enhance the generalization property of the selected genes or gene subsets and to overcome the overfitting problem of the GE system, we devised a mapping strategy to fuse the goodness information of each gene provided by multiple filtering algorithms. This information is then used for initialization and mutation operation of the genetic ensemble system. CONCLUSION: We used four benchmark microarray datasets (including both binary-class and multi-class classification problems) for concept proving and model evaluation. The experimental results indicate that the proposed multi-filter enhanced genetic ensemble (MF-GE) system is able to improve sample classification accuracy, generate more compact gene subset, and converge to the selection results more quickly. The MF-GE system is very flexible as various combinations of multiple filters and classifiers can be incorporated based on the data characteristics and the user preferences.

The paper presents EvolvingSpace, a data centric distributed system, which is intended to address the data and application integration problem in bioinformatics data centers. The system employs commodity PCs for data storage and computation. EvolvingSpace manages data in a decentralized manner, which is convenient for storing data annotations and can eliminate potential data-access bottlenecks. It indexes distributed data in multilevels to facilitate the construction of complex workflows that consist of applications running on different types of data. In addition, the paper proposes a data locality and workflow aware scheduling algorithm (ES-Scheduling) to balance the data distribution and computing performance as well as throughput and workflow response time. We run extensive experiments using the system with real bioinformatics applications. Our results show that the system is efficient for running integrated bioinformatics applications and has good scalability.

As genome sequence databases grow in size, the accuracy and speed of sequence similarity detection become more important. There is an increasing number of methods being used for detecting sequence similarity. Meanwhile the demands for genome sequence search and alignment services are also increasing. It is a challenge to scale up the computer systems for hosting various methods and serving requests to these methods in a timely manner. Traditional clusters, which are used in most of scientific centers, can not cope with this challenge. This paper tackles this problem in a novel way, which treats the sequence search requests as content requests to both genome databases and similarity detection methods; therefore, scaling up the computer systems that serve these contents is a process of constructing content distribution network. The paper gives a decentralized method to dynamically construct content distribution networks for a variety of genome sequence similarity detection services. It also provides a scheduling algorithm for efficiently using content nodes. Our simulation study shows that scalability and high content node utilization can be achieved in such a system while the cost of achieving remains reasonable.

This paper presents a novel approach to solve the Multiple Sequence Alignment (MSA) problem. The Rubber Band Technique: Index Base (RBT-I) introduced in this paper, is inspired by the elastic behavior of a Rubber Band (RB) on a plate with poles. RBT-I is an iterative optimization algorithm designed and implemented to find the optimal alignment for a set of input Protein sequences. In this technique, the alignment answer of the MSA problem is modeled as a RB, while the answer space is modeled as the plate with several poles resembling locations in the input sequences that are most likely to be correlated and/or biologically related. Fixing the head and tail of the RB at two corners of this plate, the RB is free to bend and finds its best configuration, yielding the best answer for the MSA problem. RBT-I is tested with one of the well-known benchmarks (BALiBASE 2.0) in this field. The obtained results show the superiority of the proposed technique even in the case of formidable sequences.

In this study, we propose a new machine learning model namely, Adaptive Locality-Effective Kernel Machine (Adaptive-LEKM) for protein phosphorylation site prediction. Adaptive-LEKM proves to be more accurate and exhibits a much stable predictive performance over the existing machine learning models. Adaptive-LEKM is trained using Position Specific Scoring Matrix (PSSM) to detect possible protein phosphorylation sites for a target sequence. The performance of the proposed model was compared to seven existing different machine learning models on newly proposed PS-Benchmark_1 dataset in terms of accuracy, sensitivity, specificity and correlation coefficient. Adaptive-LEKM showed better predictive performance with 82.3% accuracy, 80.1% sensitivity, 84.5% specificity and 0.65 correlation-coefficient than contemporary machine learning models.

BACKGROUND: Post-translational modifications have a substantial influence on the structure and functions of protein. Post-translational phosphorylation is one of the most common modification that occur in intracellular proteins. Accurate prediction of protein phosphorylation sites is of great importance for the understanding of diverse cellular signalling processes in both the human body and in animals. In this study, we propose a new machine learning based protein phosphorylation site predictor, SiteSeek. SiteSeek is trained using a novel compact evolutionary and hydrophobicity profile to detect possible protein phosphorylation sites for a target sequence. The newly proposed method proves to be more accurate and exhibits a much stable predictive performance than currently existing phosphorylation site predictors. RESULTS: The performance of the proposed model was compared to nine existing different machine learning models and four widely known phosphorylation site predictors with the newly proposed PS-Benchmark_1 dataset to contrast their accuracy, sensitivity, specificity and correlation coefficient. SiteSeek showed better predictive performance with 86.6% accuracy, 83.8% sensitivity, 92.5% specificity and 0.77 correlation-coefficient on the four main kinase families (CDK, CK2, PKA, and PKC). CONCLUSION: Our newly proposed methods used in SiteSeek were shown to be useful for the identification of protein phosphorylation sites as it performed much better than widely known predictors on the newly built PS-Benchmark_1 dataset.

BACKGROUND: Protein domains present some of the most useful information that can be used to understand protein structure and functions. Recent research on protein domain boundary prediction has been mainly based on widely known machine learning techniques, such as Artificial Neural Networks and Support Vector Machines. In this study, we propose a new machine learning model (IGRN) that can achieve accurate and reliable classification, with significantly reduced computations. The IGRN was trained using a PSSM (Position Specific Scoring Matrix), secondary structure, solvent accessibility information and inter-domain linker index to detect possible domain boundaries for a target sequence. RESULTS: The proposed model achieved average prediction accuracy of 67% on the Benchmark_2 dataset for domain boundary identification in multi-domains proteins and showed superior predictive performance and generalisation ability among the most widely used neural network models. With the CASP7 benchmark dataset, it also demonstrated comparable performance to existing domain boundary predictors such as DOMpro, DomPred, DomSSEA, DomCut and DomainDiscovery with 70.10% prediction accuracy. CONCLUSION: The performance of proposed model has been compared favourably to the performance of other existing machine learning based methods as well as widely known domain boundary predictors on two benchmark datasets and excels in the identification of domain boundaries in terms of model bias, generalisation and computational requirements.

As the increase of genome database size, there are increasing number of methods for detecting sequence similarity and increasing demands for genome sequence search and alignment services. It is a challenge to scale up the computer systems for serving these demands in a timely manner. This paper tackles this problem from a novel perspective, which treats the sequence search requests as content requests to both genome databases and similarity detection methods; therefore, scaling up the computer systems that serve these contents is a process of constructing content distribution network. The paper gives a decentralized method to construct content distribution network for a variety of genome sequence similarity detection services. It also gives a scheduling algorithm for efficiently using content nodes. Our simulation results show that scalability and high content node utilization can be achieved in such a system while the costs of achieving these are controllable.

In DHT-based P2P systems, Replication-based content distribution and load balancing strategies consists of such decisions as which files should be replicated, how many replicas should be created and where to replicate them in order increase the system performance in the presence of non-uniform data and access distribution. There are many works on replica placement policies; however, the impact of system workload on different replica placement strategies is not well studied. We investigate this problem under the context of content addressable overlay networks. We compare a trace based replica placement algorithm with two of its variations, namely random placement and priority based placement under different workloads. Our experimental results show that the effect of replica placement policy is highly affected by the workload of the system, which indicates that an adaptive replica placement strategy is desirable for content distribution in an overlay network.

An interesting and important, hut largely ignored question associated with the ML method is whether there exists only a single maximum likelihood point for a given phylogenetic tree. Mike Steel presented a simple analytical result to argue that the ML point is not unique. However, his view so far attracts only little attention. Though many researchers believe that multiple maximum likelihood points may exist for certain phylogenetic trees, most existing phylogenetic construction programs only produce a single best tree under the ML criterion and in practice many researchers still use only the ML values to make judgment on the quality of different trees for a given problem. In this paper we present some experimental results from a large number of synthetic test data sets and show that it is quite common that certain incorrect trees can have likelihood values at least as large as that of the correct tree. A significant implication of this is that even if we are able to find a truly globally optimal tree under the maximum likelihood criterion, this tree may not necessarily be the correct phylogenetic tree. In the paper we also show that our newly developed algorithm can perform much better in terms of accuracy than well known algorithms such as FASTDNAML and PHYML by constructing only a few more trees for a given problem

This paper describes a parallel implementation of our recently developed algorithm for phylogenetic analysis on the IBM BlueGene/L cluster. This algorithm constructs evolutionary trees for a given set of DNA or protein sequences based on the topological information of every possible quartet trees. Our experimental results showed that it has several advantages over many popular algorithms. By distributing the quartet weights evenly across the processing nodes and making effective use of a fast collective network on the IBM BlueGene/L cluster, we are able to achieve a close to linear speedup even when the number of processors involved in the computation is large.

The paper discusses the access-skew problem in a data indexed DHT network. The difference in popularity of data indexes is likely to create access hotspots that overwhelm the host node. The capability of relieving heavily loaded nodes is essential to the scalability of an overlay network. In this paper, we propose an effective content distribution method to relieve hotspots in a selforganizing manner. An algorithm is given to reduce the query traveling distance and balance the load among replica nodes. Moreover, we give a small-world model based algorithm to reduce the load-balancing cost. Experiment results show that the mechanism significantly reduces the number of dropped queries and the average query delay while keeping loadbalancing cost under control.

In this paper we introduce a new quartet-based method. This method makes use of the Bayes (or quartet) weights of quartets as those used in the quartet puzzling. However, all the weights from the related quartets are accumulated to form a global quartet weight matrix. This matrix provides integrated information and can lead us to recursively merge small sub-trees to larger ones until the final single tree is obtained. The experimental results show that the probability for the correct tree to be among a very small number of trees constructed using our method is very high. These significant results open a new research direction to further investigate more efficient algorithms for phylogenetic inference.

Most of bioinformatics data distributed on the Internet is organized in an unstructured manner, which makes it hard to construct applications that need to integrate them. In this paper, we proposed an XML schema based data indexing mechanism to integrate sequence databases stored in a DHT overlay network. The construction of large-scale distributed applications therefore can be greatly simplified with the support of structured distributed data. We present a system that can seamlessly integrate sequence databases and computing resources together to provide BLAST query services based on the data indexing mechanism. Our experiments show that, with a data centric scheduling algorithm to improve the processor utilization, the BLAST service can achieve scalable high throughput.

Summary form only given. Here we describe a new parallel program package for phylogenetic analysis of DNA sequences. This program is based on a more advanced algorithm, named advanced stepwise addition (ASA), for phylogenetic analysis using maximum likelihood approaches. There are two main advantages of our parallel program package over many existing ones. Firstly the size of the tree search space can be freely chosen and so we are able to fill up a large-scale supercomputer (as long as it is computationally feasible) to alleviate the problems of thoroughness and phylogenetic uncertainty. Secondly we adopt SPMD programming technique in our implementation. Obvious advantages of SPMD technique over the simple master/workers technique are as follows: Firstly, communication procedures are deterministic. This effectively eliminates the requirement for detecting and requesting for communication between processors. Secondly, there is no need to communicate between processors after completion of each single tree likelihood evaluation. The communication takes place only at the end of each iteration by sending/receiving among the processors small messages for identifying the current k best trees and certain number of trees for balancing the workload. This can effectively reduce the overall communication costs and alleviate the problem of communication bottleneck caused by using the simple master/workers technique. Therefore, our approach is more suitable for execution on large-scale high-performance parallel computers.

Applying gang scheduling can alleviate the blockade problem caused by exclusively space-sharing scheduling. To simply allow jobs to ran simultaneously on the same processors as in conventional gang scheduling, however, may introduce a large number of time slots in the system. In consequence the cost of context switches will be greatly increased, and each running job can only obtain a small portion of resources including memory space and processor utilisation and so no jobs can finish their computations quickly. Therefore, the number of jobs allowed to run in the system should be limited. In this paper we present some experimental results to show that by limiting real large jobs time-sharing the same processors and applying the backfilling technique we can greatly reduce the average number of time slots in the system and significantly improve the performance of both small and large jobs.

... Project is a joint research program involving staff at the Aus-tralian National University and Fujitsu Japan. The aim of the project is to produce a library of mathematical subrou-tines for the vector-parallel Fujitsu VPP300 which result in high performance and accuracy on large problems. In order to utilise the architecture of the VPPSOO it is necessary to develop new algorithms for many of the standard numerical problems.

The problem of merging two sequences of elements which are stored separately in two processing elements (PEs) occurs in the implementation of many existing sorting algorithms. We describe efficient algorithms for the merging problem on asynchronous distributed-memory machines. The algorithms reduce the cost of the merge operation and of communication, as well as partly solving the problem of load balancing. Experimental results on a Fujitsu AP1000 are reported.

We describe a new Jacobi ordering for parallel computation of SVD problems. The ordering uses the high bandwidth of a perfect binary fat-tree to minimise global interprocessor communication costs. It can thus be implemented efficiently on fat-tree architectures.

A stabilized parallel algorithm for direct-form recursive filters is obtained, using a method of derivation in the Z domain. The degree of parallelism, stability, and complexity of the algorithm is examined. It is shown how to reduce the number of multiplications compared to the number required in a naive implementation. The algorithm is regular and modular, so very efficient VLSI architectures can be constructed to implement it. The degree of parallelism in these implementations can be chosen freely and is not restricted to be a power of two.>

The authors introduce a high-throughput systolic implementation of the direct-form second-order recursive filter. The systolic structure has the advantage of regularity over implementations of the block-state-variable form. Since communication is very expensive in VLSI implementations in terms of area, as well as time, this regular structure is considered better for VLSI than those based on block-state-variable filter descriptions.>

A bit-serial systolic array has been developed to computer multiplications over GF(2/sup m/). In contrast to a previously designed systolic multiplier, this algorithm allows the input elements to center a linear systolic array in the same order, and the system only requires one control signal.>