The MPI standard provides the foundational building blocks for most parallel applications running on large-scale HPC architectures.Collective communication operations in MPI are critical components for the scalability of these applications. Most MPI librariesoffer several algorithms for a specific collective operation, and each library selects the algorithm to be used based on the numberof processes, the message size, and possibly other factors. Each collective algorithm may perform better in certain scenarios, andthus, selecting the most suitable algorithm for each use case is essential. However, even the best algorithm in a given MPI librarymay deliver suboptimal performance.Self-consistent MPI performance guidelines capture semantic relationships between different collective operations and exploitthese to express performance expectations that collectives should reasonably satisfy to be considered performance-consistent. Forcollective communication, such performance guidelines typically state that a specialized collective call should not be slower thanless specialized counterparts.In this article, we demonstrate how the consistency of MPI libraries with respect to performance guidelines can be analyzed.For this purpose, we present a tool that checks guideline compliance. For regular collective operations such as MPI_Bcast, thetool contains multiple emulated versions of the collective by composing less specialized operations. Then, for a specific number ofprocesses and message sizes, the tool experimentally assesses whether the algorithm selected by the MPI library is slower than itsemulated counterparts. If that is the case, a performance-guideline violation is detected. In a broader empirical study, we assess thecurrent state of performance consistency in MPI libraries on modern supercomputers.

ABSTRACT mpisee is a lightweight profiling tool designed to track MPI communication operations per communicator, providing fine‐grained insights into MPI applications that use communicators to partition MPI communication. While existing profiling tools offer valuable information, they may limit detailed analysis and optimization for such MPI applications, as they do not associate MPI communication with their communicator. Additionally, mpisee categorizes MPI communication operations based on message size, offering more granular information. It uses an SQLite database to efficiently store the profiling data, enabling users to analyze the application's profile from various perspectives, focusing on specific MPI ranks, operations, and more. Our analysis shows that mpisee incurs less than 5% overhead, performing on par with other state‐of‐the‐art profilers. We demonstrate mpisee 's effectiveness by profiling and analyzing an FFT application, revealing potential performance bottlenecks related to the MPI_Alltoallv collective operation on small communicators and insights not available by other profilers. Leveraging this detailed information, we improved the application's overall performance by selecting different algorithms for MPI_Alltoallv and measuring their performance on different communicators with mpisee . This study illustrates mpisee 's utility and highlights the significant advantages of a communicator‐centric approach in MPI profiling.

In modern, deeply hierarchical HPC systems shared resource congestion can hinder the efficient use of many cores by parallel applications and degrade performance. Such congestion is often caused when parallel processes within an application that execute similar operations share the same resources. Previous research suggests using fewer cores with better process-to-core mapping can improve applications’ performance but leaves many cores unused. To utilize these cores, we colocate additional applications and map them using a topology-aware process-to-core, application-agnostic mapping algorithm. We show that these mappings significantly impact memory bandwidth and communication latency. We evaluate our approach using eight parallel applications on an HPC system with 128-core nodes, demonstrating the performance effects of mappings combined with colocation. Our goal is to determine whether colocation with topology-aware mapping is a viable alternative to typical exclusive node allocation. Our results show makespan improvements of 2.4x over exclusive allocation in an HPC system, demonstrating the potential benefits of colocation with optimized mappings.

We explore the use of a regular, circulant graph communication pattern for the implementation of the reduction-to-all (MPI_Allreduce), by specialization the reduction-to-root (MPI_Reduce), the reduce-scatter (MPI_Reduce_scatter_block), the all-to-all-broadcast (MPI_Allgather) and the rooted gather and scatter (MPI_Gather and MPI_Scatter) collective operations, all as found in MPI (the Message-Passing Interface), for commutative operators and for any number of processes. The reduction-to-all algorithm reconstructs the little known algorithm by Bar-Noy, Kipnis and Schieber (1993), which the paper considerably extends.We experiment with extensions and combinations of the algorithms for these operations, and examine their performance from the perspective of performance guidelines, and in direct comparison to the implementations in common MPI libraries. On a small cluster with 36 × 32 cores and two larger HPC production systems, we show that we can especially for MPI_Reduce_scatter_block achieve considerably better performance than standard MPI library implementations. Our algorithms can perform consistently, which the implementations in standard MPI libraries sometimes do not.In a homogeneous, one-ported communication system with linear transmission costs, reduction-to-all, reduce-scatter and all-to-all-broadcast can all be implemented in O(log p + m) time steps for problems of size m with small constants which we analyze and discuss.

A major design objective of MPI is to enable support for the construction of safe parallel libraries that can be used and mixed freely in complex applications. In this respect, MPI has been extremely successful; but may nevertheless lack elementary supporting functionality for some situations, and may have made design choices that are difficult to accommodate in certain libraries. We discuss several cases of library construction requiring different kinds of supporting MPI functionality, and propose concrete improvements for library implementations and future MPI versions to alleviate the problems that were encountered. Specifically, we pinpoint (performance) issues with MPI object attributes, caching and lookup, request objects, partly collective and non-blocking communicator creation, process local reductions, type correct process local copying, and user-defined datatypes.

We give a fast(er), communication-free, parallel construction of optimal communication schedules that allow broadcasting of$n$distinct blocks of data from a root processor to all other processors in 1-ported, p- processor networks with full bidirectional communication. For any$p$and$n$, broadcasting in this model requires$n-1+\square \log_{2}p^{-}$communication rounds. In contrast to other constructions, all processors follow the same, circulant graph communication pattern, which makes it possible to use the schedules for the allgather (all-to-all-broadcast) operation as well. The new construction takes$O(\log^{3}p)$time steps per processor, each of which can compute its part of the schedule independently of the other processors in$O(\log p)$space. The result is a significant improvement over the sequential$\overline{O}(p\log^{2}p)$time and$O(p\log p)$space construction of Träff and Ripke (2009) with considerable practical import. The round-optimal schedule construction is then used to implement communication optimal algorithms for the broadcast and (irregular) allgather collective operations as found in MPI (the Message-Passing Interface), and significantly and practically improve over the implementations in standard MPI libraries for certain problem ranges. The application to the irregular allgather operation is entirely new.

