MOTIVATION: Protein sequence database search and multiple sequence alignment generation is a fundamental task in many bioinformatics analyses. As the data volume of sequences continues to grow rapidly, there is an increasing need for efficient and scalable multiple sequence query algorithms for super-large databases without expensive time and computational costs. RESULTS: We introduce Chorus, a novel protein sequence query system that leverages parallel model and heterogeneous computation architecture to enable users to query thousands of protein sequences concurrently against large protein databases on a desktop workstation. Chorus achieves over 100× speedup over BLASTP without sacrificing sensitivity. We demonstrate the utility of Chorus through a case study of analyzing a ∼1.5-TB large-scale metagenomic datasets for novel CRISPR-Cas protein discovery within 30 min. AVAILABILITY AND IMPLEMENTATION: Chorus is open-source and its code repository is available at https://github.com/Bio-Acc/Chorus.

Semi-supervised node classification in graphs is a key problem in machine learning, and graph neural networks (GNNs) currently achieve state-of-the-art performance. However, traditional GNNs fail to make use of a substantial amount of information available in a graph. For example, the training loss is often defined only with respect to labeled training nodes, which usually make up a small proportion of the graph. Also, most graphs exhibit a certain degree of homophily, in which neighboring nodes are likely to belong to the same class, but GNNs typically do not make use of this property in an explicit way. In this work, we introduce a new type of consistency regularization which is able to make use of data from unlabeled nodes and also exploits graph homophily in a novel and more accurate way. Additionally, we observe that nodes in a graph may exhibit different amounts of homophily, so that uniformly enforcing neighbor consistency regularization across all nodes can reduce accuracy. We thus introduce a second clustering based regularization targeting low homophily nodes which lack reliable information from their neighbors. We show that we can flexibly combine the two regularizations with existing GNN backbones, and then demonstrate the effectiveness of the combined method by achieving state-of-the-art accuracy on a number of datasets.

Achieving high performance in many multi-server systems (e.g., web hosting center, cloud) requires finding a good assignment of worker threads to servers and also effectively allocating each server’s resources to its assigned threads. The assignment and allocation components of this problem have been studied extensively but largely separately in the literature. In this paper, we introduce theassign and allocate (AA)problem, which seeks to simultaneously find an assignment and allocation that maximizes the total utility of the threads. Assigning and allocating the threads together can result in substantially better overall utility than performing the steps separately, as is traditionally done. We model each thread by a utility function giving its performance as a function of its assigned resources. We first prove that the AA problem is NP-hard. We then present a$2 (\sqrt {2}-1) > 0.828$factor approximation algorithm for concave utility functions, which runs in$O(mn^{2} + n (\log mC)^{2})$time for$n$threads and$m$servers with$C$amount of resources each. We also give a faster algorithm with the same approximation ratio and$O(n (\log mC)^{2})$time complexity. We then extend the problem to two more general settings. First, we consider threads with nonconcave utility functions, and give a 1/2 factor approximation algorithm. Next, we give an algorithm for threads using multiple types of resources, and show the algorithm achieves good empirical performance. We conduct extensive experiments to test the performance of our algorithms on threads with both synthetic and realistic utility functions, and find that they achieve over 92% of the optimal utility on average. We also compare our algorithms with a number of practical heuristics, and find that our algorithms achieve up to 9 times higher total utility.

Fluid simulations are often performed using the incompressible Navier-Stokes equations (INSE), leading to sparse linear systems which are difficult to solve efficiently in parallel. Recently, kinetic methods based on the adaptive-central-moment multiple-relaxation-time (ACM-MRT) model [1], [2] have demonstrated impressive capabilities to simulate both laminar and turbulent flows, with quality matching or surpassing that of state-of-the-art INSE solvers. Furthermore, due to its local formulation, this method presents the opportunity for highly scalable implementations on parallel systems such as GPUs. However, an efficient ACM-MRT-based kinetic solver needs to overcome a number of computational challenges, especially when dealing with complex solids inside the fluid domain. In this article, we present multiple novel GPU optimization techniques to efficiently implement high-quality ACM-MRT-based kinetic fluid simulations in domains containing complex solids. Our techniques include a new communication-efficient data layout, a load-balanced immersed-boundary method, a multi-kernel launch method using a simplified formulation of ACM-MRT calculations to enable greater parallelism, and the integration of these techniques into a parametric cost model to enable automated prameter search to achieve optimal execution performance. We also extended our method to multi-GPU systems to enable large-scale simulations. To demonstrate the state-of-the-art performance and high visual quality of our solver, we present extensive experimental results and comparisons to other solvers.

