Estimating parallel performance, a skeleton-based approach
Published 25 September 2010
Oleg Lobachev, Rita Loogen
Citations5
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper estimates parallel execution times, based on identifying separate "parts" of the work done by parallel programs, using an algorithmic skeletons approach, and analyses the values for parallel penalty both for growing input size and for increasing numbers of processing elements.
Abstract
In this paper we estimate parallel execution times, based on identifying separate "parts" of the work done by parallel programs. We assume that programs are described using algorithmic skeletons. Therefore our runtime analysis works without any source code inspection. The time of parallel program execution is expressed in terms of the sequential work and the parallel penalty. We measure these values for different problem sizes and numbers of processors and estimate them for unknown values in both dimensions. This allows us to predict parallel execution time for unknown inputs and non-available processor numbers.
Keywords
Computer Science
Journal of the American Statistical AssociationRobust Locally Weighted Regression and Smoothing Scatterplots
10,938 Citations1979William S. Cleveland
Visual, computational, and statistical issues of robust locally weighted regression are discussed and several examples, including data on lead intoxication, are used to illustrate the methodology.
Annual Review of Fluid MechanicsLATTICE BOLTZMANN METHOD FOR FLUID FLOWS
7,231 Citations1998Shiyi Chen, Gary D. Doolen
An overview of the lattice Boltzmann method, a parallel and efficient algorithm for simulating single-phase and multiphase fluid flows and for incorporating additional physical complexities, is presented.
Journal of the American Statistical AssociationLocally Weighted Regression: An Approach to Regression Analysis by Local Fitting
5,486 Citations1988William S. Cleveland, Susan J. Devlin
Validity of the single processor approach to achieving large scale computing capabilities
4,200 Citations1967Gene M. Amdahl
Communications of the ACMA bridging model for parallel computation
3,680 Citations1990Leslie G. Valiant
The bulk-synchronous parallel (BSP) model is introduced as a candidate for this role, and results quantifying its efficiency both in implementing high-level language features and algorithms, as well as in being implemented in hardware.
The Landscape of Parallel Computing Research: A View from Berkeley
1,993 Citations2006Krste Asanović, Ras Bodik +9 more
The parallel landscape is frame with seven questions, and the following are recommended to explore the design space rapidly: • The overarching goal should be to make it easy to write programs that execute efficiently on highly parallel computing systems • The target should be 1000s of cores per chip, as these chips are built from processing elements that are the most efficient in MIPS (Million Instructions per Second) per watt, MIPS per area of silicon, and MIPS each development dollar.
Choice Reviews OnlineIntroduction to parallel computing
1,857 Citations2004
Message Passing Interface, POSIX threads and OpenMP have been selected as programming models and the evolving application mix of parallel computing is reflected in various examples throughout the book.
LogP: towards a realistic model of parallel computation
1,504 Citations1993David Culler, Richard M. Karp +6 more
A new parallel machine model, called LogP, is offered that reflects the critical technology trends underlying parallel computers and is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers.
ComputerAmdahl's Law in the Multicore Era
1,229 Citations2008Mark D. Hill, Michael R. Marty
Augmenting Amdahl's law with a corollary for multicore hardware makes it relevant to future generations of chips with multiple processor cores.
Parallelism in random access machines
880 Citations1978Steven Fortune, James Wyllie
A model of computation based on random access machines operating in parallel and sharing a common memory is presented and can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded Turing machines.
CERN Document Server (European Organization for Nuclear Research)Algorithmic skeletons : structured management of parallel computation
876 Citations1989Murray Cole
This book introduces a new approach to the design and implementation of software systems which will help users of large scale parallel systems coordinate many concurrent activities toward a single goal and proposes a selection of independent algorithmic skeletons which describes the structure of a particular style of algorithm.
Communications of the ACMProgramming parallel algorithms
449 Citations1996Guy E. Blelloch
This research on parallel algorithms has not only improved the general understanding of par-allelism but in several cases has led to improvements in sequential algorithms.
SIAM Journal on Scientific and Statistical ComputingDevelopment of Parallel Methods for a $1024$-Processor Hypercube
422 Citations1988John L. Gustafson, G.R. Montry +1 more
The scaled-problem paradigm better reveals the capabilities of large ensembles, and permits detection of subtle hardware-induced load imbalances that may become increasingly important as parallel processors increase in node count.
Lecture notes in computer scienceEvaluating the Performance of Skeleton-Based High Level Parallel Programs
348 Citations2004Anne Benoît, Murray Cole +2 more
This paper shows how to evaluate the performance of skeleton-based high level parallel programs, and a tool which generates auto- matically a set of models and solves them is presented, proving the efficiency of this approach.
ACM SIGPLAN NoticesLogP: towards a realistic model of parallel computation
336 Citations1993David Culler, Richard M. Karp +6 more
IEEE Parallel & Distributed Technology Systems & ApplicationsIsoefficiency: measuring the scalability of parallel algorithms and architectures
313 Citations1993Ananth Grama, Aman Gupta +1 more
Patterns and Skeletons for Parallel and Distributed Computing
208 Citations2003Fethi Rabhi, Sergei Gorlatch
This chapter discusses Skeleton-based Programming Environments, a Programming Methodology with Skeletons and Collective Operations, and multi-paradigm and Design Pattern Approaches for HW/SW Design and Reuse.
Journal of Parallel and Distributed ComputingAnalyzing Scalability of Parallel Algorithms and Architectures
207 Citations1994V. Kumar, Aman Gupta
The objectives of this paper are to critically assess the state of the art in the theory of scalability analysis, and to motivate further research on the development of new and more comprehensive analytical tools to study the scalability of parallel algorithms and architectures.
Journal of Functional ProgrammingParallel functional programming in Eden
162 Citations2005Rita Loogen, Yolanda Ortega-Mallén +1 more
Introduction to parallel computing
93 Citations2003Grama, Ananth
Analytical ChemistryTime and Length Scales of Eddy Dispersion in Chromatographic Beds
72 Citations2009Siarhei Khirevich, Alexandra Höltzel +2 more
High-resolution numerical analysis of flow and mass transport in computer-generated bulk (unconfined) packings of monosized, nonporous, incompressible, spherical particles and complementary confined cylindrical packings with a cylinder-to-particle diameter ratio of d(c)/d(p) = 20 resolves time and length scales as well as the magnitude of individual contributions to eddy dispersion in chromatographic beds.
IEEE Computer Society Press eBooksIsoefficiency: measuring the scalability of parallel algorithms and architectures
72 Citations1995Ananth Grama, Anshul Gupta +1 more
Parallelism Abstractions in Eden
40 Citations2003Rita Loogen, Yolanda Ortega +3 more
In this chapter two important abstractions have contributed to create a reliable programming methodology for industrial-strength programs: functional abstraction and data abstraction.
Analytical ChemistryLarge-Scale Simulation of Flow and Transport in Reconstructed HPLC-Microchip Packings
39 Citations2009Siarhei Khirevich, Alexandra Höltzel +3 more
Porosity distributions and fluid flow velocity profiles for the reconstructed microchip packings are presented and analyzed and it is shown by comparison to experimental separation efficiencies that the simulated data genuinely reflect the general dispersion behavior of the real-life HPLC-micro chip packings.
Visualizing Parallel Functional Program Runs: Case Studies with the Eden Trace Viewer.
24 Citations2007Jost Berthold, Rita Loogen
Parallel functional programming at two levels of abstraction
19 Citations2001Ricardo Peña, Fernando Rubio
This paper presents several skeletons of Eden, most of them well-known, covering a wide range of parallel structures, and examples of application programming are shown, including predicted and actual results on a Beowulf cluster.
Concurrency Practice and ExperiencePredicting the execution time of message passing models
15 Citations1999José L. Roda, C. Rodrı́guez +2 more
Parallel algorithms and applicationsSTATIC PERFORMANCE PREDICTION OF SKELETAL PARALLEL PROGRAMS
14 Citations2002Yasushi Hayashi, Murray Cole
This work constitutes the first completely static system to account for both computation and communication in such a context and presents details of the language and its BSP implementation strategy together with an account of the analysis mechanism.
Parallel Processing LettersSkeletons, BSP and Performance Portability
8 Citations2001Andrea Zavanella⋆
Parallel Processing LettersSKELETONS, BSP AND PERFORMANCE PORTABILITY
5 Citations2001Andrea Zavanella⋆
The paper claims that an intermediate model embedding the main performance features of the target architecture facilitates performance portability across parallel architectures.
Lecture notes in computer scienceImplementing Data Parallel Rational Multiple-Residue Arithmetic in Eden
3 Citations2010Oleg Lobachev, Rita Loogen
This work combines two known results in a novel manner, which lifts an integral residue system to fractions and generalises a single-Residue system to a multiple-residue one, resulting in a rational multi-reside system.