Cryo-electron tomography, combined with subtomogram averaging (STA), can reveal three-dimensional (3D) macromolecule structures in the near-native state from cells and other biological samples. In STA, to get a high-resolution 3D view of macromolecule structures, diverse macromolecules captured by the cellular tomograms need to be accurately classified. However, due to the poor signal-to-noise-ratio (SNR) and severe ray artifacts in the tomogram, it remains a major challenge to classify macromolecules with high accuracy. In this paper, we propose a new convolutional neural network, named 3D-Dilated-DenseNet, to improve the performance of macromolecule classification. In 3D-Dilated-DenseNet, there are two key strategies to guarantee macromolecule classification accuracy: 1) Using dense connections to enhance feature map utilization (corresponding to the baseline 3D-C-DenseNet); 2) Adopting dilated convolution to enrich multi-level information in feature maps. We tested 3D-Dilated-DenseNet and 3D-C-DenseNet both on synthetic data and experimental data. The results show that, on synthetic data, compared with the state-of-the-art method in the SHREC contest (SHREC-CNN), both 3D-C-DenseNet and 3D-Dilated-DenseNet outperform SHREC-CNN. In particular, 3D-Dilated-DenseNet improves 0.393 of F1 metric on tiny-size macromolecules and 0.213 on small-size macromolecules. On experimental data, compared with 3D-C-DenseNet, 3D-Dilated-DenseNet can increase classification performance by 2.1 percent.

Cloud data centers provide end-users with a wide range of application scenarios, including scientific computing, smart grids, etc. The number and size of data centers have rapidly increased in recent years, which causes severe environmental problems and colossal power demand. Therefore, it is desirable to use a proper scheduling method to optimize resource usage and reduce energy consumption in a data center. However, it is rather difficult to design an effective and efficient task scheduling algorithm because of the dynamic and complex environment of data centers. This paper proposes a task scheduling algorithm, WSS, to optimize resource usage and reduce energy consumption based on a model-free deep reinforcement learning framework inspired by the Wolpertinger architecture. The proposed algorithm can handle the scheduling problem on a sizeable discrete action space, improve decision efficiency, and save the training convergence time. Meanwhile, the proposed algorithm based on Soft Actor-Critic is designed to improve the stability and exploration capability of WSS. Experiments based on real-world traces prove that WSS can reduce energy consumption by nearly 25% compared with the Deep Q-network task scheduling algorithm. Moreover, WSS can provide a short time of training convergence without increasing the average waiting time of tasks and achieve stable performance.

Three-dimensional (3D) reconstruction of cryo-electron microscopy (cryo-EM) is a powerful method to determine the structures of macromolecules at near-atomic resolution. Recently, larger size with finer resolution 2D images has been collected, which can improve the reconstruction resolution. However, large size data incurs high computation and huge memory overhead. Current implementations fail to perform the complete reconstruction workflow on a multi-GPU cluster for large size data. Because of no effective parallel method for 3D convolution and the huge memory demanding, large size data can not be efficiently reconstructed, which impede the resolution improving 3D reconstruction. To enable cryo-EM 3D reconstruction with large size data on multi-GPU, in this work, we propose a new parallel framework called OML-Relion. In OML-Relion, we first adopt a stride based Fourier transform and eliminate data dependence to parallelize the 3D convolution on multi-GPU. Considering the input size varying in each iteration, we next use an auto-tuning model to optimize 3D convolution performance. Finally, guaranteeing the whole reconstruction on a multi-GPU cluster for large size data, we design a novel lossless data compression algorithm to reduce memory overhead on each GPU further. The experiment shows that OML-Relion can efficiently handle large size cryo-EM 3D reconstruction on multi-GPU. The reconstruction module, including 3D convolution operation, achieves 225-330x times speedup for 200-800 pixel size particles. The compression algorithm significantly reduces memory overhead approaching 70%. Moreover, the whole workflow with OMLRelion can achieve 54-65x speedup compared with Relion using two large size datasets.

BACKGROUND: Proteins are of extremely vital importance in the human body, and no movement or activity can be performed without proteins. Currently, microscopy imaging technologies developed rapidly are employed to observe proteins in various cells and tissues. In addition, due to the complex and crowded cellular environments as well as various types and sizes of proteins, a considerable number of protein images are generated every day and cannot be classified manually. Therefore, an automatic and accurate method should be designed to properly solve and analyse protein images with mixed patterns. RESULTS: In this paper, we first propose a novel customized architecture with adaptive concatenate pooling and "buffering" layers in the classifier part, which could make the networks more adaptive to training and testing datasets, and develop a novel hard sampler at the end of our network to effectively mine the samples from small classes. Furthermore, a new loss is presented to handle the label imbalance based on the effectiveness of samples. In addition, in our method, several novel and effective optimization strategies are adopted to solve the difficult training-time optimization problem and further increase the accuracy by post-processing. CONCLUSION: Our methods outperformed the SOTA method of multi-labelled protein classification on the HPA dataset, GapNet-PL, by above 2% in the F1 score. Therefore, experimental results based on the test set split from the Human Protein Atlas dataset show that our methods have good performance in automatically classifying multi-class and multi-labelled high-throughput microscopy protein images.

In cryo-electron microscopy, RELION is a powerful tool for high-resolution reconstruction. Due to the complicated imaging procedure and the heterogeneity of particles, some of the selected particle images offer more disturbing information than others. However, in the current RELION, all these particle images are treated equally. In our work, we extend RELION's model with one scalar parameter to score the contribution of a particle depending on the error between the experimental particle and the corresponding reprojection. This scores down weight potentially poor particles, hence accelerating the convergence. Besides, by now there is no sophisticated memory management system for RELION, fragmentation on GPU will increase with iterations, eventually crashing the program. In our work, we designed the stack-based memory management system to guarantee the stability of RELION and to optimize the memory usage condition. Also, to reduce memory usage, we developed a customized compressed data structure for the memory-demanding weight array. In addition, to speed up the GPU version of RELION, we proposed two highly efficient parallel algorithms for weight calculation algorithm and weight selection algorithm. Experiments show that compared with RELION, the optimized three-dimensional refine algorithm can speed up the converge procedure, the memory system can avoid memory fragmentation, and a better speed-up ratio can be obtained.

The size and number of cloud data centers (CDCs) have grown rapidly with the increasing popularity of cloud computing and high-performance computing. This has the unintended consequences of creating new challenges due to inefficient use of resources and high energy consumption. Hence, this necessitates the need to maximize resource utilization and ensure energy efficiency in CDCs. One viable approach to achieve energy efficiency and resource utilization in CDC is task scheduling. While several task scheduling approaches have been proposed in the literature, there appears to be a lack of classification-based merging concept for real-time tasks in these existing approaches. Thus, an energy-efficient dynamic scheduling scheme (EDS) of real-time tasks for virtualized CDC is presented in this paper. In the scheduling scheme, the heterogeneous tasks and virtual machines are first classified based on a historical scheduling record. Then, similar type of tasks are merged and scheduled to maximally utilize an operational state of the host. In addition, energy efficiencies and optimal operating frequencies of heterogeneous physical hosts are employed to attain energy preservation while creating and deleting the virtual machines. Experimental results show that, in comparison with existing techniques, EDS significantly improves overall scheduling performance, achieves a higher CDC resource utilization, increases task guarantee ratio, minimizes the mean response time, and reduces energy consumption.