Search trees are one of the most important and widely used data structures, and parallelization is an effective method to improve their performance. However, many existing parallel search trees incur high synchronization costs and low memory I/O efficiency, which limits their performance. We propose PPBT, a batched parallel search tree which minimizes synchronization by partitioning the tree using novel algorithms and minimizing I/O cost using buffering. We give a new sequential algorithm for batch processing on search trees with optimal I/O efficiency for insert and delete operations, and also present a fast parallel algorithm for joining disjoint search trees. We show experimentally that PPBT is over 6×faster than the state-of-the-art parallel tree in [1] and over 40× faster than the concurrent search tree in [7], and achieves 21×speedup using 32 threads. PPBT's throughput on searches is lower due to reduced opportunities for buffering, but is still 1.3 × that of [1]. In addition, PPBT has good response times for searches, for example completing 100K searches in under 1 ms in a tree with 10M elements.

Data centers have experienced dramatic growth in recent years in order to meet the ever-increasing demand for computing. As a result, minimizing the electrical cost to operate data centers has become a crucial issue. In this paper, we observe that electricity prices change over time, and that we can take advantage of periods with low prices by scaling up processor speeds to perform more work, while scaling down speeds during high price periods to reduce cost. We apply this observation to several settings. First, we consider an offline setting which assumes future electricity prices are given, and propose an efficient algorithm for optimally scaling a processor's speed in order to minimize the total electrical cost for completing a task by a deadline. We then consider a more realistic stochastic setting in which future prices are not known, but vary according to a Markov model. We present another efficient algorithm for minimizing the expected cost to meet a deadline. We performed a number of experiments using real electricity price traces to test the performance of our algorithms. We show that our stochastic algorithm is light-weight and relies only on easily obtainable price data, but that it achieves excellent performance, with only a 1 percent cost difference on average from the optimal offline algorithm. In addition, the stochastic algorithm significantly reduced costs compared to several candidate algorithms.

Datacenters have experienced dramatic growth in recent years, and the cost for powering them has become a significant problem. This paper proposes methods to minimize the energy cost for performing a task on a datacenter server before a deadline. We observe that energy prices fluctuate over time, and schedule the task to execute in periods of relatively low cost, despite not having knowledge of future costs during the execution. This problem is studied in several models, starting with an online setting where electricity prices can change arbitrarily. A$\sqrt{\varphi }$-competitive algorithm is proposed, where$\varphi$is the ratio between the maximum and minimum electricity prices, and this algorithm is also shown to be optimal by proving a matching lower bound. Next, we consider a stochastic setting in which prices vary in a Markovian fashion and propose an optimal algorithm based on dynamic programming. We then study the performance of our algorithms in practice using prices derived from real world data. The results show that the stochastic algorithm is very effective, and achieves cost that is within 3.4 percent of the optimum. Moreover, it performs well compared to several heuristics used in practice.

Graph coloring is an important problem in computer science and engineering with numerous applications. As the size of data increases today, graphs with millions of nodes are becoming commonplace. Parallel graph coloring algorithms on high throughput graphics processing units (G PU s) have recently been proposed to color such large graphs efficiently. We present two new graph coloring algorithms for GPUs which improve upon existing algorithms both in coloring speed and quality. The first algorithm, counting-based Iones-Plassmann (CJP), uses counters to implement the classic Jones-Plassmann parallel coloring heuristic in a work-efficient manner. The second algorithm, conflict coloring (CC) achieves higher parallelism than CJP, and is based on optimistically coloring the graph using estimates of the chromatic number. We compared CC and CJP with two state-of-the-art GPU coloring algorithms, csrcolor [1] and Deveci et al's [2] vertex/edge-based algorithms (which we call VEB), as well as the sequential CPU algorithm ColPack [3]. In terms of coloring quality, CJP and CC are both far better than csrcolor, while CJP uses 10% fewer colors than VEB on average and CC uses 10% more. Compared to ColPack, CJP and CC use 1.3× and 1.5× more colors on nonbipartite graphs, resp. In terms of speed, CJP is on average 1.5–2× faster than the other algorithms, while CC is 2.7–4.3× faster.