We are considering the following problem. In a network of p processors, one designated root processor has n indivisible blocks of data that have to be broadcast (transmitted to) all other processors. The processors are fully connected, and in one communication operation, a processor can simultaneously receive one block of data from one other processor and send a block of data to one other, possibly different processor.

Abstract Commercial multicore central processing units (CPU) integrate a number of processor cores on a single chip to support parallel execution of computational tasks. Multicore CPUs can possibly improve performance over single cores for independent parallel tasks nearly linearly as long as sufficient bandwidth is available. Ideal speedup is, however, difficult to achieve when dense intercommunication between the cores or complex memory access patterns is required. This is caused by expensive synchronization and thread switching, and insufficient latency toleration. These facts guide programmers away from straight-forward parallel processing patterns toward complex and error-prone programming techniques. To address these problems, we have introduced the Thick control flow (TCF) Processor Architecture. TCF is an abstraction of parallel computation that combines self-similar threads into computational entities. In this paper, we compare the performance and programmability of an entry-level TCF processor and two Intel Skylake multicore CPUs on commonly used parallel kernels to find out how well our architecture solves these issues that greatly reduce the productivity of parallel software development. Code examples are given and programming experiences recorded.

The lock-free, ordered, singly linked list as proposed in [5, 8] is a textbook example of a concurrent data structure [6, 10]. The data structure supports lock-free insertion and deletion, and wait-free contains operations on items identified by a unique key. The lock-free implementation is actually quite subtle. The ordering condition and a relaxed invariant makes it possible to do with a single-word Compare-And-Swap operation (CAS), and all operations can be shown to be linearizable even though linearization does not always happen at fixed points in the code. The lock-free data structure has many direct and indirect applications, notably in the implementation of concurrent skiplists and hash tables [8, 9, 11, 12].

Good process-to-compute-node mappings can be decisive for well performing HPC applications. A special, important class of process-to-node mapping problems is the problem of mapping processes that communicate in a sparse stencil pattern to Cartesian grids. By thoroughly exploiting the inherently present structure in this type of problem, we devise three novel distributed algorithms that are able to handle arbitrary stencil communication patterns effectively. We analyze the expected performance of our algorithms based on an abstract model of inter- and intra-node communication. An extensive experimental evaluation on several HPC machines shows that our algorithms are up to two orders of magnitude faster in running time than a (sequential) high-quality general graph mapping tool, while obtaining similar results in communication performance. Furthermore, our algorithms also achieve significantly better mapping quality compared to previous state-of-the-art Cartesian grid mapping algorithms. This results in up to a threefold performance improvement of an MPI_Neighbor_alltoall exchange operation. Our new algorithms can be used to implement the MPI_Cart_create functionality.

Many modern, high-performance systems increase the cumulated node-bandwidth by offering more than a single communication network and/or by having multiple connections to the network, such that a single processor-core cannot by itself saturate the off-node bandwidth. Efficient algorithms and implementations for collective operations as found in, e.g., MPI, must be explicitly designed for exploiting such multilane capabilities. We are interested in gauging to which extent this might be the case. We systematically decompose the MPI collectives into similar operations that can execute concurrently on and exploit multiple network lanes. Our decomposition is applicable to all standard MPI collectives (broadcast, gather, scatter, allgather, reduce allreduce, reduce-scatter, scan, alltoall), and our implementations' performance can be readily compared to the native collectives of any given MPI library. Contrary to expectation, our full-lane, performance guideline implementations in many cases show surprising performance improvements with different MPI libraries on a dual-socket, dual-network Intel OmniPath cluster, indicating a large potential for improving the performance of native MPI library implementations. Our full-lane implementations are in many cases large factors faster than the corresponding MPI collectives. We see similar results on a larger, dual-rail Intel InfiniBand cluster. The results indicate considerable room for improvement of the MPI collectives in current MPI libraries including a more efficient use of multilane capabilities.

In order to provide for type correct implementations of applications in MPI that use derived datatypes to describe complex and possibly heterogeneous data layouts, signature datatypes describing the sequence of basic datatypes comprising the complex data layout in a compact manner have often been proposed and used to communicate and store such data in a type correct way. Signature datatypes are particularly useful in implementations of algorithms for collective communication employing pipelining and/or message-combining.

A major reason for the success of MPI as the standard for large-scale, distributed memory programming is the economy and orthogonality of key concepts. These very design principles suggest leaner and better support for stencil-like, sparse collective communication, while at the same time reducing significantly the number of concrete operation interfaces, extending the functionality that can be supported by high-quality MPI implementations, and provisioning for possible future, much more wide-ranging functionality.

Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation when processing graphs on a parallel computer. When a topology of a distributed system is known, an important task is then to map the blocks of the partition onto the processors such that the overall communication cost is reduced. We present novel multilevel algorithms that integrate graph partitioning and process mapping. Important ingredients of our algorithm include fast label propagation, more localized local search, initial partitioning, as well as a compressed data structure to compute processor distances without storing a distance matrix. Moreover, our algorithms are able to exploit a given hierarchical structure of the distributed system under consideration. Experiments indicate that our algorithms speed up the overall mapping process and, due to the integrated multilevel approach, also find much better solutions in practice. For example, one configuration of our algorithm yields similar solution quality as the previous state-of-the-art in terms of mapping quality for large numbers of partitions while being a factor 9.3 faster. Compared to the currently fastest iterated multilevel mapping algorithm Scotch, we obtain 16% better solutions while investing slightly more running time.

