BERT-like models have been widely adopted in text mining and web search due to their high accuracy. However, large BERT-like models suffer from inefficient online inference on GPUs for two main reasons. First, their high accuracy relies on large model depth, which linearly increases sequential computation on GPUs. Second, stochastic and dynamic online workloads lead to extra costs due to batching and padding. To address the problem, we present Student Parallelism for efficient GPU inference of BERT-like models under real-world online workloads. At its core, Student Parallelism adopts stacking distillation and boosting ensemble, distilling the original deep model into a group of shallow but virtually stacked student models running in parallel. This enables Student Parallelism to achieve a low model depth (e.g., two layers), and thus low inference latency while maintaining accuracy. In addition, we design adaptive student pruning to adjust the number of students according to the dynamic online workloads. For example, during workload bursts, it can temporarily decrease the number of students with minimal accuracy loss to improve system throughput. Extensive experiments on real-world datasets and workloads show that Student Parallelism achieves up to 4.1× lower latency while maintaining accuracy and up to 22.27× higher throughput during workload bursts.

Graph pooling technique in GNNs for learning expressive graph-level representation is critical yet still chal-lenging. Existing pooling methods either struggle to capture local substructures or fail to utilize high-order dependency, thus diminishing the expression capability. To solve this problem, we propose HAP, a hierarchical graph-level representation learning framework adaptively sensitive to graph structures. Specifically, HAP utilizes a novel cross-level attention mechanism MOA to naturally focus more on the close neighborhood while effectively capturing higher-order dependency. It also learns a global graph content GCont that extracts the graph pattern properties to stabilize the pre- and post-coarsening graph content, thus providing global guidance in graph coarsening. Experiments show that HAP significantly outperforms the state-of-the-art graph pooling methods.

Graph neural networks (GNN) have been proven to be mature enough for handling graph-structured data on node-level graph representation learning tasks. However, the graph pooling technique for learning expressive graph-level representation is critical yet still challenging. Existing pooling methods either struggle to capture the local substructure or fail to effectively utilize high-order dependency, thus diminishing the expression capability. In this paper we propose HAP, a hierarchical graph-level representation learning framework, which is adaptively sensitive to graph structures, i.e., HAP clusters local substructures incorporating with high-order dependencies. HAP utilizes a novel cross-level attention mechanism MOA to naturally focus more on close neighborhood while effectively capture higher-order dependency that may contain crucial information. It also learns a global graph content GCont that extracts the graph pattern properties to make the pre- and post-coarsening graph content maintain stable, thus providing global guidance in graph coarsening. This novel innovation also facilitates generalization across graphs with the same form of features. Extensive experiments on ten datasets show that HAP significantly outperforms twelve popular graph pooling methods on graph classification task with an maximum accuracy improvement of 20.18%, and exceeds the performance of state-of-the-art graph matching and graph similarity learning algorithms by over 3.42% and 16%.

Graph algorithms, such as Breadth First Search (BFS), Single Source Shortest Path (SSSP), PageRank (PR), and Connected Components (CC), are increasingly important in big data processing and analytics. As graph scales (numbers of vertices and edges) have increased from billions to trillions, Supercomputers have huge numbers (up to hundreds of thousands) of computing nodes (CNs) that can provide ultra-high aggregate computing power and memory capacity, thus being particularly suitable for processing extreme-scale graphs with trillions of vertices and edges. However, existing cluster-based graph-parallel systems perform poorly when deployed on supercomputers, since their partitioning methods overlook the hierarchical nature of supercomputer networks and incur prohibitive communication storm. This paper presents XTree, an efficient traversal-based partitioning method for minimizing communication overhead of graph processing on supercomputers. We observe that supercomputers' huge numbers of CNs are usually organized into hierarchical communication domains, which can be modeled as a domain tree where communication in lower-level domains is significantly faster than that in higher-level ones. Therefore, the key idea of XTree's partitioning is to exploit hierarchical locality by viewing the graph as a BFS tree and leveraging the topology knowledge to map the graph's BFS tree onto the domain tree, We evaluate the effectiveness of XTree by running various graph algorithms, on both real-world big graphs and synthetic trillion-scale graphs. XTree substantially reduces communication overhead and achieves orders of magnitude speedup against the Graph500 reference implementations with the state-of-the-art 2D-decomposition partitioning.

