In this paper, we propose a distributed, unordered, label-correcting distance-1 Grundy (vertex) coloring algorithm, namely, Distributed Control (DC) coloring algorithm. Our algorithm eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. DC proceeds optimistically, correcting the colors asynchronously as the algorithm progresses and depends on local ordering of tasks to minimize the execution of sub-optimal work. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm and compare their performance with 4 different types of standard RMAT graphs and real-world graphs. We show that the elimination of waiting time of global and vertex-centric barriers and investing this time for local ordering leads to improved scaling for graphs with prominent power-law characteristics and densely interconnected local subgraphs.

Economic competitiveness and national security depend increasingly on the insightful analysis of large data sets. The diversity of real-world data sources and analytic workflows impose challenging hardware and software requirements for parallel graph platforms. The irregular nature of graph methods is not supported well by the deep memory hierarchies of conventional distributed systems, requiring new processor and runtime system designs to tolerate memory and synchronization latencies. Moreover, the efficiency of relational table operations and matrix computations are not attainable when data is stored in common graph data structures. In this paper, we present HAGGLE, a high-performance, scalable data analytics platform. The platform's hybrid data model supports a variety of distributed, thread-safe data structures, parallel programming constructs, and persistent and streaming data. An abstract runtime layer enables us to map the stack to conventional, distributed computer systems with accelerators. The runtime uses multithreading, active messages, and data aggregation to hide memory and synchronization latencies on large-scale systems.

Because they were developed for optimal sequential complexity, classical graph algorithms as found in textbooks have strictly-defined orders of operations. Enforcing a prescribed order of operations, or even an approximate order, in a distributed memory setting requires significant amounts of synchronization, which in turn can severely limit scalability. As a result, new algorithms are typically required to achieve scalable performance, even for solving well-known graph problems. Yet, even in these cases, parallel graph algorithms are written according to parallel programming models that evolved for, e.g., scientific computing, and that still have inherent, and scalability-limiting, amounts of synchronization. In this paper we present a new approach to parallel graph algorithms: synchronization-avoiding algorithms. To eliminate synchronization and its associated overhead, synchronization-avoiding algorithms perform work in an unordered and fully asynchronous fashion in such a way that the result is constantly refined toward its final state. "Wasted" work is minimized by locally prioritizing tasks using problem-dependent task utility metrics. We classify algorithms for graph applications into two broad categories: algorithms with monotonic updates (which evince global synchronization) and algorithms with non-monotonic updates (which evince vertex-centric synchronization). We apply our approach to both classes and develop novel, synchronization-avoiding algorithms for solving exemplar problems: SSSP and connected components for the former, graph coloring for the latter. We demonstrate that eliminating synchronization in conjunction with effective scheduling policies and optimizations in the runtime results in improved scalability for both classes of algorithms.

The following topics are dealt with: parallel processing; learning (artificial intelligence); graphics processing units; graph theory; parallel algorithms; scheduling; application program interfaces; parallel architectures; storage management; parallel machines.

In this paper we explore scheduling and runtime system support for unordered distributed graph computations that rely on optimistic (speculative) execution. Performance of such algorithms is impacted by two competing trends: the higher degree of parallelism enabled by optimistic execution in turn requires substantial runtime support. To address the potentially high overhead and scheduling complexity introduced by the runtime, we investigate customizable scheduling policies that augment the scheduler of the underlying runtime to adapt it to a specific graph application. We present several implementations of Distributed Control (DC), a data-driven unordered approach with work prioritization and demonstrate that customizable scheduling policies result in the most efficient implementation, outperforming the well-known ?-stepping Single-Source Shortest Paths (SSSP) and Jones-Plassmann vertex-coloring algorithms. We apply two scheduling techniques, flow control and adaptive frequency of network progress, which allow application-level control over the balance of domain work and the runtime work. Experimental results show the benefit of such application-aware scheduling for irregular distributed graph algorithms.

We propose a distributed, unordered, label-correcting distance-1 vertex coloring algorithm, called Distributed Control (DC) coloring algorithm. DC eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm in the AM++ AMT runtime and compare their performance. We show that, with runtime support, the elimination of waiting time of vertex-centric barriers and investing this time for local ordering results in better execution time for power-law graphs with dense local subgraphs.

