HDC A Higher-Order Language for Divide-and-Conquer
Parallel Processing LettersPublished 1 September 2001
Christoph Herrmann
Citations36
SJR quartileQ4
SJR score0.17
SNIP0.26
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
The higher-order functional style for the parallel programming of algorithms is proposed, and two small examples, the n queens problem and Karatsuba's polynomial multiplication, are presented to demonstrate the programming comfort and the speedup one can obtain.
Abstract
We propose the higher-order functional style for the parallel programming of algorithms. The functional language HDC, a subset of the language Haskell, facilitates the clean integration of skeletons into a functional program. Skeletons are predefined programming schemata with an efficient parallel implementation. We report on our compiler, which translates HDC programs into C+MPI, especially on the design decisions we made. Two small examples, the n queens problem and Karatsuba's polynomial multiplication, are presented to demonstrate the programming comfort and the speedup one can obtain.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Principal type-schemes for functional programs
1,096 Citations1982Lúıs Damas, Robin Milner
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage.
ACM Transactions on Programming Languages and SystemsAn Efficient Unification Algorithm
772 Citations1982Alberto Martelli, Ugo Montanari
A new unification algorithm, characterized by having the acyclicity test efficiently embedded into it, is derived from the nondeterministic one, and a PASCAL implementation is given.
Journal of Functional ProgrammingAlgorithm + strategy = parallelism
246 Citations1998Phil Trinder, Kevin Hammond +2 more
Evaluation strategies are introduced: lazy higher-order functions that control the parallel evaluation of non-strict functional languages that can be used to model a wide range of commonly used programming paradigms, including divide-and-conquer parallelism, pipeline Parallelism, producer/ consumer parallelism and data-oriented parallelism.
Science of Computer ProgrammingDecomposition of distributed programs into communication-closed layers
206 Citations1982Tzilla Elrad, Nissim Francez
The safe decomposition of a distributed program into communication closed layers is suggested as a superstructure of its decomposition into a collection of communicating processes.
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.
Concurrency Practice and Experience<i>P</i><sup>3</sup><i>L</i>: A structured high‐level parallel language, and its structured support
160 Citations1995Bruno Bacci, Marco Danelutto +3 more
Functional Programming for Loosely-Coupled Multiprocessors
86 Citations1989Paul H. J. Kelly
This book proposes a new high level approach to programming that addresses the pragmatic issue of how a computation is distributed across a machine, based on functional programming and has significant advantages over existing comparable approaches, extending the domain of functional programming to include computer architectures in which communication costs are not negligible.
Parallel skeletons for structured composition
86 Citations1995John Darlington, Yike Guo +2 more
A straightforward solution to the problems of compositional parallel programming by using skeletons as the uniform mechanism for structured composition, which provides a natural integration of the compositional programming approach with the data parallel programming paradigm.
Journal of Parallel and Distributed ComputingDivide and conquer under global constraints: A solution to the N-queens problem
53 Citations1989Bruce Abramson, Moti Yung
This paper describes a new divide-and-conquer algorithm that solves both problems and investigates the relationship between them, an important method of algorithm design: detailed combinatorial analysis of an overconstrained variation can reveal solutions to the corresponding original problem.
Type-driven defunctionalization
50 Citations1997Jeffrey Bell, Françoise Bellegarde +1 more
A defunctionalization transformation which preserves typability is presented, and the transformation imposes no restriction on functional arguments of recursive functions, and it handles functions as results as well as functions encapsulated in constructors.
Optimization rules for programming with collective operations
40 Citations2003Sergei Gorlatch, C. Wedler +1 more
A formal framework for reasoning about collective operations, a set of optimization rules which save communications by fusing several collective operations into one, performance estimates, and a simple case study with machine experiments are presented.
Journal of Functional ProgrammingParallelization of divide-and-conquer by translation to nested loops
16 Citations1999Christoph Herrmann, Christian Lengauer
The aim is to identify a subclass of divide-and-conquer algorithms with an efficient parallel implementation which can be viewed as a static space-time mapping, and the correctness of the compile-time transformations is proved by equational reasoning in Haskell.