We study algorithmic approaches for recovering from the failure of several compute nodes in the parallel preconditioned conjugate gradient (PCG) solver on large-scale parallel computers. In particular, we analyze and extend an exact state reconstruction (ESR) approach, which is based on a method proposed by Chen (2011). In the ESR approach, the solver keeps redundant information from previous search directions, so that the solver state can be fully reconstructed if a node fails unexpectedly. ESR does not require checkpointing or external storage for saving dynamic solver data and has low overhead compared to the failure-free situation.

We introduce Cartesian Collective Communication as sparse, collective communication defined on processes (processors) organized into d-dimensional tori or meshes. Processes specify local neighborhoods, e.g., stencil patterns, by lists of relative Cartesian coordinate offsets. The Cartesian collective operations perform data exchanges (and reductions) over the set of all neighborhoods such that each process communicates with the processes in its local neighborhood. The key requirement is that local neighborhoods must be structurally identical (isomorphic). This makes it possible for processes to compute correct, deadlock-free, efficient communication schedules for the collective operations locally without any interaction with other processes. Cartesian Collective Communication substantially extends collective neighborhood communication on Cartesian communicators as defined by the MPI standard, and is a restricted form of neighborhood collective communication on general, distributed graph topologies.

No abstract available.

We study the complexity of finding communication trees with the lowest possible completion time for rooted, irregular gather and scatter collective communication operations in fully connected, k-ported communication networks under a linear-time transmission cost model. Consecutively numbered processors specify data blocks of possibly different sizes to be collected at (gather) or distributed from (scatter) some (given) root processor where they are stored in processor order. We distinguish between ordered and non-ordered communication trees depending on whether segments of blocks are maintained in processor order. We show that lowest completion time, ordered communication trees under one-ported communication can be found in polynomial time by giving simple, but costly dynamic programming algorithms. In contrast, we show that it is an NP-hard problem to construct completion-time optimal, non-ordered communication trees. We have implemented the dynamic programming algorithms for homogeneous networks to evaluate the quality of different types of communication trees, in particular to analyze a recent, distributed, problem-adaptive tree construction algorithm. Model experiments show that this algorithm is close to optimum for a selection of block size and root processor distributions. A concrete implementation for specially structured problems shows that optimal, non-binomial trees can possibly have even further practical advantage.

The memory reclamation problem is to determine, for any given allocated memory node, when there are no more references to the node, allowing it to be safely returned to the memory management system. In a concurrent context, the memory reclamation problem is highly non-trivial, since there may be more than one thread referencing an allocated node unbeknownst to the other threads.

MPI inter-group collective communication patterns can be viewed as bipartite graphs that divide processes into two disjoint groups in which messages are transferred between but not within the groups. Such communication patterns can serve as basic operations for scientific application workflows. In this paper, we present parallel algorithms for inter-group all-to-all broadcast (Allgather) communication with optimal bandwidth for any message size and process number under single-port communication constraints. We implement the algorithms using MPI point-to-point and intra-group collective communication functions and evaluate their performance on the Cori supercomputer at NERSC. Using message sizes ranging from 256B to 64MB, the experiments show a significant performance improvement achieved by our algorithm, which is up to 9.27 times faster than production MPI libraries that adopt the so called root-gathering algorithm.

We present Stamp-it, a new, general, portable, lock-less concurrent memory reclamation scheme with amortized, constant-time (thread-count independent) reclamation overhead. Stamp-it has been implemented and proved correct in the C++ memory model using as weak memory-consistency assumptions as possible. We have (re)implemented six other comparable reclamation schemes. By a detailed performance comparison, we show that Stamp-it performs favorably, sometimes better, but at least as good as these other schemes while being able to reclaim free memory nodes earlier.

Neighborhood collectives were added to the Message Passing Interface (MPI) to better support sparse communication patterns found in many applications. These new collectives encourage more scalable programming styles, and greatly extend the scope of MPI collectives by allowing users to define their own collective communication patterns. In this paper, we describe a new, distributed algorithm for computing improved communication schedules for neighborhood collectives. We show how to discover common process neighborhoods in fully general MPI distributed graph topologies, and how to exploit this information to build message-combining communication schedules for the MPI neighborhood collectives. Our experimental results show considerable performance improvements for application communication topologies of various shapes and sizes. On average, the performance gain is around 50%, but it can also be as much as 71% for topologies with larger numbers of neighbors.

Communication and topology aware process mapping is a powerful approach to reduce communication time in parallel applications with known communication patterns on large, distributed memory systems. We address the problem as a quadratic assignment problem (QAP), and present algorithms to construct initial mappings of processes to processors, and fast local search algorithms to further improve the mappings. By exploiting assumptions that typically hold for applications and modern supercomputer systems such as sparse communication patterns and hierarchically organized communication systems, we obtain significantly more powerful algorithms for these special QAPs. Our multilevel construction algorithms employ perfectly balanced graph partitioning techniques and exploit the given communication system hierarchy in significant ways. We present improvements to a local search algorithm of Brandfass et al. (2013), and further decrease the running time by reducing the time needed to perform swaps in the assignment as well as by carefully constraining local search neighborhoods. We also investigate different algorithms to create the communication graph that is mapped onto the processor network. Experiments indicate that our algorithms not only dramatically speed up local search, but due to the multilevel approach also find much better solutions in practice.

