Julian Shun · 2015
Parallelism is the key to achieving high performance in computing. How-ever, writing efficient and scalable parallel programs is notoriously difficult, and often requires significant expertise. To address this challenge, it is crucial to provide programmers with high-level tools to enable them to develop solutions efficiently, and at the same time emphasize the theoretical and practical aspects of algorithm design to allow the solutions developed to run efficiently under all possible settings. This thesis addresses this challenge using a three-pronged approach consisting of the design of shared-memory programming techniques, frameworks, and algorithms for important problems in computing. The thesis provides evidence that with appropriate programming techniques, frameworks, and algorithms, shared-memory programs can be simple, fast, and scalable, both in theory and in practice. The results developed in this thesis serve to ease the transition into the multicore era. The first part of this thesis introduces tools and techniques for deterministic
Cited by 0
Diehl, Patrick, Taylor, Chris · Zenodo (CERN European Organization for Nuclear Research) · 2023
What's Changed added riscv/rv64g support by @ct-clmsn in https://github.com/STEllAR-GROUP/parallelnumericalintegration/pull/2 New Contributors @ct-clmsn made their first contribution in https://github.com/STEllAR-GROUP/parallelnumericalintegration/pull/2 <strong>Full Changelog</strong>: https://github.com/STEllAR-GROUP/parallelnumericalintegration/compare/v0.1.0...v0.2.0
Cited by 1Open access
R. R. Oldehoeft, D.C. Cann · IEEE Software · 1988
An applicative language, SISAL (streams and iteration in a single-assignment language), is used to examine how effective the applicative approach can be in programming parallel computers. SISAL is a research language for investigating issues in parallel processing, especially for numerical computing. A prototype implementation of SISAL is described, focusing on loops and streams and on microtasking software. Performance results are reported for Livermore kernel 1, the Sieve prime finder, insertion sort, Batcher sort, the Simple hydrodynamics code, and the PSPhot photon-transport code.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 31
A. Scherer · Repository for Publications and Research Data (ETH Zurich) · 2001
Cited by 1Open access
K.H. Warren, Brent Gorda · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1991
The Parallel Data Distribution Preprocessor, PDDP, exploits the cycle time of local shared memory blocks to achieve efficient data parallelization on a MIMD distributed shared memory machine. Shared memory arrays are distributed among the processors. PDDP treats a subset of Fortran D primitives and provides semi-automatic parallelization when Fortran 90 array syntax is used.
Cited by 0
Joe Throop · Computer · 1999
The paper discusses OpenMP, an emerging standard for shared-memory parallelism that has considerable industry support. Large corporations such as IBM, Intel, and Silicon Graphics are building products to support the standard and also participating in its development.
Cited by 4
Gopal Gupta, Bharat Jayaraman · The Journal of Logic Programming · 1993
Cited by 26
Patrick Diehl, Steven R. Brandt, Hartmut Kaiser · Lecture notes in computer science · 2023
Cited by 6Open access
AJ Lindeman · 2010
Although much has been written about the “multi-core discontinuity”, and the impact on mathematical software, see, for example, [KD, LM], the full benefits to quantitative finance have yet to be realized. The purpose of this paper is to highlight the numerical structure of some common fixed income modeling problems with the aim of demonstrating how shared-memory parallelism may be brought to bear on improving performance, ultimately allowing us to calibrate larger and more complete models sufficiently fast to be useful in market making and risk management.
Cited by 6
Patrick Diehl, Steven R. Brandt, Hartmut Kaiser · arXiv (Cornell University) · 2023
Parallel programming remains a daunting challenge, from the struggle to express a parallel algorithm without cluttering the underlying synchronous logic, to describing which devices to employ in a calculation, to correctness. Over the years, numerous solutions have arisen, many of them requiring new programming languages, extensions to programming languages, or the addition of pragmas. Support for these various tools and extensions is available to a varying degree. In recent years, the C++ standards committee has worked to refine the language features and libraries needed to support parallel programming on a single computational node. Eventually, all major vendors and compilers will provide robust and performant implementations of these standards. Until then, the HPX library and runtime provides cutting edge implementations of the standards, as well as proposed standards and extensions. Because of these advances, it is now possible to write high performance parallel code without custom extensions to C++. We provide an overview of modern parallel programming in C++, describing the language and library features, and providing brief examples of how to use them.
Cited by 0Open access
Jean-Yves L’Excellent, Mohamed W. Sid-Lakhdar · HAL (Le Centre pour la Communication Scientifique Directe) · 2013
We study the adaptation of a parallel distributed-memory solver towards a shared-memory code, targeting multi-core architectures. The advantage of adapting the code over a new design is to fully benefit from its numerical kernels, range of functionalities and internal features. Although the studied code is a direct solver for sparse systems of linear equations, the approaches described in this paper are general and could be useful to a wide range of applications. We show how existing parallel algorithms can be adapted to an OpenMP environment while, at the same time, also relying on third-party optimized multithreaded libraries. We propose simple approaches to take advantage of NUMA architectures, and original optimizations to limit thread synchronization costs. For each point, the performance gains are analyzed in detail on test problems from various application areas.
Cited by 4Open access
Nicholas J. Dingle · MIMS EPrints (University of Southampton) · 2011
Multicore CPUs are now found in desktops, servers and supercomputers but many existing parallel performance analysis tools were designed for the single-core distributed-memory world. We investigate the practicality of taking an existing tool, namely the HYDRA response time analyser, and parallelising it with OpenMP to produce a multithreaded implementation suitable for execution on multicore shared-memory machines. We discuss the amount of software engineering work required and show that only a small number of lines of code need to be added to achieve dramatic speed-ups over the serial version. We also compare the run-times of our OpenMP-parallelised version with existing MPI-parallelised code on the same hardware.
Cited by 1
Diehl, Patrick, Taylor, Chris · Zenodo (CERN European Organization for Nuclear Research) · 2023
What's Changed Pine64 Star64 by @ct-clmsn in https://github.com/STEllAR-GROUP/parallelnumericalintegration/pull/3 <strong>Full Changelog</strong>: https://github.com/STEllAR-GROUP/parallelnumericalintegration/compare/v0.2.0...v0.2.1
Cited by 0Open access
Daniel M. Berry · Acta Informatica · 1985
Cited by 4
Amittai Aviram, Bryan Ford, Yu Zhang · 2013
Recent interest in deterministic parallelism has yielded new deterministic programming languages, which offer promising features but require rewriting existing code, and deterministic schedulers, which emulate existing thread APIs but do not eliminate races from the basic programming model. Workspace consistency (WC) is a new synchronization and memory consistency model that offers a “naturally deterministic, ” race-free programming model that can be adopted in both new or existing languages. WC’s basic semantics are inspired by—and intended to be as easily understood as— the “parallel assignment ” construct in sequential languages such as Perl and JavaScript, where concurrent threads always read their inputs before writing shared outputs. Prototype implementations of a restricted form of WC already exist, supporting only strictly hierarchical fork/join-style synchronization, but this paper develops and explores the model in more detail and extends it to support non-hierarchical synchronization patterns such as producer/consumer pipelines and futures. 1
Cited by 0
Amittai Aviram, Bryan Ford · arXiv (Cornell University) · 2009
The difficulty of developing reliable parallel software is generating\ninterest in deterministic environments, where a given program and input can\nyield only one possible result. Languages or type systems can enforce\ndeterminism in new code, and runtime systems can impose synthetic schedules on\nlegacy parallel code. To parallelize existing serial code, however, we would\nlike a programming model that is naturally deterministic without language\nrestrictions or artificial scheduling. We propose "deterministic consistency",\na parallel programming model as easy to understand as the "parallel assignment"\nconstruct in sequential languages such as Perl and JavaScript, where concurrent\nthreads always read their inputs before writing shared outputs. DC supports\ncommon data- and task-parallel synchronization abstractions such as fork/join\nand barriers, as well as non-hierarchical structures such as producer/consumer\npipelines and futures. A preliminary prototype suggests that software-only\nimplementations of DC can run applications written for popular parallel\nenvironments such as OpenMP with low (<10%) overhead for some applications.\n
Cited by 0Open access
David K. Lowenthal, Vincent W. Freeh, Gregory R. Andrews · Concurrency Practice and Experience · 1998
A coarse-grain parallel program typically has one thread (task) per processor, whereas a fine-grain program has one thread for each independent unit of work. Although there are several advantages to fine-grain parallelism, conventional wisdom is that coarse-grain parallelism is more efficient. This paper illustrates the advantages of fine-grain parallelism and presents an efficient implementation for shared-memory machines. The approach has been implemented in a portable software package called Filaments, which employs a unique combination of techniques to achieve efficiency. The performance of the fine-grain programs discussed in this paper is always within 13% of a hand-coded coarse-grain program and is usually within 5%. © 1998 John Wiley & Sons, Ltd.
Cited by 0
David K. Lowenthal Ý, Vincent W. Freeh Þ, Gregory R. Andrews Ü · 2001
A coarse-grain parallel program typically has one thread (task) per processor, whereas a fine-grain program has one thread for each independent unit of work. Although there are several advantages to fine-grain parallelism, conventional wisdom is that coarse-grain parallelism is more efficient. This paper illustrates the advantages of fine-grain parallelism and presents an efficient implementation for shared-memory machines. The approach has been implemented in a portable software package called Filaments, which employs a unique combination of techniques to achieve efficiency. The performance of the fine-grain programs discussed in this paper is always within 13 % of a hand-coded coarse-grain program and is usually within 5 percent. 1
Cited by 0
Sanjay Rajopadhye, Tomofumi Yuki · 2013
With the introduction of multi-core processors, motivated by power and energy concerns, parallel processing has become main-stream. Parallel programming is much more difficult due to its non-deterministic nature, and because of parallel programming bugs that arise from non-determinacy. One solution is automatic parallelization, where it is entirely up to the compiler to efficiently parallelize sequential programs. However, automatic parallelization is very difficult, and only a handful of successful techniques are available, even after decades of research.
Automatic parallelization for distributed memory architectures is even more problematic in that it requires explicit handling of data partitioning and communication. Since data must be partitioned among multiple nodes that do not share memory, the original memory allocation of sequential programs cannot be directly used. One of the main contributions of this dissertation is the development of techniques for generating distributed memory parallel code with parametric tiling.
Our approach builds on important contributions to the polyhedral model, a mathematical framework for reasoning about program transformations. We show that many affine control programs can be uniformized only with simple techniques. Being able to assume uniform dependences significantly simplifies distributed memory code generation, and also enables parametric tiling. Our approach implemented in the AlphaZ system, a system for prototyping analyses, transformations, and code generators in the polyhedral model. The key features of AlphaZ are memory re-allocation, and explicit representation of reductions.
We evaluate our approach on a collection of polyhedral kernels from the PolyBench suite, and show that our approach scales as well as PLuTo, a state-of-the-art shared memory automatic parallelizer using the polyhedral model.
Automatic parallelization is only one approach to dealing with the non-deterministic nature of parallel programming that leaves the difficulty entirely to the compiler. Another approach is to develop novel parallel programming languages. These languages, such as X10, aim to provide highly productive parallel programming environment by including parallelism into the language design. However, even in these languages, parallel bugs remain to be an important issue that hinders programmer productivity.
Another contribution of this dissertation is to extend the array dataflow analysis to handle a subset of X10 programs. We apply the result of dataflow analysis to statically guarantee determinism. Providing static guarantees can significantly increase programmer productivity by catching questionable implementations at compile-time, or even while programming.
Cited by 0
Vincent Freeh, Vincent W. Freeh, David K. Lowenthal et al. · 1996
A coarse-grain parallel program typically has one thread (task) per processor, whereas a fine-grain program has one thread for each independent unit of work. Although there are several advantages to fine-grain parallelism, conventional wisdom is that coarsegrain parallelism is more efficient. This paper illustrates the advantages of fine-grain parallelism and presents an efficient implementation for shared-memory machines. The approach has been implemented in a portable software package called Filaments, which employs a unique combination of techniques to achieve efficiency. The performance of the fine-grain programs discussed in this paper is always within 13% of a hand-coded coarse-grain program and is usually within 5 percent. January 29, 1996 Department of Computer Science The University of Arizona Tucson, AZ 85721 1 This work was supported by NSF grants CCR-9415303 and CDA-8822652. 1 Introduction The typical approach to writing a parallel program for a p-processor machine is t...
Cited by 0