Cloud data centers (CDCs) have become increasingly popular and widespread in recent years with the growing popularity of cloud computing and high-performance computing. Due to the multi-step computation of data streams and heterogeneous task dependencies, task failure frequently occurs, resulting in poor user experience and additional energy consumption. To reduce task execution failure as well as energy consumption, we propose a novel AI-driven energy-aware proactive fault-tolerant scheduling scheme for CDCs in this paper. First, a prediction model based on the machine learning approach is trained to classify the arriving tasks into “failure-prone tasks” and “non-failure-prone tasks” according to the predicted failure rate. Then, two efficient scheduling mechanisms are proposed to allocate two types of tasks to the most appropriate hosts in a CDC. The vector reconstruction method is developed to construct super tasks from failure-prone tasks and separately schedule these super tasks and non-failure-prone tasks to the most suitable physical host. All the tasks are scheduled in an earliest-deadline-first manner. Our evaluation results show that the proposed scheme can intelligently predict task failure and achieves better fault tolerance and reduces total energy consumption better than the existing schemes.

The size and amount of colocation data centers (colocations, for short) have been growing rapidly with the increasing popularity of cloud services, which ultimately causes a heavy burden on the power grid and the environment. However, even a colocation owner wishes to reduce its energy consumption, it may not be able to apply some effective energy saving techniques directly to the servers, since the servers belong to and are operated by its tenants. To solve the "uncoordinated relationship" issue between owners and tenants and achieve the energy reduction with a limited cost budget, an energy saving-oriented incentive mechanism, ESCo is proposed in this paper. Different from existing mechanisms that emphasize on minimizing the cost for the owners, our mechanism emphasizes on the maximization of the amount of energy saved by the tenants given a limited budget that the owner wants to pay for the energy saving. An algorithm is developed to realize a stable assignment in the mechanism. Trace-driven simulations based on real-world data are performed to verify the effectiveness of ESCo. The results show that ESCo can achieve 14.47% more energy saving than existing colocation incentive mechanisms.

Web latency remains the main obstacle to improving user experience with the continuous development of the web. A lot of works have been made in this course. Quick UDP Internet Connection (QUIC) embeds stream multiplexing to solve the head-of-line blocking caused by the in-order requirement of TCP. Multipath-QUIC (MPQUIC) brings further improvements by utilizing multiple paths, as is done in MultiPath TCP (MPTCP). Different from MPTCP schedulers, MPQUIC schedulers are stream-aware and thus can provide finer granularity of multipath scheduling. As streams are with different features based on their contents, the resource preferences of a stream are highly related to its feature. We find that scheduling without the recognition of the stream features can aggravate inter-stream blocking when sharing paths. We fill this gap and propose PStream - a priority-based online stream scheduling mechanism for MPQUIC, which performs path scheduling based on the stream features. We examine the effectiveness of PStream under different path heterogeneity comparing to the original and the latest scheduler of MPQUIC. Our evaluation shows that our scheduler can reduce up to 25.4% of page load time in high path heterogeneity.

Colocation data centers (colocations, for short) are developing rapidly in recent years, resulting in a heavy burden on the power grid and the environment. Due to the special management mode of colocations, even the colocation operators wish to reduce their power demand, they have no authority to control the servers because the servers belong to and are operated by the tenants themselves. To solve the "uncoordinated relationship" issue between operators and tenants, a truthful and feasible incentive mechanism MesPP is proposed in this paper. Different from existing works, MesPP aims at maximizing the energy reduction of colocations with a limited cost budget and can be applied even there is no demand response (DR) program. Meanwhile, power prediction is integrated into MesPP to further improve the energy efficiency of colocations and fairness of the mechanism. To solve the optimization problem, we develop a (1−ε)-approximation algorithm. Simulations are performed and show that MesPP can achieve 12.23% more energy saving compared with existing incentive mechanisms.

Abstract Background Electron tomography (ET) is an important technique for the study of complex biological structures and their functions. Electron tomography reconstructs the interior of a three-dimensional object from its projections at different orientations. However, due to the instrument limitation, the angular tilt range of the projections is limited within +70∘ to −70∘. The missing angle range is known as the missing wedge and will cause artifacts. Results In this paper, we proposed a novel algorithm, compressed sensing improved iterative reconstruction-reprojection (CSIIRR), which follows the schedule of improved iterative reconstruction-reprojection but further considers the sparsity of the biological ultra-structural content in specimen. The proposed algorithm keeps both the merits of the improved iterative reconstruction-reprojection (IIRR) and compressed sensing, resulting in an estimation of the electron tomography with faster execution speed and better reconstruction result. A comprehensive experiment has been carried out, in which CSIIRR was challenged on both simulated and real-world datasets as well as compared with a number of classical methods. The experimental results prove the effectiveness and efficiency of CSIIRR, and further show its advantages over the other methods. Conclusions The proposed algorithm has an obvious advance in the suppression of missing wedge effects and the restoration of missing information, which provides an option to the structural biologist for clear and accurate tomographic reconstruction.

On-chip optical links can consume considerable energy. Previous work shows that there exists a trade-off between the optical link bandwidth and energy consumption. In this paper, we analyze the temporal behavior of on-chip communication in typical applications and make the following observation: both ONoC and processor cores are not always busy, and there are significant amounts of time during which these components are relatively idle. Base on such an observation, we present a novel technique called Shifting Link to dynamically changing the bandwidth for optical link according to the workload situation. To evaluate our proposed method, we implement the Shifting Link in FlexiShare ONoC architecture. The experiment result shows that, on geometric mean, Shifting Link reduces the energy consumption by 35.0% with only 5.8% decrease in the performance.

While the web keeps evolving, web latency remains a major obstacle to improving user experience. In the past, many efforts have been made in this course. SPDY achieves reduced latency through multiplexing and prioritization by manipulating HTTP. Quick UDP Internet Connection (QUIC) generalizes the idea and embeds multiplexing in the transport layer by introducing application-oriented streams. Multipath-QUIC brings further improvements by utilizing multiple paths as is done in MultiPath TCP (MPTCP). However, failing to account for stream priorities in the transport layer can result in suboptimal performance for time-critical streams. We fill this gap and propose FStream - a flexible stream scheduling mechanism for Multipath-QUIC, which provides stream prioritization down to the transport layer. We implement FStream in Multipath-QUIC and demonstrate its effectiveness in reducing the completion time of time-critical streams ( 3x) through extensive experiments under different path dissimilarity conditions.