The container stowage planning problem is known to be NP-hard and heuristic algorithms have been proposed. Conventionally, the efficiency of the stowage planning algorithms are improved by pruning or reducing the search space. We observe that constraint evaluation is the core of most algorithms. In addition, the order at which the constraints are evaluated can have significant impact on the efficiency of the constraint evaluation engine. We propose random sample model (RSM) and sequential sample model (SSM) for analysis of the problem. We present and evaluate seven strategies in optimizing the constraint evaluation engine. We show how to achieve the optimal constraint ordering with respect to RSM and SSM, respectively. However, the optimal ordering for SSM requires perfect information about the states of the constraint tests, which is impractical. We present an alternative strategy and show empirically that its efficiency is close to the optimal. Experiments show that, compared to a naïve ordering, an average of 2.74 times speed up in the evaluation engine can be achieved.Note to Practitioners—Automated stowage planning has become a trend as the number of mega-scale containerships being deployed has increased drastically over the past decade. Due to the nature of the problem, it is impractical to expect the best stowage plan within a limited amount of time, and hence, many heuristics have been devised to reduce the solution space. Many heuristics algorithms share a common core-repeatedly selecting a stowage slot and a container (selection mechanism) and evaluate whether all of the constraints are satisfied. To improve the efficiency, most studies aim to reduce the number of location-container pairs being considered. We consider an alternative approach that improves the efficiency of the constraint evaluation engine. Specifically, we show how to improve the efficiency by strategically reordering the sequence in which the constraints are evaluated. With the improvements on the efficiency, the stowage algorithm is one step closer to being able to generate solutions in real time. This may enable the shipping companies to take last-minute shipment order and react to changes in demands quickly.

Summary Energy efficiency of data analysis systems has become a very important issue in recent times because of the increasing costs of data center operations. Although distributed streaming workloads have increasingly been present in modern data centers, energy‐efficient scheduling of such applications remains as a significant challenge. In this paper, we conduct an energy consumption analysis of data stream processing systems in order to identify their energy consumption patterns. We follow stream system benchmarking approach to solve this issue. Specifically, we implement Linear Road benchmark on six stream processing environments (S4, Storm, ActiveMQ, Esper, Kafka, and Spark Streaming) and characterize these systems' performance on a real‐world data center. We study the energy consumption characteristics of each system with varying number of roads as well as with different types of component layouts. We also use a microbenchmark to capture raw energy consumption characteristics. We observed that S4, Esper, and Spark Streaming environments had highest average energy consumption efficiencies compared with the other systems. Using a neural networkbased technique with the power/performance information gathered from our experiments, we developed a model for the power consumption behavior of a streaming environment. We observed that energy‐efficient execution of streaming application cannot be specifically attributed to the system CPU usage. We observed that communication between compute nodes with moderate tuple sizes and scheduling plans with balanced system overhead produces better power consumption behaviors in the context of data stream processing systems. Copyright © 2016 John Wiley & Sons, Ltd.

Video streaming is one of the most widely used mobile applications today, and it also accounts for a large fraction of mobile battery usage. Much of the energy consumption is for wireless data transmission and is highly correlated to network bandwidth conditions. In periods of poor connectivity, up to 90% of mobile energy can be used for wireless data transfer. In this article, we study the problem of energy-efficient mobile video streaming. We make use of the observed correlation between bandwidth and user location , and also observe that a user’s location is predictable in many situations, such as when commuting to a known destination. Based on the user’s predicted locations and bandwidth conditions, we optimize wireless transmission times to achieve high quality video playback while minimizing energy use. We propose an optimal offline algorithm for this problem, which runs in O ( Tk ) time, where T is the duration of the video and k is the size of the video buffer. We also propose LAWS, a Location AWare Streaming algorithm. LAWS learns from historical location-aware bandwidth conditions and predicts future bandwidths along a planned route to make online wireless download decisions. We evaluate LAWS using real bandwidth traces, and show that LAWS closely approximates the performance of the optimal offline algorithm, achieving 90.6% of the optimal performance on average, and 97% in certain cases. LAWS also outperforms three popular strategies used in practice by, on average, 69%, 63%, and 38%, respectively. Lastly, we show that LAWS is able to deal with noisy data and can attain the stated performance after sampling bandwidth conditions only five times.