The derived datatype mechanism is a powerful, integral feature of the Message-Passing Interface (MPI) for communicating arbitrarily structured, possibly non-consecutive and non-homogeneous application data. MPI defines a set of derived datatype constructors of increasing generality, which allows to describe arbitrary data layouts in a reasonably compact fashion. The constructors may be applied recursively, leading to tree-like representations of the application data layouts. Efficient derived datatype representations are required for MPI implementations to efficiently access and process structured application data. We study the problem of finding tree-like representations of MPI derived datatypes that are optimal in terms of space and processing cost. More precisely, we consider the so-called MPI Type Reconstruction Problem of determining a least-cost tree-like representation of a given data layout for a given set of constructors. In an additive cost model that accounts for the space consumption of the constructors and lower-bounds the processing costs, we show that the problem can be solved in polynomial time for the full set of MPI datatype constructors. Our algorithm uses dynamic programming and requires the solution of a series of shortest path problems on an incrementally built, directed, acyclic graph.

We examine natural expectations on communication performance using MPI derived datatypes in comparison to the baseline, "raw" performance of communicating simple, noncontiguous data layouts. We show that common MPI libraries sometimes violate these datatype performance expectations, and discuss reasons why this happens, but also show cases where MPI libraries perform well. Our findings are in many ways surprising and disappointing. First, the performance of derived datatypes is sometimes worse than the semantically equivalent packing and unpacking using the corresponding MPI functionality. Second, the communication performance equivalence stated in the MPI standard between a single contiguous datatype and the repetition of its constituent datatype does not hold universally. Third, the heuristics that are typically employed by MPI libraries at type-commit time are insufficient to enforce natural performance guidelines, and better type normalization heuristics may have a significant performance impact. We show cases where all the MPI type constructors are necessary to achieve the expected performance for certain data layouts. We describe our benchmarking approach to verify the datatype performance guidelines, and present extensive verification results for different MPI libraries.

We present a library providing functionality beyond the MPI standard for manipulating application data layouts described by MPI derived datatypes. The main contributions are: a) Constructors for several, new datatypes for describing application relevant data layouts. b) A set of extent-free constructors that eliminate the need for type resizing. c) New navigation and query functionality for accessing individual data elements in layouts described by datatypes, and for comparing layouts. d) Representation of datatype signatures by explicit, associated signature types, as well as functionality for explicit generation of type maps. As a simple application, we implement reduction collectives on noncontiguous, but homogeneous derived datatypes. Some of the proposed functionality could be implemented more efficiently within an MPI library.

A number of concurrent, relaxed priority queues have recently been proposed and implemented. Results are commonly reported for a throughput benchmark that uses a uniform distribution of keys from a large integer range, a balanced mixture of operations, and mostly for single systems. We have conducted more extensive benchmarking of three recent, relaxed priority queues on four different types of systems with different key ranges and distributions. While we can show superior throughput and scalability for our own k-LSM priority queue for the uniform key distribution, the picture changes drastically for other distributions, both with respect to achieved throughput and relative merit of the priority queues. The throughput benchmark alone is thus not sufficient to characterize the performance of concurrent priority queues. Our priority queue, benchmark code and full set of results are publicly available to foster comparison.

This special issue of Concurrency and Computation: Practice and Experience contains revised and extended versions of selected papers presented at the conference Euro-Par 2015.Euro-Par-the European Conference on Parallel Computing-is an annual series of international conferences dedicated to the promotion and advancement of all aspects of parallel and distributed computing.Euro-Par covers a wide spectrum of topics from algorithms and theory to software technology and hardware-related issues, with application areas ranging from scientific to mobile and cloud computing.The major part of the Euro-Par audience consists of researchers in academic institutions, government laboratories and industrial organisations.Euro-Par 2015, the 21st conference in the Euro-Par series, was held in Vienna, Austria.It was organised by the Research Group for Parallel Computing of the Vienna University of Technology (TU Wien).Thirteen broad topics were defined and advertised, covering a large variety of aspects of parallel and distributed computing.The call for papers attracted a total of 190 submissions.The submitted papers were reviewed at least three and, in most cases, four or even more times (four reviews on average).A total of 51 papers were finally accepted for publication.This makes a global acceptance rate of 27 %.The authors of accepted papers came from 21 countries, with the four main contributing countries-the United States, France, Spain and Germany-accounting for a bit more than half of them.Based on the results of the reviews and a majority opinion of the respective topic programme committees, a number of papers were recommended for this special issue.The authors were contacted at the conference and invited to submit revised and extended versions of their papers.These new versions were reviewed independently by three reviewers; two had previously reviewed the conference version, the third had not.Eventually, four papers were accepted for publication.This year, two Euro-Par topics are represented-both covering methods of programming modern computer architectures.Topic 13 on Accelerator Computing is represented with three papers.The paper Performance optimization of sparse matrix-vector multiplication for multi-component PDE-based applications using GPUs, authored by Ahmad Abdelfattah, Hatem Ltaief, David Keyes and Jack Dongarra [1], describes the implementation of a single-GPU and multi-GPU kernel for block-sparse matrix-vector multiplication, a problem that appears in the discretisation of partial differential equations with many dependent variables.The performance of the kernel is measured on a subset of the Florida Sparse Matrix Collection.Especially noted by the reviewers was the uniform interface that applies to a wide range of problem sizes via tunable parameters.This makes it perform efficiently on a wide range of GPU architectures running CUDA.The paper Fast parallel skew and prefix-doubling suffix array construction on the GPU, authored by Leyuan Wang, Sean Baxter and John D. Owens [2], proposes a hybrid GPU implementation of known algorithms for constructing suffix arrays of a string that fits the given GPU architecture best.One highlight pointed out in the reviews is a highly efficient segmented sorting primitive, which is also valuable as independent result.The paper Performance and portability of accelerated lattice Boltzmann applications with OpenACC, authored by Enrico Calore, Jiri Kraus, Sebastiano Fabio Schifano and Raffaele Tripiccione [3], reports on a performance study based on a simple performance model of an OpenACCbased lattice Boltzmann implementation on three different architectures: an NVIDIA GPU, an AMD GPU and a multi-core CPU.The practical relevance of this work was particularly appreciated.