Motivation: Dual-axis electron tomography is an important 3 D macro-molecular structure reconstruction technology, which can reduce artifacts and suppress the effect of missing wedge. However, the fully automatic data process for dual-axis electron tomography still remains a challenge due to three difficulties: (i) how to track the mass of fiducial markers automatically; (ii) how to integrate the information from the two different tilt series; and (iii) how to cope with the inconsistency between the two different tilt series. Results: Here we develop a toolkit for fully automatic alignment of dual-axis electron tomography, with a simultaneous reconstruction procedure. The proposed toolkit and its workflow carries out the following solutions: (i) fully automatic detection and tracking of fiducial markers under large-field datasets; (ii) automatic combination of two different tilt series and global calibration of projection parameters; and (iii) inconsistency correction based on distortion correction parameters and the consequently simultaneous reconstruction. With all of these features, the presented toolkit can achieve accurate alignment and reconstruction simultaneously and conveniently under a single global coordinate system. Availability and implementation: The toolkit AuTom-dualx (alignment module dualxmauto and reconstruction module volrec_mltm) are accessible for general application at http://ear.ict.ac.cn, and the key source code is freely available under request. Supplementary information: Supplementary data are available at Bioinformatics online.

BACKGROUND: Cryo-electron microscopy (cryo-EM) has become a widely used tool for determining the structures of proteins and macromolecular complexes. To acquire the input for single-particle cryo-EM reconstruction, researchers must select hundreds of thousands of particles from micrographs. As the signal-to-noise ratio (SNR) of micrographs is extremely low, the performance of automated particle-selection methods is still unable to meet research requirements. To free researchers from this laborious work and to acquire a large number of high-quality particles, we propose an automated particle-selection method (PIXER) based on the idea of segmentation using a deep neural network. RESULTS: First, to accommodate low-SNR conditions, we convert micrographs into probability density maps using a segmentation network. These probability density maps indicate the likelihood that each pixel of a micrograph is part of a particle instead of just background noise. Particles selected from density maps have a more robust signal than do those directly selected from the original noisy micrographs. Second, at present, there is no segmentation-training dataset for cryo-EM. To enable our plan, we present an automated method to generate a training dataset for segmentation using real-world data. Third, we propose a grid-based, local-maximum method to locate the particles from the probability density maps. We tested our method on simulated and real-world experimental datasets and compared PIXER with the mainstream methods RELION, DeepEM and DeepPicker to demonstrate its performance. The results indicate that, as a fully automated method, PIXER can acquire results as good as the semi-automated methods RELION and DeepEM. CONCLUSION: To our knowledge, our work is the first to address the particle-selection problem using the segmentation network concept. As a fully automated particle-selection method, PIXER can free researchers from laborious particle-selection work. Based on the results of experiments, PIXER can acquire accurate results under low-SNR conditions within minutes.

MLC PCM provides high-density data storage and extended data retention; therefore it is a promising alternative for DRAM main memory. However, its low write performance is a major obstacle to commercialization. One opportunity for improving the latency of MLC PCM writes is to use fewer SET iterations in a single write. Unfortunately, this comes with a cost: the data written by these short writes have remarkably shorter retentions and thus need frequent refreshes. As a result, it is impractical to use these short-latency, short-retention writes globally. In this paper, we analyze the temporal behavior of write operations in typical applications and show that the write operations are bursty in nature, that is, during some time intervals the memory is subject to a large number of writes, while during other time intervals there hardly any memory operations take place. Based on this observation, we propose Quick-and-Dirty (QnD), a lightweight scheme to improve the performance of MLC PCM. When the write performance becomes the system bottleneck, QnD performs some write operations using the short-latency, short-retention write mode. Then, when the memory system is relatively quiet, QnD uses idle-memory intervals to refresh the data written by short-latency, short-retention writes in order to mitigate the short retention problem. Our experimental results show that QnD improves performance by 30.9 percent on geometric mean while still providing acceptable memory lifetime (7.58 years on geometric mean). We also provide sensitivity studies of the aggressiveness, memory coverage and granularity of QnD technique.

Current QoS-aware automatic service composition queries over a network of web services are often one-time in nature. After a network of web services is built, such queries are issued once, and answers are found from the scratch. The underlying assumption is that the participating web services are rather static, which means that their functional and non-functional parameters seldom change. However, such an assumption is often baseless. New services come and go, service APIs change gradually, and QoS values fluctuate in practice. Therefore, a support for efficiently adapting service composition is desired. In this paper, we propose an event driven continuous query algorithm to intelligently cope with different types of dynamic services, and thus enable evolution of service composition. Evaluation using both real QoS data and synthetic web service data shows its superior performance, compared with the state-of-the-art solution which won the performance championship of Web Service Challenge in 2009 and 2010. Moreover, we generalize a new graph problem: dynamic single-source optimal-Directed Acyclic Graphs (DAG) problem based on the above work. It is argued that API recommendation for framework evolution, as another typical application, could also be modeled and addressed efficiently using the proposed new graph approach.

Virtual machine placement is a key component of cloud resource management, which may affect network bandwidth allocation. In this paper, we revisit the virtual machine placement problem in cloud data centers and aim to maximize the overall resource utilization in multiple dimensions, while ensuring that the resource constraints on both the server such as CPU capacity and the network such as bandwidth are not violated. We model the bandwidth-guaranteed virtual machine placement problem and prove its NP-hardness, and design offline and online algorithms to solve the problem. We first consider the offline version and develop approximation algorithms with bounded performance ratios for both the homogeneous and the heterogeneous cases. Then, for the online version, we propose simple and efficient heuristics based on the insights from the offline algorithm design. Comprehensive experimental results verify that the overall resource utilization can be significantly improved by applying our proposals.

Multi Level Cell (MLC) Phase Change Memory (PCM) is an enhancement of PCM technology, which provides higher capacity by allowing multiple digital bits to be stored in a single PCM cell. However, the retention time of MLC PCM is limited by the resistance drift problem and refresh operations are required. Previous work shows that there exists a trade-off between write latency and retention-a write scheme with more SET iterations and smaller current provides a longer retention time but at the cost of a longer write latency. Otherwise, a write scheme with fewer SET iterations achieves high performance for writes but requires a greater number of refresh operations due to its significantly reduced retention time, and this hurts the lifetime of MLC PCM. In this paper, we show that only a small part of memory (i.e., hot memory regions) will be frequently accessed in a given period of time. Based on such an observation, we propose Region Retention Monitor (RRM), a novel structure that records and predicts the write frequency of memory regions. For every incoming memory write operation, RRM select a proper write latency for it. Our evaluations show that RRM helps the system improves the balance between system performance and memory lifetime. On the performance side, the system with RRM bridges 77.2% of the performance gap between systems with long writes and systems with short writes. On the lifetime side, a system with RRM achieves a lifetime of 6.4 years, while systems using only long writes and short writes achieve lifetimes of 10.6 and 0.3 years, respectively. Also, we can easily control the aggressiveness of RRM through an attribute called hot threshold. A more aggressively configured RRM can achieve the performance which is only 3.5% inferior than the system using static short writes, while still achieve a lifetime of 5.78 years.

