IEEE Transactions on Parallel and Distributed Systems · 1991 · 308 citations · 25 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingParallel Algorithm DesignParallel ArchitecturesParallel ComputationParallel Computing SystemsParallel Programming ModelsTask ParallelismGranularityGranularity ControlInliningParallel Program DesignParallelism GranularityTask Granularity Analysis
When a parallel algorithm is written naturally, the resulting program often produces tasks of a finer grain than an implementation can exploit efficiently. Two solutions to the granularity problem that combine parallel tasks dynamically at runtime are discussed. The simpler load-based inlining method, in which tasks are combined based on dynamic bad level, is rejected in favor of the safer and more robust lazy task creation method, in which tasks are created only retroactively as processing results become available. The strategies grew out of work on Mul-T, an efficient parallel implementation of Scheme, but could be used with other languages as well. Mul-T implementations of lazy task creation are described for two contrasting machines, and performance statistics that show the method's effectiveness are presented. Lazy task creation is shown to allow efficient execution of naturally expressed algorithms of a substantially finer grain than possible with previous parallel Lisp systems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
25
The Manchester prototype dataflow computer
John R. Gurd, Chris Kirkham, Ian Watson · Communications of the ACM · 1985 · 466 citations · Full text
David Chaiken, John Kubiatowicz, Anant Agarwal · 1991 · 332 citations
Anant Agarwal, Beng-Hong Lim, David Kranz et al. · ACM SIGARCH Computer Architecture News · 1990 · 293 citations
David Kranz, Richard Kelsey, Jonathan Rees et al. · ACM SIGPLAN Notices · 2004 · 259 citations