We present a new, concurrent, lock-free priority queue that relaxes the delete-min operation to allow deletion of any of the ρ smallest keys instead of only a minimal one, where ρ is a parameter that can be configured at runtime. It is built from a logarithmic number of sorted arrays, similar to log-structured merge-trees (LSM). For keys added and removed by the same thread the behavior is identical to a non-relaxed priority queue. We compare to state-of-the-art lock-free priority queues with both relaxed and non-relaxed semantics, showing high performance and good scalability of our approach.

Type reconstruction is the process of finding an efficient representation in terms of space and processing time of a data layout as an MPI derived datatype. Practically efficient type reconstruction and normalization is important for high-quality MPI implementations that strive to provide good performance for communication operations involving noncontiguous data. Although it has recently been shown that the general problem of computing optimal tree representations of derived datatypes allowing any of the MPI derived datatype constructors can be solved in polynomial time, the algorithm for this may unfortunately be impractical for datatypes with large counts. By restricting the allowed constructors to vector and index-block type constructors, but excluding the most general MPI_Type_create_struct constructor, the problem can be solved much more efficiently. More precisely, we give a new O(n log n/log log n) time algorithm for finding cost-optimal representations of MPI type maps of length n using only vector and index-block constructors for a simple but flexible, additive cost model. This improves significantly over a previous O(n√n) time algorithm for the same problem, and the algorithm is simple enough to be considered for practical MPI libraries.

No abstract available.

We propose a specification and discuss implementations of collective operations for parallel stencil-like computations that are not supported well by the current MPI 3.1 neighborhood collectives. In our isomorphic, sparse collectives all processes partaking in the communication operation use similar neighborhoods of processes with which to exchange data. Our interface assumes the p processes to be arranged in a d-dimensional torus (mesh) over which neighborhoods are specified per process by identical lists of relative coordinates. This extends significantly on the functionality for Cartesian communicators, and is a much lighter mechanism than distributed graph topologies. It allows for fast, local computation of communication schedules, and can be used in more dynamic contexts than current MPI functionality. We sketch three algorithms for neighborhoods with s source and target neighbors, namely a) a direct algorithm taking s communication rounds, b) a message-combining algorithm that communicates only along torus coordinates, and c) a message-combining algorithm using between [log s] and [log p] communication rounds. Our concrete interface has been implemented using the direct algorithm a). We benchmark our implementations and compare to the MPI neighborhood collectives. We demonstrate significant advantages in set-up times, and comparable communication times. Finally, we use our isomorphic, sparse collectives to implement a stencil computation with a deep halo, and discuss derived datatypes required for this application.

We investigate the use of the derived datatype mechanism of MPI (the Message-Passing Interface) in the implementation of the classic all-to-all communication algorithm of Bruck et al.\ (1997). Through a series of improvements to the canonical implementation of the algorithm we gradually eliminate initial and final processor-local data reorganizations, culminating in a \emph{zero-copy} version that contains no explicit, process-local data movement or copy operations: all necessary data movements are implied by MPI derived datatypes, and carried out as part of the communication operations. We furthermore show how the improved algorithm can be used to solve irregular all-to-all communication problems (that are not too irregular). The Bruck algorithm serves as a vehicle to demonstrate descriptive and performance advantages with MPI datatypes in the implementation of complex algorithms, and discuss shortcomings and inconveniences in the current MPI datatype mechanism. In particular, we use and implement three new derived datatypes (bounded vector, circular vector, and bucket) not in MPI that might be useful in other contexts. We also discuss the role of persistent collectives which are currently not found in MPI for amortizing type creation (and other) overheads, and implement a persistent variant of the \texttt{MPI\_Alltoall} collective.

We present three lock-free data structures for priority task scheduling: a priority work-stealing one, a centralized one with ρ-relaxed semantics, and a hybrid one combining both concepts. With the single-source shortest path (SSSP) problem as example, we show how the different approaches affect the prioritization and provide upper bounds on the number of examined nodes. We argue that priority task scheduling allows for an intuitive and easy way to parallelize the SSSP problem, notoriously a hard task. Experimental evidence supports the good scalability of the resulting algorithm. The larger aim of this work is to understand the trade-offs between scalability and priority guarantees in task scheduling systems. We show that ρ-relaxation is a valuable technique for improving the first, while still allowing semantic constraints to be satisfied: the lock-free, hybrid $k$-priority data structure can scale as well as work-stealing, while still providing strong priority scheduling guarantees, which depend on the parameter k. Our theoretical results open up possibilities for even more scalable data structures by adopting a weaker form of ρ-relaxation, which still enables the semantic constraints to be respected.

Work-stealing systems are typically oblivious to the nature of the tasks they are scheduling. They do not know or take into account how long a task will take to execute or how many subtasks it will spawn. Moreover, task execution order is typically determined by an underlying task storage data structure, and cannot be changed. There are thus possibilities for optimizing task parallel executions by providing information on specific tasks and their preferred execution order to the scheduling system.