Today's data center applications can generate a diverse mix of short and long flows. However, switches used in a typical data center network are usually shallow buffered in order to reduce queueing delay and deployment cost. As a result, the buildup of the queues by long flows can block short flows, leading to frequent packet losses and retransmissions, which translates to crucial performance degradation. While multiple end-to-end TCP-based solutions have been proposed, none of them have tackled the real challenge: reliable transmission in the network. In this paper, we fill this gap by presenting PABO — a novel link-layer design that can mitigate congestion by temporarily bouncing packets to upstream switches. PABO's design fulfills the following demands: i) providing per-flow based flow control on the link layer, ii) handling transient congestion without the intervention of end devices, and iii) gradually back propagating the congestion signal to the source when the network is not capable to handle the congestion. We complete a proof-of-concept implementation, and experiments under different severities of congestion show that PABO outperforms the standard unreliable link-layer protocol by guaranteeing zero packet loss while introducing only a reasonable stretch on packet delay.

Low write performance is a major obstacle to the commercialization of MLC PCM. One opportunity for improving the latency of MLC PCM writes is to use fewer SET iterations in a single write. Unfortunately, the data written by these short writes have significantly shorter retention time and thus need frequent refreshes. As a result, it is impractical to use these short-latency, short-retention writes globally. In this paper, we analyze the temporal behavior of write operations in typical applications and propose Quick-and-Dirty (QnD), a lightweight scheme to improve the performance of MLC PCM. QnD dynamically performs the short-latency, short-retention write when write operations are bursty, and then uses short-latency, short-retention writes to mitigate the short retention problem when memory system is relatively quiet. Our experimental results show that QnD improves performance by 30.9% on geometric mean while still providing acceptable memory lifetime (7.58 years on geometric mean). We also provide sensitivity studies of the aggressiveness, memory coverage and granularity of QnD technique.

We study the problem of flow scheduling in data center networks. Using speed scaling, our aim is to find an online scheduling algorithm that minimizes the total energy consumption of the network by determining both the transmission order and rates of the arriving flows while providing a strict flow deadline guarantee. Observing the superlinear property of link power consumption, the key challenge is in constantly determining the minimum transmission rate for “delay-tolerable” flows without any priori knowledge. To leverage the flow arrival pattern, we propose a probability-based flow prediction model to capture the uncertainty of the network flows. Based on the prediction model, we propose a tunable online flow scheduling algorithm to solve the online flow scheduling problem effectively. By introducing a scaling factor on bandwidth allocation, this algorithm allows us to conduct arbitrary trade-offs between the conservative and aggressive behaviors in terms of energy conser- vation. The effectiveness of the proposed algorithm is validated through rigorous theoretical analysis and further confirmed by extensive numerical simulations.

With the popularity of cloud computing, optimizing cloud resource consumption while providing predictable cloud service has become one of the focuses of research in recent years. In order to ensure a predictable performance, the requests from tenants are abstracted as Virtual Clusters, which not only specify the computing demands, but also establish the communication requirements among virtual machines. While much work has been done on virtual cluster embedding under a variety of goals, very few people have studied this issue in consideration of service survivability, which also plays a vital role in ensuring the performance in cloud data centers. In this paper, we study the resource optimization for survivable embedding of virtual clusters and aim to minimize the consumption of cloud resources in terms of server and bandwidth, while ensuring that both the resource constraints and the survivability constraints are not violated. We formally define this problem and analyze its complexity, and design efficient algorithms to solve the problem. Comprehensive experimental results verify that the overall resource consumption can be significantly reduced by applying our proposals.

The high energy consumption has become one bottleneck in the development of the data centers (DCs), where the main energy consumers are the cooling system and the servers. Therefore, the joint optimization for the energy efficiency of the cooling system and the servers is a crucial problem, while most of previous works on energy saving only studies one of these two components in an isolated manner. In this paper, we propose a real-time strategy, rTCS (real-time Task Classification and Scheduling strategy), to jointly optimize the energy efficiency of these two components in the scenario where the tasks arrive dynamically. Strategy rTCS first labels the tasks to classify them according to their run time and end time with a time complexity of O(1) and a bounded space complexity. Then, rTCS schedules the tasks in real time based on their labels and the energy consumption model of the DC. Simulation results show that rTCS can effectively improve the energy efficiency of DCs.

Particle selection from cryo-electron microscopy (Cryo-EM) images is very important for high-resolution reconstruction of macromolecular structure. The methods of particle selection can be roughly grouped into two classes, template-matching methods and feature-based methods. In general, template-matching methods usually generate better results than feature-based methods. However, the accuracy of template-matching methods is restricted by the noise and low contrast of Cryo-EM images. Moreover, the processing speed of template-matching methods, restricted by the random orientation of particles, further limits their practical applications. In this paper, combining the advantages of feature-based methods and template-matching methods, we present a two-phase improved correlation method for automatic, fast particle selection. In Phase I, we generate a preliminary particle set using rotation-invariant features of particles. In Phase II, we filter the preliminary particle set using a correlation method to reduce the interference of the high noise background and improve the precision of particle selection. We apply several optimization strategies, including a modified adaboost algorithm, Divide and Conquer technique, cascade strategy and graphics processing unit parallel technique, to improve feature recognition ability and reduce processing time. In addition, we developed two correlation score functions for different correlation situations. Experimental results on the benchmark of Cryo-EM images show that our method can improve the accuracy and processing speed of particle selection significantly.

Virtual machine (VM) scheduling is an important technique for the efficient operation of the computing resources in a data center. Previous work has mainly focused on consolidating VMs to improve resource utilization and to optimize energy consumption. However, the interference between collocated VMs is usually ignored, which can result in much worse performance degradation of the applications running on the VMs due to the contention of the shared resources. Based on this observation, we aim at designing efficient VM assignment and scheduling strategies in which we consider optimizing both the operational cost of the data center and the performance degradation of the running applications. We then propose a general model that captures the tradeoff between the two contradictory objectives. We present offline and online solutions for this problem by exploiting the spatial and temporal information of performance interference of VM collocation, where VM scheduling is performed by jointly considering the combinations and the life-cycle overlap of the VMs. Evaluation results show that the proposed methods can generate efficient schedules for VMs, achieving low operational cost while significantly reducing the performance degradation of applications in cloud data centers.

