Search

Cloud warehouses have been exploiting multi-tenancy in CPU-FPGA collaborative environments, so clients can share the same infrastructure, achieving scalability and maximizing resource utilization. Therefore, the distribution of tasks across CPU and FPGA must be well-balanced so performance and energy are optimized in a highly variant workload scenario. In this paper, we take a step further and, in contrast to existing approaches, exploit DVFS (Dynamic Voltage and Frequency Scaling) on the CPU, together with an intelligent CPU-FPGA resource provisioning mechanism, to further improve energy. For that, we propose EASER, an end user-transparent framework that employs multiple strategies and dynamically selects the most appropriate one to optimize resource provisioning and DVFS according to the warehouse needs, workload properties, and target architecture. Our synergistic DVFS optimization brings up to 22% additional energy gains over our dynamic provisioning alone. Compared to fixed single strategies with DVFS, EASER brings, on average, 71% of energy gains. • We explore voltage/frequency scaling and provisioning in multi-tenant CPU-FPGA Cloud. • Different strategies are needed depending on the architecture and workload properties. • EASER is end-user transparent and fully-adaptive. • EASER achieves energy improvements without harming makespan. [ABSTRACT FROM AUTHOR]

Structural plasticity of the brain describes the creation of new and the deletion of old synapses over time. Rinke et al. (JPDC 2018) introduced a scalable algorithm that simulates structural plasticity for up to one billion neurons on current hardware using a variant of the Barnes–Hut algorithm. They demonstrate good scalability and prove a runtime complexity of O (n log 2 ⁡ n). In this comment paper, we show that with careful consideration of the algorithm and a rigorous proof, the theoretical runtime can even be classified as O (n log ⁡ n). • Improved serial runtime bound for the adapted Barnes–Hut algorithm to Θ(n*log(n)). • Improved the parallel runtime bound to Θ(n/p*log(n)+p). • Mathematical justification that the given runtime bound is sharp. [ABSTRACT FROM AUTHOR]

Communication overhead is the key challenge for distributed training. Gradient compression is a widely used approach to reduce communication traffic. When combined with a parallel communication mechanism method like pipeline, gradient compression technique can greatly alleviate the impact of communication overhead. However, there exist two problems of gradient compression technique to be solved. Firstly, gradient compression brings in extra computation cost, which will delay the next training iteration. Secondly, gradient compression usually leads to a decrease in convergence accuracy. In this paper, we combine parallel mechanism with gradient quantization and periodic full-gradient compensation, and propose a new distributed optimization method named CP-SGD, which can hide the overhead of gradient compression, overlap part of the communication and obtain high convergence accuracy. The local update operation in CP-SGD allows the next iteration to be launched quickly without waiting for the completion of gradient compression and the current communication process. Besides, the accuracy loss caused by gradient compression is solved by k-step correction method introduced in CP-SGD, which provides a gradient correction every k iterations. We prove that CP-SGD has a convergence guarantee and it achieves at least O (1 K + 1 K) convergence rate, where K is the number of iterations. We conduct extensive experiments on MXNet to verify the convergence properties and scaling performance of CP-SGD. Experimental results on a 32-GPU cluster show that convergence accuracy of CP-SGD is close to or even slightly better than that of S-SGD, and its end-to-end time is 30% less than 2-bit gradient compression under a 56Gbps bandwidth environment. In addition, we analyze the performance of CP-SGD when training on 8, 16 and 32 GPUs. It is found that CP-SGD is suitable for most compression-supported update algorithms, and its scalability is approximately linear. • CP-SGD: Distributed Stochastic Gradient Descent with Compression and Periodic Compensation. • CP-SGD help distributed deep learning train with high-accuracy and friendly-communication simultaneously. • Combining the advantages of parallel mechanism and gradient compression. • K-step correction technique makes CP-SGD achieve codesign optimizations and improve compression-based methods greatly. • CP-SGD suits most compression-supported update algorithms and gradient compression strategies. [ABSTRACT FROM AUTHOR]

• A parallel scalable DBSCAN algorithm which outperforms other implementations. • Optimizations for data partitioning, spatial indexing, and cluster merging. • Exploiting hybrid parallelization to take advantage of modern HPC architectures. • Demonstrating accuracy, performance and scalability of our algorithm. Dbscan is a density-based clustering algorithm which is well known for its ability to discover clusters of arbitrary shape as well as to distinguish noise. As it is computationally expensive for large datasets, research studies on the parallelization of Dbscan have been received a considerable amount of attention. In this paper we present an exact, efficient and scalable parallel Dbscan algorithm which we call Hy-Dbscan. It employs three major techniques to enable scalable data clustering on distributed-memory computers i) a modified kd-tree for domain decomposition, ii) a spatial indexing approach based on grid and inference, and iii) a cluster merging scheme based on distributed Rem's Union-Find algorithm. Moreover, Hy-Dbscan exploits process level and thread level parallelization. In experiments, we have demonstrated performance and scalability using two scientific datasets on up to 2048 cores of a distributed-memory computer. Through extensive evaluation, we show that Hy-Dbscan significantly outperforms previous state-of-the-art Dbscan implementations. [ABSTRACT FROM AUTHOR]