The maximal independent set (MIS) graph problem arises in many applications such as computer vision, information theory, molecular biology, and process scheduling. The growing scale of graph data suggests the use of distributed memory hardware as a cost-effective approach to providing necessary compute and memory resources. Existing distributed memory parallel MIS algorithms rely on synchronous communication and use techniques such as subgraph computations. In this paper, we present an asynchronous distributed-memory parallel graph algorithm that relies on a virtual directed acyclic graph (DAG) that is created during the algorithm execution. We introduce two additional algorithms that save computations by ordering generated work. The first algorithm applies ordering globally to reduce computations, and the second algorithm applies ordering locally at the level of threads to minimize the synchronization overhead. We use two different implementations of Luby's algorithm variants as baseline to compare the performance of the presented algorithms: (1) vertex-centric Luby A and Luby B implementations, and (2) the CombBLAS linear-algebra Luby A implementation. Results show that proposed algorithms outperform both implementations of Luby algorithms, especially in distributed execution. Furthermore, we show that for low- diameter graphs the algorithm that applies global ordering scales better than other algorithms and for high diameter graphs the original asynchronous algorithm and thread-level ordering algorithm show better performance.

In distributed computing, parallel overheads such as \emph{synchronization overhead} may hinder performance. We introduce the idea of \emph{Distributed Control} (DC) where global synchronization is reduced to \emph{termination detection} and each worker proceeds ahead optimistically, based on the local knowledge of the global computation. To avoid "wasted'' work, \DC relies on local work prioritization. However, the work order obtained by local prioritization is susceptible to interference from the runtime. We show that employing effective scheduling policies and optimizations in the runtime, in conjunction with eliminating global barriers, improves performance in two graph applications: single-source shortest paths and connected components.

Measurements for distributed algorithms, such as performance results, are usually reported using averages, similarly to prevailing practice in other areas of computer science. We argue that including standard deviations offers additional information and that the minimal burden of providing standard deviations is outweighed by the benefits. We propose a new way of reporting run time speedup that incorporates standard deviation and demonstrate its usefulness in terms of two distributed graph algorithms.

With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.

We describe a novel methodology for systematic and rigorous testing of C++ generic libraries: separate testing. The approach is based on separate testing of generic (template) algorithms and data structures and of user-defined types that will be used with the library. Templates are tested against specifications using representative types called prototypes that contain metadata which is used to query otherwise unobservable properties of the input types and values. User-defined types are tested against the concepts required by the generic components of the library. Testing separately minimizes the required effort while fully exercising all components involved. The methodology is supported by the Origin Testing library, which is, in turn, being used to test the remainder of the Origin C++ 11 libraries.

Abstract Earlier studies have introduced a list of high-level evaluation criteria to assess how well a language supports generic programming. Languages that meet all criteria include Haskell because of its type classes and C++ with the concept feature. We refine these criteria into a taxonomy that captures commonalities and differences between type classes in Haskell and concepts in C++ and discuss which differences are incidental and which ones are due to other language features. The taxonomy allows for an improved understanding of language support for generic programming, and the comparison is useful for the ongoing discussions among language designers and users of both languages.

Since the standard template library (STL), generic libraries in C++ rely on concepts to precisely specify the requirements of generic algorithms (function templates) on their parameters (template arguments). Modifying the definition of a concept even slightly, can have a potentially large impact on the (interfaces of the) entire library. In particular the non-local effects of a change, however, make its impact difficult to determine by hand. In this paper we propose a conceptual change impact analysis (CCIA), which determines the impact of changes of the conceptual specification of a generic library. The analysis is organized in a pipe-and-filter manner, where the first stage finds any kind of impact, the second stage various specific kinds of impact. Both stages describe reachability algorithms, which operate on a conceptual dependence graph. In a case study, we apply CCIA to a new proposal for STL iterator concepts, which is under review by the C++ standardization committee. The analysis shows a number of unexpected incompatibilities and, for certain STL algorithms, a loss of genericity