Existing Data Center Network (DCN) architectures are classified into two categories: switch-centric and server-centric architectures. In switch-centric DCNs, routing intelligence is placed on switches; each server usually uses only one port of the Network Interface Card (NIC) to connect to the network. In server-centric DCNs, switches are only used as cross-bars, and routing intelligence is placed on servers, where multiple NIC ports may be used. In this paper, we formally introduce a new category of DCN architectures: thedual-centricDCN architectures, where routing intelligence can be placed on both switches and servers. The dual-centric philosophy can achieve various tradeoffs in designing DCN architectures. We propose three novel dual-centric DCN architectures: FCell, FRectangle, and FSquare, all of which are based on the folded Clos topology. FCell is a power-efficient DCN architecture, with a larger diameter and lower bisection bandwidth than FSquare and FRectangle. FSquare is a high performance DCN architecture, in which the diameter is small and the bisection bandwidth is large; however, the DCN power consumption per server in FSquare is high. FRectangle significantly reduces the DCN power consumption per server, compared to FSquare, at the sacrifice of some networking performances. By investigating FCell, FRectangle and FSquare, and by comparing them with existing architectures, we demonstrate that, the three novel dual-centric architectures enjoy the advantages of both switch-centric designs and server-centric designs, have various nice properties for practical data centers, and provide flexible tradeoff choices in designing DCN architectures.

The proliferation of new online Internet services has substantially increased the energy consumption in wired networks, which has become a critical issue for Internet service providers. In this paper, we target the network-wide energy-saving problem by leveraging speed scaling as the energy-saving strategy. We propose a distributed routing scheme-HDEER-to improve network energy efficiency in a distributed manner without significantly compromising traffic delay. HDEER is a two-stage routing scheme where a simple distributed multipath finding algorithm is firstly performed to guarantee loop-free routing, and then a distributed routing algorithm is executed for energy-efficient routing in each node among the multiple loop-free paths. We conduct extensive experiments on the NS3 simulator and simulations with real network topologies in different scales under different traffic scenarios. Experiment results show that HDEER can reduce network energy consumption with a fair tradeoff between network energy consumption and traffic delay.

Existing Data Center Network (DCN) architectures are classified into two categories: switch-centric and server-centric architectures. In switch-centric DCNs, routing intelligence is placed on switches, each server usually uses only one port of the Network Interface Card (NIC) to connect to the network. In server-centric DCNs, switches are only used as cross-bars, and routing intelligence is placed on servers, where multiple NIC ports may be used. In this paper, we formally introduce a new category of DCN architectures: the dual-centric DCN architectures, where routing intelligence can be placed on both switches and servers. We propose two typical dual-centric DCN architectures: FSquare and Rectangle, both of which are based on the folded Clos topology. FSquare is a high performance DCN architecture, in which the diameter is small and the bisection bandwidth is large, however, the DCN power consumption per server in FSquare is high. Rectangle significantly reduces the DCN power consumption per server, compared to FSquare, at the sacrifice of some performances, thus, Rectangle has a larger diameter and a smaller bisection bandwidth. By investigating FSquare and Rectangle, and by comparing them with existing architectures, we demonstrate that, these two novel dual-centric architectures enjoy the advantages of both switch-centric designs and server-centric designs, have various nice properties for practical data centers, and provide flexible choices in designing DCN architectures.

With the rapid development of software defined networking and network function virtualization, researchers have proposed a new cloud networking model called Network-as-a-Service (NaaS) which enables both in-network packet processing and application-specific network control. In this paper, we revisit the problem of achieving network energy efficiency in data centers and identify some new optimization challenges under the NaaS model. Particularly, we extend the energy-efficient routing optimization from single-resource to multi-resource settings. We characterize the problem through a detailed model and provide a formal problem definition. Due to the high complexity of direct solutions, we propose a greedy routing scheme to approximate the optimum, where flows are selected progressively to exhaust residual capacities of active nodes, and routing paths are assigned based on the distributions of both node residual capacities and flow demands. By leveraging the structural regularity of data center networks, we also provide a fast topology-aware heuristic method based on hierarchically solving a series of vector bin packing instances. Extensive simulations show that the proposed routing scheme can achieve significant gain on energy savings and the topology-aware heuristic can produce comparably good results while reducing the computation time to a large extent.

The power consumption of enormous network devices in data centers has emerged as a big concern to data center operators. Despite many traffic-engineering-based solutions, very little attention has been paid on performance-guaranteed energy saving schemes. In this paper, we propose a novel energy-saving model for data center networks by scheduling and routing "deadline-constrained flows" where the transmission of every flow has to be accomplished before a rigorous deadline, being the most critical requirement in production data center networks. Based on speed scaling and power-down energy saving strategies for network devices, we aim to explore the most energy efficient way of scheduling and routing flows on the network, as well as determining the transmission speed for every flow. We consider two general versions of the problem. For the version of only flow scheduling where routes of flows are pre-given, we show that it can be solved polynomially and we develop an optimal combinatorial algorithm for it. For the version of joint flow scheduling and routing, we prove that it is strongly NP-hard and cannot have a Fully Polynomial-Time Approximation Scheme (FPTAS) unless P=NP. Based on a relaxation and randomized rounding technique, we provide an efficient approximation algorithm which can guarantee a provable performance ratio with respect to a polynomial of the total number of flows.

We study the energy minimization problem (EMP) in the optical WDM networks with arbitrary topologies. It is assumed that the traffic requests can arrive at and depart from the network arbitrarily, and idle network devices can be dynamically switched off to save energy. For each traffic request R, we need to specify a wavelength λRand a fiber in each link along its path to carry λR. The objective is to minimize the energy consumption incurred by the active devices over the entire network for any time period [0, t]. In this paper, a randomized online algorithm is proposed for EMP. Particularly, for each traffic request, our algorithm only needs O(1)-time to determine the wavelength, and the fiber allocation procedure can be performed in a fully distributed manner in each link with polynomial time. The competitive ratio of our algorithm is bounded by O(log μ · log hmax), where μ represents the number of wavelengths carried by each fiber and hmaxrepresents the holding time of the longest traffic request.

The increasing amount of web services over the Internet enable users composing them to satisfy the users'needs efficiently. Such service composing is prone to errors. Automatically detecting incompatible web services interaction and correcting them will largely improve users' experience on service composing. When correcting the errors, two major issues need to be addressed: First, how to satisfy diverse correction requirements of different users, Second, how to find the corrections efficiently. This paper proposes an approach to discovering maximum diversity corrections to reduce the risk of unsatisfying different end users' needs when presenting correction plans to them. To solve the problem efficiently, this paper proposes an approximate algorithm to find diverse correction plans. Furthermore, two pruning strategies are adopted to reduce the runtime of the algorithm. Experiments illustrate that our approach outperforms the baseline on the diversity of correction plans, and the two pruning strategies reduce the runtime significantly.

