Overview | Members | Recent Publications

Research Overview and Activities

In our work on algorithmic skeletons we investigate the idea that recurrent patterns of parallel computation and interaction can be abstracted as second order operations, parameterised by other simpler operations, thereby raising the conceptual level at which parallel computations are described and encouraging cost effective portability. More information on this area can be found at the skeletal parallelism homepage.

Earlier work on the H-PRAM model of computation spanned algorithmic and architectural concerns. The H-PRAM is a recursively partitionable variant of the well-known PRAM model. Dynamically partitioned sub-PRAMs are charged implementation overheads related to their size, thereby promoting locality in algorithm design, and providing a target for implementation techniques with cost effective scalability in mind.

Members

• Murray Cole
• Yasushi Hayashi
• Roopa Rangaswami

Recent Publications

• Coordinating Heterogeneous Parallel Systems with Skeletons and Activity Graphs , Murray Cole and Andrea Zavanella, to appear in Journal of Systems Integration, 2000.

• Activity Graphs: A Model-Independent Intermediate Layer for Skeletal Co-ordination , Murray Cole and Andrea Zavanella, Proceedings of ACM Symposium on Applied Computing 2000.

• BSP-based Cost Analysis of Skeletal Programs , Murray Cole and Yashushi Hayashi, Proceedings of Scottish Workshop on Functional Programming 1999, Intellect, 2000.

• Algorithmic Skeletons, Murray Cole, a survey chapter in Parallel Functional Programming, K. Hammond \& G. Michaelson (Eds.), Springer-Verlag, 1999.

• Practical Structured Paralleism using BMF , David Crooke, PhD thesis, University of Edinburgh, 1999.

• Descriptive Simplicity in Parallel Computing , Marcus Marr, PhD thesis, University of Edinburgh, 1998.

• A Monadic Calculus for Parallel Costing of a Functional Language of Arrays, C.B. Jay, M.I. Cole, M. Sekanina, and P.A. Steckler, presented at Euro-Par 97, Passau (Germany).

• Dividing and Conquering, Murray Cole, which is CSG report ECS-CSG-31-97, March 1997 (a short version was presented at Euro-Par 97, Passau (Germany).

• Synchronizing Arbitrary Processor Groups in Dynamically Partitioned 2D Meshes, George Chochia, Murray Cole and Todd Heywood, which is CSG report ECS-CSG-25-96, July 1996.

• Compile-time Cost Analysis for Parallel Programming , Roopa Rangaswami, presented at Euro-Par 96, Lyon (France).

• Robustness and Performance in Structured Parallelism, David Crooke, in Abstract Machine Models for Parallel and Distributed Computing, Kara et al (eds), IOS Press 1996.

• Lower Bounds on Average Time for Random Destination Mesh Routing and Their Utility as Performance Predictors for PRAM Simulation , George Chochia, Murray Cole and Todd Heywood, which is CSG report ECS-CSG-18-95. Presented at the Workshop on Randomized Parallel Computation at IPPS '96.

• HOPP - A Higher-Order Parallel Programming Model , Roopa Rangaswami, in "Algorithms and Parallel VLSI Architectures", M.Moonen and F.Cathoor (Editors), Elsevier Science 1995.

• A Cost Analysis for a Higher-Order Parallel Programming Model , Roopa Rangaswami, PhD thesis, University of Edinburgh, 1996.

• Implementing the Hierarchical PRAM on the 2D Mesh: Analyses and Experiments , George Chochia, Murray Cole and Todd Heywood, which is CSG report ECS-CSG-10-95. A version was also presented at IEEE SPDP '95.

• Hierarchical Skeletons and ad-hoc Parallelism, (with Marcus Marr), presented at ParCo '95.

• Parallel Programming with List Homomorphisms , Murray Cole, which is based on the two reports below and appears in Parallel Processing Letters. volume 5, number 2.

• Parallel Programming, List Homomorphisms and the Maximum Segment Sum Problem, which is technical report CS-25-93.

• List Homomorphic Parallel Algorithms for Bracket Matching, which is technical report CS-29-93.