Pregel's vertex-centric model allows us to implement many interesting graph algorithms, where optimization plays an important role in making it practically useful. Although many optimizations have been developed for dealing with different performance issues, it is hard to compose them together to optimize complex algorithms, where we have to deal with multiple performance issues at the same time. In this paper, we propose a new approach to composing optimizations, by making use of the interface, as a replacement of Pregel's message passing and aggregator mechanism, which can better structure the communication in Pregel algorithms. We demonstrate that it is convenient to optimize a Pregel program by simply using a proper channel from the channel library or composing them to deal with multiple performance issues. We intensively evaluate the approach through many nontrivial examples. By adopting the channel interface, our system achieves an all-around performance gain for various graph algorithms. In particular, the composition of different optimizations makes the S-V algorithm 2.20x faster than the current best implementation.
To support intuitive message slicing in Pregel-like systems, Telos @cite_36 proposes a layered architecture where interleaving tasks are implemented as separate , each having a user-defined compute() function with a dedicated message buffer. However, it lacks an essential feature for optimization that users cannot modify the implementation of the message buffer. Husky @cite_23 is a general-purpose distributed framework with the channel interface, and it supports primitives like , and and to combine the strength of graph-parallel and machine learning systems. We extend this idea for composing optimizations in graph-parallel system and propose our optimized channels for three common performance issues.
@cite_36 @cite_23
1889296357 2949679549 2092038045 2740001873
In this paper, we study resource allocation for multiuser multiple-input–single-output secondary communication systems with multiple system design objectives. We consider cognitive radio (CR) networks where the secondary receivers are able to harvest energy from the radio frequency when they are idle. The secondary system provides simultaneous wireless power and secure information transfer to the secondary receivers. We propose a multiobjective optimization framework for the design of a Pareto-optimal resource allocation algorithm based on the weighted Tchebycheff approach. In particular, the algorithm design incorporates three important system design objectives: total transmit power minimization, energy harvesting efficiency maximization, and interference-power-leakage-to-transmit-power ratio minimization. The proposed framework takes into account a quality-of-service (QoS) requirement regarding communication secrecy in the secondary system and the imperfection of the channel state information (CSI) of potential eavesdroppers (idle secondary receivers and primary receivers) at the secondary transmitter. The proposed framework includes total harvested power maximization and interference power leakage minimization as special cases. The adopted multiobjective optimization problem is nonconvex and is recast as a convex optimization problem via semidefinite programming (SDP) relaxation. It is shown that the global optimal solution of the original problem can be constructed by exploiting both the primal and the dual optimal solutions of the SDP-relaxed problem. Moreover, two suboptimal resource allocation schemes for the case when the solution of the dual problem is unavailable for constructing the optimal solution are proposed. Numerical results not only demonstrate the close-to-optimal performance of the proposed suboptimal schemes but unveil an interesting tradeoff among the considered conflicting system design objectives as well. Massive graphs, such as online social networks and communication networks, have become common today. To efficiently analyze such large graphs, many distributed graph computing systems have been developed. These systems employ the "think like a vertex" programming paradigm, where a program proceeds in iterations and at each iteration, vertices exchange messages with each other. However, using Pregel's simple message passing mechanism, some vertices may send receive significantly more messages than others due to either the high degree of these vertices or the logic of the algorithm used. This forms the communication bottleneck and leads to imbalanced workload among machines in the cluster. In this paper, we propose two effective message reduction techniques: (1)vertex mirroring with message combining, and (2)an additional request-respond API. These techniques not only reduce the total number of messages exchanged through the network, but also bound the number of messages sent received by any single vertex. We theoretically analyze the effectiveness of our techniques, and implement them on top of our open-source Pregel implementation called Pregel+. Our experiments on various large real graphs demonstrate that our message reduction techniques significantly improve the performance of distributed graph computation. In many-core architectures different distributed applications are executed in parallel. The applications may need hard guarantees for communication with respect to latency and throughput to cope with their constraints. Networks on Chip (NoC) are the most promising approach to handle these requirements in architectures with a large number of cores. Dynamic reservation of communication resources in virtual channel NoCs is used to enable quality of service for concurrent communication. This paper presents a router design supporting best effort and connection-oriented guaranteed service communication. The communication resources are shared dynamically between the two communication schemes. The key contribution is a concept for virtual channel reservation supporting different bandwidth and latency guarantees for simultaneous guaranteed service communication flows. Different to state-of-the-art, the used scheduling approach allows to give hard guarantees regarding throughput and latency. The concept enables to adjust the bandwidth and latency requirements of connections at run-time to cope with dynamically changing application requirements. Due to its distributed reservation process and resource allocation it offers good scalability for many-core architectures. The implementation of a router and the required extension of a network interface to support the proposed concept are presented. The software perspective is discussed. An algorithm is presented that is used to establish guaranteed service connections according to the applications bandwidth requirements. Simulation results are compared to state-of-the-art arbitration schemes and show significant improvements of latency and throughput, e.g. for an MPEG4 application. Synthesis results expose the low area overhead and impact on energy consumption which makes the concepts highly attractive for QoS-constraint many-core architectures. Traditionally, MPI runtimes have been designed for clusters with a large number of nodes. However, with the advent of MPI+CUDA applications and dense multi-GPU systems, it has become important to design efficient communication schemes. This coupled with new application workloads brought forward by Deep Learning frameworks like Caffe and Microsoft CNTK pose additional design constraints due to very large message communication of GPU buffers during the training phase. In this context, special-purpose libraries like NCCL have been proposed. In this paper, we propose a pipelined chain (ring) design for the MPI_Bcast collective operation along with an enhanced collective tuning framework in MVAPICH2-GDR that enables efficient intra- internode multi-GPU communication. We present an in-depth performance landscape for the proposed MPI_Bcast schemes along with a comparative analysis of NCCL Broadcast and NCCL-based MPI_Bcast. The proposed designs for MVAPICH2-GDR enable up to 14X and 16.6X improvement, compared to NCCL-based solutions, for intra- and internode broadcast latency, respectively. In addition, the proposed designs provide up to 7 improvement over NCCL-based solutions for data parallel training of the VGG network on 128 GPUs using Microsoft CNTK. The proposed solutions outperform the recently introduced NCCL2 library for small and medium message sizes and offer comparable better performance for very large message sizes.