General sparse matrix-matrix multiplication (SpGEMM) is a core component of many algorithms. A number of recent works have used high throughput graphics processing units (GPUs) to accelerate SpGEMM. However, exploiting the power of GPUs for SpGEMM requires addressing a number of challenges, including highly imbalanced workloads and large numbers of inefficient random global memory accesses. This paper presents a SpGEMM algorithm which uses several novel techniques to overcome these problems. We first propose two low cost methods to achieve perfect load balancing during the most expensive step in SpGEMM. Next, we show how to eliminate nearly all random global memory accesses using shared memory based hash tables. To optimize the performance of the hash tables, we propose a lightweight method to estimate the number of nonzeros in the output matrix. We compared our algorithm to the CUSP, CUSPARSE and the state-of-the-art BHSPARSE GPU SpGEMM algorithms, and show that it performs 5.6x, 2.4x and 1.5x better on average, and up to 11.8x, 9.5x and 2.5x better in the best case, respectively. Furthermore, we show that our algorithm performs especially well on highly imbalanced and unstructured matrices.

Achieving high performance in many distributed systems requires finding a good assignment of threads to servers as well as effectively allocating each server's resources to its assigned threads. The assignment and allocation components of this problem have both been studied extensively, but separately in the literature. In this paper, we introduce the assign and allocate (AA) problem, which seeks to simultaneously find an assignment and allocations that maximize the total utility of the threads. Assigning and allocating the threads together can result in substantially better overall utility than performing the steps separately, as is traditionally done. We model each thread by a concave utility function giving its throughput as a function of its assigned resources. We first show that the AA problem is NP-hard, even when there are only two servers. We then present a 2(√2-1) > 0.828 factor approximation algorithm, which runs in O(mn2 + n (log mC)2) time for n threads and m servers with C amount of resources each. We also present a faster algorithm with the same approximation ratio and O(n(log mC)2) running time. We conducted experiments to test the performance of our algorithm on threads with different types of utility functions, and found that it achieves over 99% of the optimal utility on average. We also compared our algorithm against several other assignment and allocation algorithms, and found that it achieves up to 5.7 times better total utility.

To achieve higher performance, cache sizes have been steadily increasing in computer processors and network systems. But caches are often over-provisioned for peak demand and underutilized in typical non-peak workloads. As caches consume substantial power, this results in significant amounts of wasted energy. To address this, existing works turn off parts of the cache when they do not contribute to higher performance. However, while these methods are effective empirically, they lack provable performance bounds. In addition, existing works focus on processor caches and are not applicable to network caches where data size and cost can vary. In this paper, we study the energy-aware caching (EAC) problem, and seek to minimize the total cost incurred due to cache misses and energy consumption. We propose three algorithms to solve different variants of this problem. The first is an optimal offline algorithm that runs in O(kn log n) time for a size k cache and n cache accesses. Then, we propose a simple online algorithm for uniform data size and cost that is $2 + {{h} \over {h-h+1}}$ competitive compared to an optimal algorithm with a size h ≤ k cache. Lastly, we propose a $2 + {{h-1} \over {h-h+1}}$ competitive online algorithm that allows arbitrary data sizes and costs. We give an efficient implementation of the algorithm that takes O(log k) amortized time per cache access, and also present an adaptive version that reacts to workload patterns to achieve better real-world performance. Using trace driven simulations, we show our algorithm has substantially lower cost than algorithms focused on maximizing cache hit rates or minimizing energy usage alone.