We discuss three complementary approaches that can provide both portability and an increased level of abstraction for the programming of heterogeneous multicore systems. Together, these approaches also support performance portability, as currently investigated in the EU FP7 project PEPPHER. In particular, we consider (1) a library-based approach, here represented by the integration of the SkePU C++ skeleton programming library with the StarPU runtime system for dynamic scheduling and dynamic selection of suitable execution units for parallel tasks; (2) a language-based approach, here represented by the Offload-C++ high-level language extensions and Offload compiler to generate platform-specific code; and (3) a component-based approach, specifically the PEPPHER component system for annotating user-level application components with performance metadata, thereby preparing them for performance-aware composition. We discuss the strengths and weaknesses of these approaches and show how they could complement each other in an integrational programming framework for heterogeneous multicore systems.

We show how to extend classical work-stealing to deal with tightly coupled data parallel tasks that can require any number of threads r ≥ 1 for their execution, and term this extension work-stealing with deterministic team-building. As threads become idle they attempt to join a team of threads designated for a task requiring r > 1 threads for its execution, alternatively to steal a task, requiring no central coordination. Team building and stealing are done according to a deterministic hierarchy and involve at most a logarithmic number of possibly randomized steal attempts. Threads attempting to join the team for a task requiring a large number of threads may help smaller teams while waiting for the large team to form. Once a team has been formed the threads can in close coordination execute the data parallel task. Implementation can be done with standard lock-free data structures, and takes only a single extra compare-and-swap (CAS) operation per thread to build a team. In the degenerate case where all tasks require only a single thread, the implementation coincides with a locality aware work-stealing implementation. Using a prototype C++ implementation of our extended work-stealing algorithm, a mixed-mode parallel Quicksort algorithm with a data parallel partitioning step has been implemented. We compare our (improved) implementation of this algorithm on top of our extended work-stealing scheduler to a standard task-parallel implementation with this scheduler, and with Intel Cilk Plus and Threading Building Blocks. In addition, we also compare to the optimized parallel MCSTL Quicksort. Results are shown for a 32-core Intel Nehalem EX system and a 16-core Sun T2+ system supporting up to 128 hardware threads. The mixed-mode parallel algorithm performs consistently better than the fork-join implementation, often significantly.

Abstract The Message‐passing Interface (MPI) standard provides basic means for adaptations of the mapping of MPI process ranks to processing elements to better match the communication characteristics of applications to the capabilities of the underlying systems. The MPI process topology mechanism enables the MPI implementation to rerank processes by creating a new communicator that reflects user‐supplied information about the application communication pattern. With the newly released MPI 2.2 version of the MPI standard, the process topology mechanism has been enhanced with new interfaces for scalable and informative user‐specification of communication patterns. Applications with relatively static communication patterns are encouraged to take advantage of the mechanism whenever convenient by specifying their communication pattern to the MPI library. Reference implementations of the new mechanism can be expected to be readily available (and come at essentially no cost), but non‐trivial implementations pose challenging problems for the MPI implementer. This paper is first and foremost addressed to application programmers wanting to use the new process topology interfaces. It explains the use and the motivation for the enhanced interfaces and the advantages gained even with a straightforward implementation. For the MPI implementer, the paper summarizes the main issues in the efficient implementation of the interface and explains the optimization problems that need to be (approximately) solved by a good MPI library. Copyright © 2010 John Wiley & Sons, Ltd.

Message passing using the Message-Passing Interface (MPI) is at present the most widely adopted framework for programming parallel applications for distributed memory and clustered parallel systems. For reasons of (universal) implementability, the MPI standard does not state any specific performance guarantees, but users expect MPI implementations to deliver good and consistent performance in the sense of efficient utilization of the underlying parallel (communication) system. For performance portability reasons, users also naturally desire communication optimizations performed on one parallel platform with one MPI implementation to be preserved when switching to another MPI implementation on another platform. We address the problem of ensuring performance consistency and portability by formulating performance guidelines and conditions that are desirable for good MPI implementations to fulfill. Instead of prescribing a specific performance model (which may be realistic on some systems, under some MPI protocol and algorithm assumptions, etc.), we formulate these guidelines by relating the performance of various aspects of the semantically strongly interrelated MPI standard to each other. Common-sense expectations, for instance, suggest that no MPI function should perform worse than a combination of other MPI functions that implement the same functionality, no specialized function should perform worse than a more general function that can implement the same functionality, no function with weak semantic guarantees should perform worse than a similar function with stronger semantics, and so on. Such guidelines may enable implementers to provide higher quality MPI implementations, minimize performance surprises, and eliminate the need for users to make special, nonportable optimizations by hand. We introduce and semiformalize the concept of self-consistent performance guidelines for MPI, and provide a (nonexhaustive) set of such guidelines in a form that could be automatically verified by benchmarks and experiment management tools. We present experimental results that show cases where guidelines are not satisfied in common MPI implementations, thereby indicating room for improvement in today's MPI implementations.

The MPI-2 Standard, released in 1997, defined an interface for one-sided communication, also known as remote memory access (RMA). It was designed with the goal that it should permit efficient implementations on multiple platforms and networking technologies, and also in heterogeneous environments and non-cache-coherent systems. Nonetheless, even 12 years after its existence, the MPI-2 RMA interface remains scarcely used for a number of reasons. This paper discusses the limitations of the MPI-2 RMA specification, outlines the goals and requirements for a new RMA API that would better meet the needs of both users and implementers, and presents a strawman proposal for such an API. We also study the tradeoffs facing the design of this new API and discuss how it may be implemented efficiently on both cache-coherent and non-cache-coherent systems.

We discuss issues in designing sparse (nearest neighbor) collective operations for communication and reduction operations in small neighborhoods for the message passing interface (MPI). We propose three such operations, namely a sparse gather operation, a sparse all-to-all, and a sparse reduction operation in both regular and irregular (vector) variants. By two simple experiments we show a) that a collective handle for message scheduling and communication optimization is necessary for any such interface, b) that the possibly different amount of communication between neighbors need to be taken into account by the optimization, and c) illustrate the improvements that are possible by schedules that possess global information compared to implementations that can rely on only local information. We discuss different forms the interface and optimization handles could take. The paper is inspired by current discussion in the MPI Forum.

