Considering the diverse nature of real-world distributed applications that makes it hard to identify a representative subset of distributed benchmarks, we focus on their underlying distributed algorithms. We present and characterize a new kernel benchmark suite (named IMSuite) that simulates some of the classical distributed algorithms in task parallel languages. We present multiple variations of our kernels, broadly categorized under two heads: (a) varying synchronization primitives (with and without fine grain synchronization primitives); and (b) varying forms of parallelization (data parallel and recursive task parallel). Our characterization covers interesting aspects of distributed applications such as distribution of remote communication requests, number of synchronization, task creation, task termination and atomic operations. We study the behavior (execution time) of our kernels by varying the problem size, the number of compute threads, and the input configurations. We also present an involved set of input generators and output validators. © 2014 Elsevier Inc. All rights reserved.

Venkata Nandivada

Department of Computer Science and Engineering

Algorithms

parallel algorithms

Synchronization

ATOMIC OPERATION

Benchmark suites

DATA PARALLELISM

Distributed applications

Performance evaluation

REMOTE COMMUNICATION

Synchronization primitive

TASK PARALLELISM

Benchmarking

Fulltext

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Journal of Parallel and Distributed Computing

Many modern task-parallel languages allow the programmer to synchronize tasks using high-level constructs like barriers, clocks, and phasers. While these high-level synchronization primitives help the programmer express the program logic in a convenient manner, they also have their associated overheads. In this paper, we identify the sources of some of these overheads for task-parallel languages like X10 that support lock-step synchronization, and propose a mechanism to reduce these overheads. We first propose three desirable properties that an efficient runtime (for task-parallel languages like X10, HJ, Chapel, and so on) should satisfy, to minimize the overheads during lock-step synchronization. We use these properties to derive a scheme to called uClocks to improve the efficiency of X10 clocks; uClocks consists of an extension to X10 clocks and two related runtime optimizations. We prove that uClocks satisfies the proposed desirable properties. We have implemented uClocks for the X10 language+runtime and show that the resulting system leads to a geometric mean speedup of 5.36× on a 16-core Intel system and 11.39× on a 64-core AMD system, for benchmarks with a significant number of synchronization operations. © 2019 John Wiley & Sons, Ltd.

Software - Practice and Experience

Efficient lock-step synchronization in task-parallel languages

OpenMP uses the efficient ‘team of workers’ model, where workers are given chunks of tasks (iterations of a parallel-for-loop, or sections in a parallel-sections block) to execute, and worker (not tasks) can be synchronized using barriers. Thus, OpenMP restricts the invocation of barriers in these tasks; as otherwise, the behavior of the program would be dependent on the number of runtime workers. To address such a restriction which can adversely impact programmability and readability, Aloor and Nandivada proposed UW-OpenMP by taking inspiration from the more intuitive interaction of tasks and barriers in newer task parallel languages like X10, HJ, Chapel and so on. UW-OpenMP gives the programmer an impression that each parallel task is executed by a unique worker, and importantly these parallel tasks can be synchronized using a barrier construct. Though UW-OpenMP is a useful extension of OpenMP (more expressive and efficient), it does not admit barriers within recursive functions invoked from parallel-for-loops, because of the inherent challenges in handing them. In this paper, we extend UW-OpenMP (we call it UWOmp++) to address this challenging limitation and in the process also realize more efficient programs. We propose a source to source transformation scheme to translate UWOmp++ C programs to equivalent OpenMP C programs that are guaranteed not to invoke barriers in any task. Our translation uses a novel intermediate representation called UWOmpCPS, which represents a parallel program written in OpenMP in an extended CPS format (admits parallel-for-loops and barriers). The use of this intermediate representation leads us to handle recursive functions within parallel-for-loops efficiently. We have implemented our proposed translation scheme in the ROSE compiler framework. Our preliminary evaluation shows that the proposed language extension to allow recursion helps plug an important gap in expressiveness, without compromising on the efficiency resulting from the ‘team of workers’ model. © 2019 Association for Computing Machinery.

ACM International Conference Proceeding Series

Efficiency and expressiveness in UW-OpenMP

