A Cost Calculus for Parallel Functional Programming
Journal of Parallel and Distributed ComputingPublished 1 July 1995
David B. Skillicorn, Wentong Cai
Citations71
SJR quartileQ1
SJR score0.98
SNIP1.35
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 work presents a strategy for building cost calculi for skeleton-based programming languages which can be used for derivational software development and which deals in a pragmatic way with the difficulties of composition.
Abstract
Building a cost calculus for a parallel program development environment is difficult because of the many degrees of freedom available in parallel implementations and because of difficulties with compositionality. We present a strategy for building cost calculi for skeleton-based programming languages which can be used for derivational software development and which deals in a pragmatic way with the difficulties of composition. The approach is illustrated for the Bird-Meertens theory of lists, a parallel functional language with an associated equational transformation system.
Keywords
Computer Science
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.
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.
ACM Computing SurveysCompiler transformations for high-performance computing
812 Citations1994David F. Bacon, Susan L. Graham +1 more
This survey is a comprehensive overview of the important high-level program restructuring techniques for imperative languages, such as C and Fortran, and describes the purpose of each transformation, how to determine if it is legal, and an example of its application.
An Introduction to the Theory of Lists
606 Citations1987Richard Bird
In these lectures a notation and a calculus for specifying and manipulating computable functions over lists are introduced, used to derive efficient solutions for a number of problems, including problems in text processing.
Vector models for data-parallel computing
464 Citations1990Guy E. Blelloch
A model of parallelism that extends and formalizes the Data-Parallel model on which the Connection Machine and other supercomputers are based is described, and it is argued that data-parallel models are not only practical and can be applied to a surprisingly wide variety of problems, they are also well suited for very-high-level languages and lead to a concise and clear description of algorithms and their complexity.
Lecture notes in computer scienceParallel programming using skeleton functions
275 Citations1993John Darlington, A. J. Field +5 more
Performance will be generally poor unless the issue of resource allocation is addressed explicitly, diminishing the advantage of using a functional language in the first place.
Lectures on Constructive Functional Programming
219 Citations1989Richard Bird
This work hopes to show that a functional approach to the problem of systematically calculating programs from their specifications can take its place alongside other methodologies.
Acta InformaticaRandomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
211 Citations1984Kurt Mehlhorn, Uzi Vishkin
The present paper provides a comprehensive study of algorithms which are designed for shared memory models of parallel computation (PRAMs) in which processors are allowed to have fairly unrestricted access patterns to the shared memory.
Lecture notes in computer scienceLoop parallelization in the polytope model
192 Citations1993Christian Lengauer
The polytope model for loop parallelization has its origin in systolic design, but it applies in more general settings and methods based on it will become a part of future parallelizing compilers.
Future Generation Computer SystemsA methodology for the development and the support of massively parallel programs
67 Citations1992Marco Danelutto, Roberto Di Meglio +3 more
This work presents a methodology to easily write efficient, high performance and portable massively parallel programs, based on the definition of a new explicitly parallel programming language, namely P 3 L, and of a set of compiling tools that perform automatic adaptation of the program features to the target architecture hardware.
IEEE Transactions on ComputersScans as primitive parallel operations
47 Citations1989Guy E. Blelloch
A study of the effects of adding two scan primitives as unit-time primitives to PRAM (parallel random access machine) models is presented and it is shown that the primitives improve the asymptotic running time of many algorithms by an O(log n) factor, greatly simplifying the description of many technologies.
International Journal of Parallel ProgrammingModels for practical parallel computation
41 Citations1991David B. Skillicorn
It is concluded that data parallelism is a style with much to commend it, and the Bird-Meertens formalism as a coherent approach to data parallel programming is discussed.
Parallel programming using functional languages
41 Citations1991Paul Roe
This thesis investigates parallel programming using functional languages from a programming perspective, and shows that some aspects of Squigol are suitable for parallel program derivation, while others aspects are specifically orientated towards sequential algorithm derivation.
Science of Computer ProgrammingFormal derivation of a pattern matching algorithm
35 Citations1989Richard Bird, Jeremy Gibbons +1 more
This paper is devoted to the synthesis of a functional version of the Knuth-MorrisPratt algorithm for pattern matching, and the derivation makes use of the calculus of lists described by Bird.
Size and access inference for data-parallel programs
30 Citations1991Siddhartha Chatterjee, Guy E. Blelloch +1 more
Optimally Universal Parallel Computers
27 Citations1989Leslie G. Valiant
Lecture notes in computer scienceThe data parallel programming model: A semantic perspective
22 Citations1996Luc Bougé
It is argued that parallel computing often makes little distinction between the execution model and the programming model, which results in poor programming and low portability, and data parallelism can be seen as a way out of this difficulty.
Mechanical analysis of program complexity
15 Citations1985Daniel Le Métayer
The ACE (for Automatic Complexity Evaluator) system is presented, which is able to analyse reasonably large programs like sorting programs or numerical programs in a fully mechanical way and describes the operations performed and its implementation.
Parallel Processing LettersCALCULATING RECURRENCES USING THE BIRD-MEERTENS FORMALISM
15 Citations1995Wentong Cai, David B. Skillicorn
New operators for the theory of lists that compute generalized recurrences are built that have logarithmic parallel time complexity and are illustrated by deriving a parallel solution to the maximum segment sum problem.
Science of Computer ProgrammingRewriting systems on FP expressions to reduce the number of sequences yielded
14 Citations1986Françoise Bellegarde
The paper relates the experience in using REVE to process a large set of equations and shows the actual limitations, and proposes transformation rules based on the algebra of functional programs.