Two important components that consume the majority of IT power in data centers are the servers and the Data Center Network (DCN). Existing works fail to fully utilize power management techniques on the servers and in the DCN at the same time. In this paper, we jointly consider VM placement on servers with scalable frequencies and flow scheduling in the DCN, to minimize the overall system's power consumption. Due to the convex relation between a server's power consumption and its operating frequency, we prove that, given the number of servers to be used, computation workloads should be allocated to severs in a balanced way, to minimize the power consumption on servers. To reduce the power consumption of the DCN, we further consider the flow requirements among the VMs during VM allocation and assignment. Also, after VM placement, flow consolidation is conducted to reduce the number of active switches and ports. We notice that, choosing the minimum number of servers to accommodate the VMs may result in high power consumption on servers, due to servers' increased operating frequencies. Choosing the optimal number of servers purely based on servers' power consumption leads to reduced power consumption on servers, but may increase power consumption of the DCN. We propose to choose the optimal number of servers to be used, based on the overall system's power consumption. Simulations show that, our joint power optimization method helps to reduce the overall power consumption significantly, and outperforms various existing state-of-the-art methods in terms of reducing the overall system's power consumption.

The rapid growth of Internet services has brought emergent concerns over network energy efficiency. This study aims to improve network energy efficiency using power-down technique. We propose DEER, a fully distributed routing scheme. The main concept of DEER is to dynamically allocate the traffic demands in the nodes so that some links connected to the nodes can be put into sleep mode, thus reducing the energy consumption. The special features of DEER include that it does not need global traffic matrix of the network and that it uses only the local information of link loads, making DEER be able to be implemented in a distributed manner without centralized control. We develop algorithms in DEER to dynamically change the link state (into active or sleep mode) according to link utilization and to balance the loads of links by adjusting the link weights. With the traffic load varying over time, the link state transformation is triggered when any of the pre-defined thresholds is violated. Extensive simulations with the network topology and real traffic traces from the GÉANT network confirm that by involving DEER, up to 50% of the links can be put into sleep while the frequency of chaining the state of a link stays fairly low.

The popularization of cloud computing has raised concerns over the energy consumption that takes place in data centers. In addition to the energy consumed by servers, the energy consumed by large numbers of network devices emerges as a significant problem. Existing work on energy-efficient data center networking primarily focuses on traffic engineering, which is usually adapted from traditional networks. We propose a new framework to embrace the new opportunities brought by combining some special features of data centers with traffic engineering. Based on this framework, we characterize the problem of achieving energy efficiency with a time-aware model, and we prove its NP-hardness with a solution that has two steps. First, we solve the problem of assigning virtual machines (VM) to servers to reduce the amount of traffic and to generate favorable conditions for traffic engineering. The solution reached for this problem is based on three essential principles that we propose. Second, we reduce the number of active switches and balance traffic flows, depending on the relation between power consumption and routing, to achieve energy conservation. Experimental results confirm that, by using this framework, we can achieve up to 50 percent energy savings. We also provide a comprehensive discussion on the scalability and practicability of the framework.

With the proliferation of Web services, service engineers demand automatic service composition algorithms that not only synthesize the correct service compositions from thousands of services but also satisfy the quality requirements of users. This is known as QoS-aware automatic service composition problem. Our observation is that current research of only finding the optimal service composition result has several shortcomings. Users have to utilize the optimal one, which will make it rigid, and consequently bring about problems, such as overload of “hot services” and lack of choices for users. To cope with these problems, a top k query mechanism is introduced in this paper, and a progressive and incremental Key-Path-Based Loose (KPL) algorithm with 100 percent accuracy is proposed. Our QSynth, which won the performance championship of Web Service Challenge 2009 and 2010, is extended to support top k query based on KPL algorithm. Evaluations show that, compared to the state of the art, KPL algorithm achieves superior scalability and accuracy with respect to a large variety of composition scenarios. Moreover, we generalize a new graph problem: top k DAGs (Directed Acyclic Graphs) problem based on the above work. Applications of this new graph problem contain API recommender, supply chain, and so on. KPL algorithm illustrated in this paper can address them efficiently, too.

Virtual machines (VMs) consolidation has emerged as an important method for the design of energy-efficient data centers. The purpose is to aggregate VMs to fewer physical machines and put the idle servers into power-saving mode. Existing researches mainly focus on transforming the VMs consolidation into various bin packing problems. However, VMs consolidation may cost Service Level Agreement (SLA) violations just after the migration due to the uncertainty of applications' demands. In this paper, we provide a SLA risk management framework, involving a stochastic program to solve the resource allocation for VMs and an algorithm for dynamic VMs consolidation at runtime, to optimize both the energy consumption saving and SLA violations. We validate the proposed algorithm using workloads from a real world system. The results compare with other VMs consolidation algorithms that without considering risk, and show that our SLA violations is reduced by four times from 25% to 2% - 5% while only losing little energy consumption saving.

Apart from servers, the energy consumed by enormous amount of network devices in data centers also emerges as a big problem. Existing work on energy- efficient data center networking primarily focuses on traffic engineering to consolidate flows and shut down unused devices, not considering another important factor, virtual machine assignment, which has been shown to have a big influence on traffic engineering. Moreover, the lack of information about upper layer applications leads to misunderstand the traffic patterns of the network. This may result in poor effectiveness in the traffic-based optimization in practice. In this paper, we aim to achieve better network energy efficiency in MapReduce systems by combining virtual machine assignment and traffic engineering. By exploiting the characteristics of MapReduce applications, we provide a unified model to describe this problem. Due to its NP-hardness, a general framework is proposed to solve it, where virtual machines are first clustered and then different virtual machine assignments are generated greedily and a local search procedure is used to improve them. The local search procedure depends on the results of an energy-efficient routing provided by GEERA. GEERA is an approximate algorithm designed to select routing paths for flows. Experimental results confirm the efficiency of GEERA, as well as the overall framework. By using this framework, up to $20\%$ more energy savings can be achieved compared with sole traffic engineering solutions.

Energy efficiency is becoming an important issue in networks. Although some research works have been devoted to this topic, only a little attention has been paid to the stability of the network equipped with the energy conservation mechanisms. In fact, we find that the stability of networks can be undermined in the worst case if it isn't considered with care by the energy conservation mechanism.In this paper, we propose an energy-efficient scheduling protocol which can guarantee the stability of the network in all cases. We start by building a new model which can be used to verify the stability of the network equipped with the energy conservation mechanisms. With this model, we transform the packet scheduling problem to a Job Shop Scheduling problem. For this problem, we propose a time-stamp based work-conserving scheduling algorithm - G-FSA. Compared with existing methods, this scheduling algorithm guarantees a tighter bound on the make span of the jobs. Then, we integrate G-FSA with a time partition approach to generate our energy-efficient packet scheduling protocol. It is proved that the obtained protocol can guarantee the stability of network in all cases. And its approximation ratio in terms of energy efficiency can be bounded by O((1+∈ )α) for any ∈ > 0, where is an input parameter depending on the hardware infrastructure. Typically, 1 <; α ≤ 3.