X10 is a partitioned global address space programming language that supports the notion of places; a place consists of some data and some lightweight tasks called activities. Each activity runs at a place and may invoke a place-change operation (using the at-construct) to synchronously perform some computation at another place. These place-change operations can be very expensive, as they need to copy all the required data from the current place to the remote place. However, identifying the necessary number of place-change operations and the required data during each place-change operation are non-trivial tasks, especially in the context of irregular applications (like graph applications) that contain complex code with large amounts of cross-referencing objects-not all of those objects may be actually required, at the remote place. In this article, we present AT-Com, a scheme to optimize X10 code with place-change operations. AT-Com consists of two inter-related new optimizations: (i) AT-Opt, which minimizes the amount of data serialized and communicated during place-change operations, and (ii) AT-Pruning, which identifies/elides redundant place-change operations and does parallel execution of place-change operations. AT-Opt uses a novel abstraction, called abstract-place-tree, to capture place-change operations in the program. For each place-change operation, AT-Opt uses a novel inter-procedural analysis to precisely identify the data required at the remote place in terms of the variables in the current scope. AT-Opt then emits the appropriate code to copy the identified data-items to the remote place. AT-Pruning introduces a set of program transformation techniques to emit optimized code such that it avoids the redundant place-change operations. We have implemented AT-Com in the x10v2.6.0 compiler and tested it over the IMSuite benchmark kernels. Compared to the current X10 compiler, the AT-Com optimized code achieved a geometric mean speedup of 18.72× and 17.83× on a four-node (32 cores per node) Intel and two-node (16 cores per node) AMD system, respectively. © 2019 Association for Computing Machinery.

ACM Transactions on Architecture and Code Optimization

Optimizing remote communication in X10

X10 is a partitioned global address space (PGAS) programming language that supports the notion of places; a place consists of some data and some lightweight tasks called activities. Each activity runs at a place and may invoke a place-change operation (using the at-construct) to synchronously perform some computation at another place. These place-change operations need to copy all the required data from the current place to the remote place. However, identifying the required data during each place-change operation is a non-trivial task, especially in the context of irregular applications (like graph applications) that contain large amounts of cross-referencing objects - not all of those objects may be actually required, at the remote place. In this paper, we present a new optimization AT-Opt that minimizes the amount of data serialized and communicated during place-change operations. AT-Opt uses a novel abstraction called abstract-place-tree to capture place-change operations in the program. For each place-change operation, AT-Opt uses a novel inter-procedural analysis to precisely identify the data required at the remote place, in terms of the variables in the current scope. AT-Opt then emits the appropriate code to copy the identified dataitems to the remote place. We have implemented AT-Opt in the x10v2.6.0 compiler and tested it over the IMSuite benchmark kernels. Compared to the current X10 compiler, the AT-Opt optimized code achieved a geometric mean speedup of 8.61× and 5.57×, on a two-node (32 cores each) Intel and two-node (16 cores each) AMD system, respectively. © 2018 Association for Computing Machinery.

Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

Optimizing remote data transfers in X10

We present a new optimization DECAF that optimizes recursive task parallel (RTP) programs by reducing the task creation and termination overheads. DECAF reduces the task termination (join) operations by aggressively increasing the scope of join operations (in a semantics preserving way), and eliminating the redundant join operations discovered on the way. Further, DECAF extends the traditional loop chunking technique to perform load-balanced chunking, at runtime, based on the number of available worker threads. This helps reduce the redundant parallel tasks at different levels of recursion. We also discuss the impact of exceptions on our techniques and extend them to handle RTP programs that may throw exceptions. We implemented DECAF in the X10v2.3 compiler and tested it over a set of benchmark kernels on two different hardwares (a 16-core Intel system and a 64-core AMD system). With respect to the base X10 compiler extended with loop-chunking of Nandivada et al. [26] (LC), DECAF achieved a geometric mean speed up of 2.14× and 2.53× on the Intel and AMD system, respectively. We also present an evaluation with respect to the energy consumption on the Intel system and show that on average, compared to the LC versions, the DECAF versions consume 71.2% less energy. © 2017 Association for Computing Machinery.

Proceedings of the International Conference on Supercomputing

Optimizing recursive task parallel programs

ACM SIGPLAN Notices

Ligra

4th IEEE International Conference on Cloud Computing Technology and Science Proceedings

XGDBench: A benchmarking platform for graph stores in exascale clouds

An algorithmic strategy for in-network distributed spatial analysis in wireless sensor networks

A new distributed topology control algorithm based on optimization of delay and energy in wireless networks

Proceedings of the 2012 SIAM International Conference on Data Mining

A Flexible Open-Source Toolbox for Scalable Complex Graph Analysis

IMSuite: A benchmark suite for simulating distributed algorithms

Journal	Journal of Parallel and Distributed Computing
Publisher	Academic Press Inc.
ISSN	07437315
Open Access	Yes