Multicore processors are currently hitting the market at enormous speed. Multi-processing in all its variants is seen as the way into the future of computational systems and imply parallelism for future applications. The basics of software development are changing when going parallel. One key concept to ensure scalability of today's applications for the future is the idea of using work stealing scheduling systems to ensure load balancing, and re-writing existing software is necessary to exploit that style of programming. The numerous work stealing concepts however differ in form of implementation, interfaces and supported systems. Handling this diversity of systems makes the already complicated process of going parallel even worse. We present a simple but complete work stealing scheduler (TPI - Task Processing Interface) as an example and formulate the requirements to a basic work stealing interface as a first step to an open standard proposal.

We observe that in the past decade parallel processing and parallel algorithmics have disappeared from mainstream computer-science curricula and moved either into advanced graduate courses or into the application domains. This is well illustrated by current textbook availability. The influential book by Cormen, Leiserson and Rivest (1990) in its first edition had a substantial chapter on PRAM algorithmics that was dropped from the second edition (2001), the parallel algorithms book by Jala (1992) is no longer in print, and recent algorithms texts by Kleinberg and Tardos (2005), or Dasgupta et al. (2007) do not touch on parallelism at all. In the past decade it was well possible to complete an advanced computer science degree without exposure to parallel processing, and in particular parallel algorithmics.It is timely for the parallel-processing community to take stock: What does the community have to offer the upcoming generation that will have to deal with parallelism for a much broader range of applications? What are the fundamental paradigms and techniques of the past? How can these be most effectively conveyed, and to whom? Which were the mistakes and wrong turns of the past? How can repetition be avoided? Which problems remain unsolved, and what are the major, new challenges?

Abstract Parallel performance analysis tools must be tested as to whether they perform their task correctly, which comprises at least three aspects. First, it must be ensured that the tools neither alter the semantics nor distort the run‐time behavior of the application under investigation. Next, it must be verified that the tools collect the correct performance data as required by their specification. Finally, it must be checked that the tools perform their intended tasks and detect relevant performance problems. Focusing on the latter (correctness) aspect, testing can be done using synthetic test functions with controllable performance properties, possibly complemented by real‐world applications with known performance behavior. A systematic test suite can be built from synthetic test functions and other components, possibly with the help of tools to assist the user in putting the pieces together into executable test programs. Clearly, such a test suite can be highly useful to builders of performance analysis tools. It is surprising that, up until now, no systematic effort has been undertaken to provide such a suite. In this paper we describe the APART Test Suite (ATS) for checking the correctness (in the above sense) of parallel performance analysis tools. In particular, we describe a collection of synthetic test functions which allows one to easily construct both simple and more complex test programs with desired performance properties. We briefly report on experience with MPI and OpenMP performance tools when applied to the test cases generated by ATS. Copyright © 2006 John Wiley & Sons, Ltd.

We give an overview of the algorithms and implementations in the high-performance MPI libraries MPI/SX and MPI/ES of some of the most important collective operations of MPI (the message passing interface). The infrastructure of MPI/SX makes it easy to incorporate new algorithms and algorithms for common special cases (e.g. a single SX node, or a single MPI process per SX node). Algorithms that are among the best known are employed, and special hardware features of the SX architecture and internode crossbar switch (IXS) are exploited wherever possible. We discuss in more detail the implementation of MPLBarrier, MPLBcast, the MPI reduction collectives, MPI-Alltoall, and the gather/scatter collectives. Performance figures and comparisons to straightforward algorithms are given for a large SX-8 system, and for the Earth Simulator. The measurements show excellent absolute performance, and demonstrate the scalability of MPI/SX and MPI/ES to systems with large numbers of nodes

Summary form only given. We present and implement simple, binomial-tree based algorithms for the gather and scatter operations of MPI (the message passing interface). For small data sets, data are gathered (scattered) in a tree-like fashion. As the size of the data increases, the algorithms gracefully degrade toward the serial algorithm in which the root process gathers (scatters) data from (to) one process after the next. We extend these algorithms to the more difficult irregular gather/scatter operations in which the processes send/receive different amounts of data. The algorithms are furthermore adopted to the hierarchical communication structure of SMP-clusters. We compare the new algorithms to the straightforward, serial implementations of the gather/scatter primitives, and demonstrate substantial improvements both on a 32-node, 2-way SMP cluster, and on a 4-node NEC SX-6 vector supercomputer with 8 processors per node. For the regular gather/scatter operations improvements of a factor of 3 to 7 are achieved for critical data sizes on the SMP-system, and a factor of 3 to 4 on the SX-6. On 256 nodes of the earth simulator the improvement for scattering small data is more than a factor of 60. Comparable improvements are achieved for the irregular operations, despite preprocessing and communication overhead for dynamic tree construction. We discuss issues in modeling and analyzing the performance of the algorithms for the irregular collectives in particular.

Automatic performance tools must of course be tested as to whether they perform their task correctly. Because performance tools are meta-programs, tool testing is more complex than ordinary program testing and comprises at least three aspects. First, it must be ensured that the tools do neither alter the semantics nor distort the run-time behavior of the application under investigation. Next, it must be verified that the tools collect the correct performance data as required by their specification. Finally, it must be checked that the tools indeed perform their intended tasks and detect relevant performance problems. Focusing on the latter (correctness) aspect, testing can be done using synthetic test functions with controllable performance properties, and/or real world applications with known performance behavior. A systematic test suite can be built from synthetic test functions and other components, possibly with the help of tools to assist the user in putting the pieces together into executable test programs. Clearly, such a test suite can be highly useful to builders of performance analysis tools. It is surprising that up till now, no systematic effort has been undertaken to provide such a suite. In this paper we discuss the initial design of a test suite for checking the correctness (in the above sense) of automatic performance analysis tools. In particular, we describe a collection of synthetic test functions which allows to easily construct both simple and more complex test programs with desired performance properties.