• Simulation of complex networks. • Simulation of dissemination protocols. • Parallel and Distributed Simulation (PADS). • Adaptive self-clustering for load-balancing. Complex networks are an important methodology to model several (if not all) aspects of the real world, in which multiple entities interact, in some way. While many aspects related to such interactions can be investigated by looking at the general mathematical metrics of the networks, an alternative approach lies in the simulation of some application protocol on top of (large scale) complex networks. In this paper, we present a study on this intricate problem. The complexity of the simulation is due to the need to model all the interactions among network nodes. We focus on discrete-event simulation, a simulation methodology that enables both sequential (i.e. monolithic) and Parallel And Distributed Simulation (i.e. PADS) approaches. We discuss the performance and scalability requirements that the simulator should have. We also introduce a case study based on the agent-based simulation of gossip dissemination on top of a complex network. To demonstrate the viability of this simulation technique, we focus on a tool we built to simulate complex networks. The tool exploits adaptive partitioning mechanisms, which are essential to reduce the communication overhead in the PADS. An experimental evaluation has been conducted using different network topologies and simulator setups. Results demonstrate the feasibility of the approach to simulate complex networks. [ABSTRACT FROM AUTHOR]

Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. • LHABcast is a fully decentralized leaderless algorithm broadcast algorithm. • LHABcast organizes processes on a vCube, which has several logarithmic properties. • LHABcast uses autonomic spanning trees rooted at the sender for message dissemination. • LHABcast is described with examples, and multiple properties are proved. • LHABcast was evaluated both with a Neko simulation and using the Java Akka framework. [ABSTRACT FROM AUTHOR]

Synchronous SGD with data parallelism, the most popular parallelization strategy for CNN training, suffers from the expensive communication cost of averaging gradients among all workers. The iterative parameter updates of SGD cause frequent communications and it becomes the performance bottleneck. In this paper, we propose a lazy parameter update algorithm that adaptively adjusts the parameter update frequency to address the expensive communication cost issue. Our algorithm accumulates the gradients if the difference of the accumulated gradients and the latest gradients is sufficiently small. The less frequent parameter updates reduce the per-iteration communication cost while maintaining the model accuracy. Our experimental results demonstrate that the lazy update method remarkably improves the scalability while maintaining the model accuracy. For ResNet50 training on ImageNet, the proposed algorithm achieves a significantly higher speedup (739.6 on 2048 Cori KNL nodes) as compared to the vanilla synchronous SGD (276.6) while the model accuracy is almost not affected (<0.2% difference). • Adaptive parameter update frequency control for scalable parallel deep learning. • Allowing gradient accumulation considering the direction of the gradients. • Reducing per-iteration communication cost at the input side model layers. • Overlapping gradient communications with backpropagation computations. [ABSTRACT FROM AUTHOR]

• A new mesh-based method for designing unstructured mesh particle-in-cell simulations. • Implementation details of a library, PUMIPic, using the mesh-based approach on GPUs. • Analysis of mesh-based scaling on a pseudo physics simulation built with PUMIPic. Unstructured mesh particle-in-cell, PIC, simulations executing on the current and next generation of massively parallel systems require new methods for both the mesh and particles to achieve performance and scalability on GPUs. The traditional approach to implementing PIC simulations defines data structures and algorithms in terms of particles with a full copy of the unstructured mesh on every process. To effectively scale the unstructured mesh and particles, mesh-based PIC uses the unstructured mesh as the predominant data structure with the particles stored in terms of the mesh entities. This paper details the PUMIPic library, a framework for developing efficient and performance-portable mesh-based PIC simulations on GPU systems. A pseudo physics simulation based on a five-dimensional gyro-kinetic code for modeling plasma physics is used to examine the performance of PUMIPic. Scaling studies of the unstructured mesh partition and number of particles are performed up to 4096 nodes of the Summit system at Oak Ridge National Laboratory. The studies show that mesh-based PIC can utilize a partitioned mesh and maintain scaling up to system limitations. [ABSTRACT FROM AUTHOR]

Blockchain systems, one of the most popular distributed systems, are well-applied in various scenarios, e.g., logistics and finance. However, traditional blockchain systems suffer from scalability issues. To tackle this issue, Payment Channel Hubs (PCHs) are proposed. Recent efforts, such as A2L (SP'21) and Teechain (SOSP'19), enhance the privacy, reusability, and interoperability properties of PCHs. Nevertheless, these solutions have intrinsic limitations: they rely on trusted hardware or suffer from the deposit lock-in problem. Furthermore, the functionalities of some of these solutions are restricted to fixed-amount payments and do not support multi-party participation. These aforementioned problems limit their capabilities to alleviate blockchain scalability issues. In this paper, we propose PRI, a novel PCH solution that simultaneously guarantees transaction P rivacy (i.e., relationship unlinkability and value confidentiality), deposit R eusability, and blockchain I nteroperability, which can mitigate the aforementioned problems. PRI is constructed by several new building blocks, including (1) an atomic deposit protocol that enforces user and hub to deposit equivalent assets in a shared address for building a fair payment channel; (2) a privacy-preserving deposit certification scheme that leverages the Pointcheval and Sanders signature and non-interactive zero-knowledge proof to resolve the deposit lock-in issue in maintaining payment channels; (3) a range proof which ensures the legality and confidentiality of transaction values. We conduct extensive experimental evaluations of PRI, demonstrating that it improves the state-of-the-art approaches in terms of performance. • We propose a dual-script atomic deposit protocol to securely lock assets without an expiration time, preventing the loss of deposits in dishonest scenarios. • Additionally, we introduce PRI, a flexible and privacy-preserving PCH-based off-chain payment solution, built on the atomic deposit protocol and cryptographic primitives. • We conducted a feasibility and performance evaluation, considering computation cost, communication cost, and latency. • In two-party payments, PRI achieves a throughput of 7.5 payments per second for each payer-payee pair with a communication cost of under 20 KB. • Compared to BOLT and A2L, PRI demonstrates superior performance. [ABSTRACT FROM AUTHOR]