Despite some proposals for energy-efficient topologies, most of the studies for saving energy in data center networks are focused on traffic engineering, i.e., consolidating flows and switching off unnecessary network devices. The major weakness of this approach is network oscillation brought by the frequent change of network topology when traffic fluctuates very fast. In this paper, we propose to incorporate rate adaptation into green data center networks. With rate adaptive network devices, we aim at approaching network-wide energy proportionality by routing optimization. We formalize the problem with an integer program and propose an efficient approximation algorithm - TSRR, solving the problem quickly while guaranteeing a constant performance ratio. Extensive range of simulations confirm that more than 40% of the energy can be saved while introducing very slight stretch on network delay.

Deterministic replay is a key technique for debugging simultaneous multithreaded programs on multicore processor. With this scheme, software-only implementations generally incur large runtime overhead. Hardware assisted methods can significantly reduce the overhead, but most hardware based recorders are system oriented. They capture all orders happened in monitored application, Operating System, and other applications. This produces inefficiency and inconvenience for application programmers to debug their programs. This paper proposes a hardware assisted recorder (HRUL), which is lightweight and convenient to application programmers. HRUL uses a hybrid hardware-software method to extract dependencies from monitored application in a complex execution environment, and compresses the orders with a combination of online and offline compression algorithm. What' more, It also captures implicit dependencies caused by system call and scheduling in Operating System to make replay faithful. We evaluate the scheme with 16-core runs of PARSEC, our results show that HRUL introduces runtime overhead less than 3% and can reduce log size by 81% (only with online-hardware compression).

GPUs provide powerful computing ability especially for data parallel algorithms. However, the complexity of the GPU system makes the optimization of even a simple algorithm difficult. Different parallel algorithms or optimization methods on a GPU often lead to very different performances. The matrix-vector multiplication routine for general dense matrices (GEMV) is a building block for many scientific and engineering computations. We find that the implementations of GEMV in CUBLAS 4.0 or MAGMA are not efficient, especially for small matrix or fat matrix (a matrix with small number of rows and large number of columns). In this paper, we propose two new algorithms to optimize GEMV on Fermi GPU. Instead of using only one thread, we use a warp to compute an element of vector y. We also propose a novel register blocking method to accelerate GEMV on GPU further. The proposed optimization methods for GEMV are comprehensively evaluated on the matrices with different sizes. Experiment results show that the new methods can achieve over 10x speedup for small square matrices and fat matrices compared to CUBLAS 4.0 or MAGMA, and the new register blocking method can also perform better than CUBLAS 4.0 or MAGMA for large square matrices. We also propose a performance-tuning framework on how to choose an optimal algorithm of GEMV for an arbitrary input matrix on GPU.

Current QoS-aware automatic service composition queries over a network of Web services are often one-time innature. After a network of Web services is built, such queries are issued once, and answers are found from the scratch. The underlying assumption is that the participating Web services are rather static so that their functional and non-functional parameters seldom change. However, such an assumption is often baseless. New services come and go, service APIs change gradually, and QoS values fluctuate. Therefore, a support for efficiently handling "continuous" service composition queries is desired. In this paper, we propose an event driven continuous query algorithm for QoS-aware automatic service composition problem to cope with different types of dynamic services. Moreover, we integrated this algorithm in our service composition system, QSynth. Finally, we evaluate our proposal using both real QoS data and synthetic Web service data and show the superior performance of ours, compared to the state-of-the art solution which won the performance championship of Web Service Challenge in 2009 and 2010.

It is an important task to tune performance for sparse matrix vector multiplication (SpMV), but it is also a difficult task because of its irregularity. In this paper, we propose a cache blocking method to improve the performance of SpMV on the emerging GPU architecture. The sparse matrix is partitioned into many sub-blocks, which are stored in CSR format. With the blocking method, the corresponding part of vector x can be reused in the GPU cache, so the time spent on accessing the global memory for vector x is reduced heavily. Experimental results on GeForce GTX 480 show that SpMV kernel with the cache blocking method is 5x faster than the unblocked CSR kernel in the best case.

BACKGROUND: Three-dimensional (3D) reconstruction in electron tomography (ET) has emerged as a leading technique to elucidate the molecular structures of complex biological specimens. Blob-based iterative methods are advantageous reconstruction methods for 3D reconstruction in ET, but demand huge computational costs. Multiple graphic processing units (multi-GPUs) offer an affordable platform to meet these demands. However, a synchronous communication scheme between multi-GPUs leads to idle GPU time, and a weighted matrix involved in iterative methods cannot be loaded into GPUs especially for large images due to the limited available memory of GPUs. RESULTS: In this paper we propose a multilevel parallel strategy combined with an asynchronous communication scheme and a blob-ELLR data structure to efficiently perform blob-based iterative reconstructions on multi-GPUs. The asynchronous communication scheme is used to minimize the idle GPU time so as to asynchronously overlap communications with computations. The blob-ELLR data structure only needs nearly 1/16 of the storage space in comparison with ELLPACK-R (ELLR) data structure and yields significant acceleration. CONCLUSIONS: Experimental results indicate that the multilevel parallel scheme combined with the asynchronous communication scheme and the blob-ELLR data structure allows efficient implementations of 3D reconstruction in ET on multi-GPUs.

Accurate alignment of electron tomographic images without using embedded gold particles as fiducial markers is still a challenge. Here we propose a new markerless alignment method that employs Scale Invariant Feature Transform features (SIFT) as virtual markers. It differs from other types of feature in a way the sufficient and distinctive information it represents. This characteristic makes the following feature matching and tracking steps automatic and more reliable, which allows for estimating alignment parameters accurately. Furthermore, we use Sparse Bundle Adjustment (SPA) with M-estimation to estimate alignment parameters for each image. Experiments show that our method can achieve a reprojection residual less than 0.4 pixel and can approach the same accuracy of marker alignment. Besides, our method can apply to adjusting typical misalignments such as magnitude divergences or in-plane rotation and can detect bad images.

A cloud computing provider can dynamically allocate virtual machines (VM) based on the needs of the customers, while maintaining the privileged access to the Management Virtual Machine that directly manages the hardware and supports the guest VMs. The customers must trust the cloud providers to protect the confidentiality and integrity of their applications and data. However, as the VMs from different customers are running on the same host, an attack to the management virtual machine will easily lead to the compromise of the guest VMs. Therefore, it is critical for a cloud computing system to ensure the trustworthiness of management VMs. To this end, we propose VMGuard, an integrity monitoring and detecting system for management virtual machines in a distributed environment. VMGuard utilizes a special VM, Guard Domain, which runs on each physical node to monitor the co-resident management VMs. The integrity measurements collected by the Guard Domains are sent to the VMGuard server for safe store and independent analysis. The experimental evaluation of a Xen-based prototype shows that VMGuard can quickly detect the root kit attacks while the performance overhead is low.