Sparse matrix-vector multiplication (Spiv) is an important kernel used in solving many scientific and engineering problems. The massive parallelism of graphics processing units (GPUs) makes them well suited for Spiv computations. However, fully utilizing the power of GPUs is challenging because Spiv makes a large number of scattered memory accesses which saturate the Gnu's memory bandwidth. Most previous works sought to address the bandwidth limitation by using efficient storage formats for the matrix. However, we show that for most matrices, a majority of the bandwidth is consumed by accesses to the vector. In this paper, we introduce two techniques to significantly decrease the I/O for vector accesses, by making novel use of the Gnu's fast shared memory. A key advantage of our vector optimizations is that they are complementary to existing matrix I/O optimizations, so that it is possible to use both techniques in conjunction. Furthermore, combining the optimizations requires only minor code changes. We demonstrate how to combine our techniques with the widely used CUSP Spiv algorithm and the currently highest performing yaSpMV algorithm to significantly improve both algorithms' performance. We experimented with a wide range of matrices, and show that the modified version of CUSP on average reduces vector I/O by 37% and reduces the total I/O by 31%, while the modified version of yaSpMV reduces the vector and total I/O by 36% and 31%, resp. We improve CUSP's total throughput by 14% on average and up to 77% for certain matrices, and improve yaSpMV's throughput by 12% on average and 35% for some matrices.

In-network processing is touted as a key technology to eliminate data redundancy and minimize data transmission, which are crucial to saving energy in wireless sensor networks (WSNs). Specifically, operators participating in in-network processing are mapped to nodes in a sensor network. They receive data from downstream operators, process them and route the output to either the upstream operator or the sink node. The objective of operator tree placement is to minimize the total energy consumed in performing in-network processing. Two types of placement algorithms, centralized and distributed, have been proposed. A problem with the centralized algorithm is that it does not scale to large WSN's, because each sensor node is required to know the complete topology of the network. A problem with the distributed algorithm is their high message complexity. In this paper, we propose a heuristic algorithm to place a treestructured operator graph, and present a distributed implementation to optimize in-network processing cost and reduce the communication overhead. We prove a tight upper bound on the minimum in-network processing cost, and show that the heuristic algorithm has better performance than a canonical greedy algorithm. Simulation-based evaluations demonstrate the superior performance of our heuristic algorithm. We also give an improved distributed implementation of our algorithm that has a message overhead of O(M) per node, which is much less than the O(√NM log2M) and O(√NM) complexities for two previously proposed algorithms, Sync and MCFA, respectively. Here, N is the number of network nodes and M is the size of the operator tree.

An effective way to reduce the number of aborts in software transactional memory (STM) is to keep multiple versions of transactional objects. In this paper, we study inherent properties of STMs that use multiple versions to guarantee successful commits of all read-only transactions.

We prove an Ω(n log n) lower bound on the number of non-busywaiting memory accesses by any deterministic algorithm solving n process mutual exclusion that communicates via shared registers. The cost of the algorithm is measured in the state change cost model, a variation of the cache coherent model. Our bound is tight in this model. We introduce a novel information theoretic proof technique. We first establish a lower bound on the information needed by processes to solve mutual exclusion. Then we relate the amount of information processes can acquire through shared memory accesses to the cost they incur. We believe our proof technique is flexible and intuitive, and may be applied to a variety of other problems and system models.

We introduce the distributed gradient clock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their hardware clocks and message exchanges, and the goal is to synchronize the nodes' logical clocks as closely as possible, while satisfying certain validity conditions. The new feature of gradient clock synchronization (GCS for short) is to require that the skew between any two nodes' logical clocks be bounded by a nondecreasing function of the uncertainty in message delay (call this the distance) between the two nodes. That is, we require nearby nodes to be closely synchronized, and allow faraway nodes to be more loosely synchronized. We contrast GCS with traditional clock synchronization, and discuss several practical motivations for GCS, mostly arising in sensor and ad hoc networks. Our main result is that the worst case clock skew between two nodes at distance d from each other is Ω(d + log D log log D), where D is the diameter1 of the network. This means that clock synchronization is not a local property, in the sense that the clock skew between two nodes depends not only on the distance between the nodes, but also on the size of the network. Our lower bound implies, for example, that the TDMA protocol with a fixed slot granularity will fail as the network grows, even if the maximum degree of each node stays constant.