Online-transaction-processing (OLTP) applications require the underlying storage system to guarantee consistency and serializability for distributed transactions involving large numbers of servers, which tends to introduce high coordination cost and cause low system performance. In-network coordination is a promising approach to alleviate this problem, which leverages programmable switches to move a piece of coordination functionality into the network. This paper presents a fast and scalable transaction processing system called SwitchTx. At the core of SwitchTx is a decentralized multi-switch in-network coordination mechanism, which leverages modern switches' programmability to reduce coordination cost while avoiding the central-switch-caused problems in the state-of-the-art Eris transaction processing system. SwitchTx abstracts various coordination tasks (e.g., locking, validating, and replicating) as in-switch gather-and-scatter (GaS) operations, and offloads coordination to a tree of switches for each transaction (instead of to a central switch for all transactions) where the client and the participants connect to the leaves. Moreover, to control the transaction traffic intelligently, SwitchTx reorders the coordination messages according to their semantics and redesigns the congestion control combined with admission control. Evaluation shows that SwitchTx outperforms current transaction processing systems in various workloads by up to 2.16X in throughput, 40.4% in latency, and 41.5% in lock time.

Despite the fact that GPUs and accelerators are more efficient in deep learning (DL), commercial clouds like Facebook and Amazon now heavily use CPUs in DL computation because there are large numbers of CPUs which would otherwise sit idle during off-peak periods. Following the trend, CPU vendors have not only released high-performance many-core CPUs but also developed efficient math kernel libraries. However, current DL platforms cannot scale well to a large number of CPU cores, making many-core CPUs inefficient in DL computation. We analyze the memory access patterns of various layers and identify the root cause of the low scalability, i.e., the per-layer barriers that are implicitly imposed by current platforms which assign one single instance (i.e., one batch of input data) to a CPU. The barriers cause severe memory bandwidth contention and CPU starvation in the access-intensive layers (like activation and BN). This paper presents a novel approach called ParaX, which boosts the performance of DL on many-core CPUs by effectively alleviating bandwidth contention and CPU starvation. Our key idea is to assign one instance to each CPU core instead of to the entire CPU, so as to remove the per-layer barriers on the executions of the many cores. ParaX designs an ultralight scheduling policy which sufficiently overlaps the access-intensive layers with the compute-intensive ones to avoid contention, and proposes a NUMA-aware gradient server mechanism for training which leverages shared memory to substantially reduce the overhead of per-iteration parameter synchronization. We have implemented ParaX on MXNet. Extensive evaluation on a two-NUMA Intel 8280 CPU shows that ParaX significantly improves the training/inference throughput for all tested models (for image recognition and natural language processing) by 1.73X ~ 2.93X.

Traditional graph partitioning methods attempt to both minimize communication cost and guarantee load balancing in computation. However, the skewed degree distribution of natural graphs makes it difficult to simultaneously achieve the two objectives. This paper proposes topology refactorization (TR), a topology-aware method allowing graph-parallel systems to separately handle the two objectives: refactorization is mainly focused on reducing communication cost, and partitioning is mainly targeted for balancing the load. TR transforms a skewed graph into a more communication-efficient topology through fusion and fission , where the fusion operation organizes a set of neighboring low-degree vertices into a super-vertex, and the fission operation splits a high-degree vertex into a set of sibling sub-vertices. Based on TR, we design an efficient graph-parallel system (TopoX) which pipelines refactorization with partitioning to both reduce communication cost and balance computation load. Prototype evaluation shows that TopoX outperforms state-of-the-art PowerLyra by up to 78.5% (from 37.2%) on real-world graphs and is significantly faster than other graph-parallel systems, while only introducing small refactorization overhead and memory consumption.

Compressive spectral clustering (CSC) efficiently leverages graph filter and random sampling techniques to speed up clustering process. However, we find that CSC algorithm suffers from two main problems: i) The direct use of the dichotomy and eigencount techniques for estimating laplacian matrix’s k-th eigenvalue is expensive. ii) The computation of polynomial approximation repeats in each iteration for every cluster in the interpolation process, which occupies most of the computation time of CSC. To address these problems, we propose a new approach called FCSC for fast compressive spectral clustering. FCSC addresses the first problem by assuming that the eigenvalues approximately satisfy local uniform distribution, and addresses the second problem by recalculating the pairwise similarity between nodes with low-dimensional representation to reconstruct denoised laplacian matrix. The time complexity of reconstruction is linear with the number of non-zeros in laplacian matrix. As experimentally demonstrated on artificial and real-world datasets, our approach significantly reduces the computation time while preserving high clustering accuracy comparable to previous designs, verifying the effectiveness of FCSC.

Most proposed DHTs engage certain topology maintenance mechanisms specific to the static graphs on which they are based. The designs of these mechanisms are complicated and repeated with graph-relevant concerns. In this paper, we propose the “distributed line graphs” (DLG), a universal technique for designing DHTs based on arbitrary regular graphs. Using DLG, the main features of the initial graphs are preserved, and thus people can design a new DHT by simply choosing the graph with desirable features and applying DLG to it. We demonstrate the power of DLG by illustrating four DLG-enabled DHTs based on different graphs, namely, Kautz, de Bruijn, butterfly, and hypertree graphs. The effectiveness of our proposals is demonstrated through analysis, simulation, and implementation.