With the proliferation of Web services, service engineers demand good automatic service composition algorithms that not only synthesize the correct work plans from thousands of services but also satisfy the quality requirements of the users. Our observation is that conventional approaches suffer from serious limitations in scalability and accuracy when addressing both requirements simultaneously. We have designed and implemented a tool QSynth to use QoS objectives of service requests as the search directives. This approach effectively prunes the search space and significantly improves the accuracy of the search results. Evaluations show that, compared to the state of the art, QSynth achieves superior scalability and accuracy with respect to a large variety of composition scenarios. Our design of QSynth won the performance championship of Web Services Challenge 2009.

A simple yet common scheduling problem is identified, as a special case of the R||Cmaxproblem. We name it Linear Makespan Minimization on Unrelated Parallel Machines (LMMUPM). A novel algorithm, MOBSA (Multi-Objective Based Scheduling Algorithm), is presented to solve it. Two auxiliary problems are introduced as the basis of our algorithm. The first one can be reduced to a Multi-Objective Integer Program, while the second is constructed based on the solution of the first one. Results on random datasets revealed that MOBSA produced smaller and more stable makespans than other scheduling algorithms. Additionally, the makespan produced by MOBSA was within 1% of the optimum for every case. Presently, MOBSA has been applied to parallelize EMAN, one of the most popular software packages for cryo-electron microscopy single particle reconstruction. High speedups and ideal load balancing have been obtained. It is expected that MOBSA is also applicable to other similar applications.

Three-dimensional reconstruction of cryo-electron tomography (cryo-ET) has emerged as the leading technique in analyzing structures of complex pleomorphic cellulars. A classical iterative method, simultaneous algebraic reconstruction technique (SART), has been employed to reconstruct volume images in cryo-ET. However, SART starts with an arbitrary approximation and takes into account only a weighted factor when updating density value in every error-correction iterative procedure, thus limits the improvement of the reconstruction resolution. Facing these problems, we present a modified simultaneous algebraic reconstruction technique (MSART) which applies several key techniques, a back projection technique (BPT) and an adaptive adjustment of corrections. Experimental results show that MSART can improve significantly the quality of reconstruction. Additionally, in order to address the computational requirements demanded by the reconstruction of large volumes, we have presented and implanted a strategy to parallel the MSART algorithm on DAWNING 4000H cluster system, and obtained a good computational performance.

On-chip many core architecture is an emerging and promising computation platform. High speed on-chip communication and abundant chipped resources are two outstanding advantages of this architecture, which provide an opportunity to implement efficient synchronization scheme. The practical execution efficiency of synchronization scheme is critical to this platform. However, there are few researches on systematic evaluation method of choice synchronization schemes for on-chip many core processors, and effect of dedicated hardware support in this context. So we focus on the evaluation method and criterion of synchronization scheme on the platform. Firstly, we present several criterions proper to on-chip many core architecture, that is, absolute overhead of synchronization operation, the transferring time between different synchronization operations, overhead caused by load imbalance, and the network congestion caused by synchronization operation. Secondly, we illustrate how to design microbenchmarks which one dedicated to evaluate a performance criterion respectively. Finally, we implement these microbenchmarks and synchronization schemes on an on-chip many core processor with shared level-two cache and AMD Opteron commercial chip multi-processor, respectively. And we analyze effect of dedicated hardware support. Results show that the most overhead of synchronization is caused by load imbalance and serialization on synchronization point. It also shows that synchronization scheme supported with dedicated hardware can improve its performance obviously for chipped many-core processor.

MOTIVATION: EMAN is one of the most popular software packages for single particle reconstruction. But the particle clusters produced during its model refining stage are of low qualities. We attempt to refine the particle clusters by more accurately determining orientations of particles, and thereby achieving higher resolutions of consequent 3D structures. RESULTS: A particle reclustering framework (PRF) is introduced, which consists of three components. Each of them is responsible for one of the basic tasks of PRF: normalization, threshold determination and reclustering. Our implementation is also described and proved to meet the constraints proposed by PRF. Experiments revealed that our implementation improved resolutions of consequent structures for most cases, but only a little extra execution time was incurred. Therefore, it is practical to incorporate PRF in EMAN to improve qualities of generated 3D structures. AVAILABILITY AND IMPLEMENTATION: Implementation of our algorithm is available upon request from the authors.

In this paper, we presented a method to improve structural modeling based on conserved domain clusters and structure-anchored alignment. First we mapped all the InterPro domains in the entire PDB, partitioned and clustered homologous domains into the domain-based template library. This aimed at expanding structural coverage to more protein sequences. For each cluster, we generated a multiple structural alignment based only on the 3 D information. Then we extracted a core-structure and built a position-specific profile from the structure and sequence information for each of cluster. Based on the multiple structural alignments, core-structures and the profiles, we developed a structure-anchored alignment method to increase the alignment accuracy between a query and its templates. Preliminary results show that our template library and the structure-anchored alignment method can be used for the prediction for a majority of known protein sequences with better qualities.

Aiming at the two main shortcomings in Homology Modeling, we have designed and established a domain clustering database. Searching the database is a fundamental work for it. However, current alignment algorithms are mainly based on the sequences, ignoring the structure conservation in domain. This paper proposed a profile-based alignment which considers the structure information into the profile, based on the character of our domain database. We designed an experiment within the database. The results show that both the quality and sensitivity of our scheme are better than pure Smith-Waterman and sequence-based profile algorithms. We strongly believe that this work can help to improve the protein structure prediction

Recently, large-scale protein-protein interactions were recovered using the similar two-hybrid system for the model systems. This information allows us to investigate the protein interaction network from a systematic point of view. However, experimentally determined interactions are susceptible to errors. A previous assessment estimated that only ~10% of the interactions can be supported by more than one independent experiment, and about half of the interactions may be false positives. These false positives might unnecessarily link unrelated proteins, resulting in huge apparent interaction clusters, which complicate elucidation for the biological importance of these interactions. Address this problem, we present an approach to integrate, assess and characterize all available protein-protein interactions in model organisms yeast and fly. We first integrate all available protein-protein interaction databases of yeast and fly, and merge all the datasets. We then use machine learning techniques to score the reliability for each interaction, and to rigorously validate the scoring scheme of yeast protein-protein interactions from different aspects. Our results show that this scoring scheme provides a good basis for selecting reliable protein-protein interaction dataset

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability —will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n -node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n ). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

In this paper we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic adversarial model of packet generation and path determination for which the time-averaged injection rate of packets requiring the use of any edge is limited to be less than 1. A crucial issue that arises in such a setting is that of stability-will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly-used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size. Our results resolve several questions posed by Borodin et al. and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.