The Message Passing Interface (MPI) is designed as an architecture independent interface for parallel programming in the shared-nothing, message passing paradigm. We briefly summarize basic requirements to a high-quality implementation of MPI for efficient programming of SMP clusters and related architectures, and discuss possible, mild extensions of the topology functionality of MPI, which, while retaining a high degree of architecture independence, can make MPI more useful and efficient for message-passing programming of SMP clusters. We show that the discussed extensions can all be implemented on top of MPI with very little environmental support.

Many applications of parallel I/O perform non-contiguous file accesses: instead of accessing a single (large) block of data in a file, a number of (smaller) blocks of data scattered throughout the file needs to be accessed in each logical I/O operation. However, only few file system interfaces directly support this kind of non-contiguous file access. In contrast, the most commonly used parallel programming interface, MPI, incorporates a exible model of parallel I/O through its MPI-IO interface. With MPI-IO, arbitrary non-contiguous file accesses are supported in a uniform fashion by the use of derived MPI datatypes set up by the user to re ect the desired I/O pattern. Despite a considerable amount of recent work in this area, current MPI-IO implementations suffer from low performance of such non-contiguous accesses when compared to the performance of the storage system for contiguous accesses. In this paper we analyze an important bottleneck in the efficient handling of non-contiguous access patterns in current implementations of MPI-IO. We present a new technique, termed listless I/O, that can be incorporated into MPI-IO implementations like the well-known ROMIO implementation, and completely eliminates this bottleneck. We have implemented the technique in MPI/SX, the MPI implementation for the NEC SX-series of parallel vector computers. Results with a synthetic benchmark and an application kernel show that listless I/O is able to increase the bandwidth for non-contiguous file access by sometimes more than a factor of 500 when compared to the traditional approach.

The topology functionality of the Message Passing Interface (MPI) provides a portable, architecture-independent means for adapting application programs to the communication architecture of the target hardware. However, current MPI implementations rarely go beyond the most trivial implementation, and simply performs no process remapping. We discuss the potential of the topology mechanism for systems with a hierarchical communication architecture like clusters of SMP nodes. The MPI topology functionality is a weak mechanism, and we argue about some of its shortcomings. We formulate the topology optimization problem as a graph embedding problem , and show that for hierarchical systems it can be solved by graph partitioning . We state the properties of a new heuristic for solving both the embedding problem and the "easier" graph partitioning problem. The graph partitioning based framework has been fully implemented in MPI/SX for the NEC SX-series of parallel vector computers. MPI/SX is thus one of very few MPI implementations with a non-trivial topology functionality. On a 4 node NEC SX-6 significant communication performance improvements are achieved with synthetic MPI benchmarks.

Performance analysis is an important step in tuning performance critical applications. It is a cyclic process of measuring and analyzing performance data which is driven by the programmers hypotheses on potential performance problems. Currently this process is controlled manually by the programmer. The implicit knowledge applied in this cyclic process must be formalized in order to be reused in the automation of performance analysis tools. This article describes the performance property specification language ASL developed in the APART Esprit IV working group. ASL allows the specification of performance data via an object model and of performance properties via a specially designed notation. Performance bottlenecks can then be identified based on the specification since bottlenecks are viewed as performance properties with a huge negative impact. We present the ASL language in the context of MPI applications.

We describe the MPI/SX implementation of the MPI-2 standard for one-sided communication (Remote Memory Access) for the NEC SX-5 vector supercomputer. MPI/SX is a non-threaded implementation of the full MPI-2 standard. Essential features of the implementation are presented, including the synchronization mechanisms, the handling of communication windows in global shared and in process local memory, as well as the handling of MPI derived datatypes. In comparative benchmarks the data transfer operations for one-sided communication and point-to-point message passing show very similar performance, both when data reside in global shared and when in process local memory. Derived datatypes, which are of particular importance for applications using one-sided communications, impose only a modest overhead and can be used without any significant loss of performance. Thus, the MPI/SX programmer can freely choose either the message passing or the one-sided communication model, whichever is most convenient for the given application.

Article Free Access Share on A library of basic PRAM algorithms and its implementation in FORK Authors: Christoph W. Kessler FB 4 Informatik, Universität Trier D-54286 Trier, Germany FB 4 Informatik, Universität Trier D-54286 Trier, GermanyView Profile , Jesper Larsson Träff Max-Planck-Institut für Informatik D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik D-66123 Saarbrücken, GermanyView Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 193–195https://doi.org/10.1145/237502.237545Online:24 June 1996Publication History 4citation220DownloadsMetricsTotal Citations4Total Downloads220Last 12 Months6Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present an implementation of the maximum flow algorithm of Shiloach and Vishkin (1982) on a distributed system without shared memory. This algorithm is a clever variation of Karzanov's algorithm, has a clear parallel orientation, and possesses features which make it an interesting candidate for distributed implementation also. The paper briefly describes the algorithm and discusses implementation issues which are relevant regardless of the specifics of the distributed system at hand: distribution of data structures (graph, queue, stacks) and reduction of communication volume. Experiments with the distributed algorithm on a 16 processor transputer system indicate that speed-up is indeed possible in practice: absolute speed-up of 2 to 3 on 8 processors have been consistently achieved on random graphs. But first and foremost the experiments pinpoint problems inherent in a synchronized implementation. Possible improvements are discussed.