Structured Parallelism Group
Overview  Members  Recent Publications
Research Overview and Activities
We are interested in the structure of parallel computation.
In the sequential world, high level structuring and abstraction mechanisms
have superseded simpler primitive
concepts. We believe that analogous mechanisms and models must be
developed to allow parallel computing to enjoy similar success.
In our work on algorithmic skeletons we investigate the idea that
recurrent patterns of parallel computation and interaction can be
abstracted as frameworks, templates or second order operations,
parameterised by other simpler operations, thereby raising the conceptual
level at which parallel programs are described and encouraging cost effective
portability.
You can find more specific information on the
eSkel and
Enhance projects,
or more general information on the area at the
skeletal
parallelism homepage.
Members
Alumni
Publications
 Adaptive Structured Parallelism for Distributed Heterogeneous Architectures: A Methodological Approach with Pipelines and Farms,
Horacio Gonzalez and Murray Cole, to appear, Concurrency and Computation: Practice and Experience, 2009.
 Adaptive Statistical Scheduling of Divisible Workloads in Heterogeneous Systems,
Horacio Gonzalez and Murray Cole, to appear, Journal of Scheduling, 2009.
 Characterising Effective Resource Analyses for Parallel and Distributed Coordination,
P. W. Trinder, M. Cole, HW. Loidl and G. J. Michaelson, to appear, International Workshop on Foundational and Practical Aspects of Resource Analysis (FOPARA09), 2009.
 Adaptive Structured Parallelism,
Horacio GonzalezVelez, PhD thesis, University of Edinburgh, 2008.

Reactive Scheduling of DAG Applications on Heterogeneous and Dynamic Distributed Computing Systems,
Jesus Israel Hernandez, PhD thesis, University of Edinburgh, 2008.
 An Adaptive Parallel Pipeline Pattern for Grids , Horacio Gonzalez and Murray Cole, IEEE International Parallel & Distributed Processing Symposium, pages 111, 2008.
 Scheduling DAGs on Grids with Copying and Migration,
Israel Hernandez and Murray Cole, Parallel Processing and Applied Mathematics 2007 (PPAM07), LNCS 4967, pages 10191028, Springer, 2008.
A Structural Approach for Modelling Performance of Systems using Skeletons, Gagarine Yaikhom, Murray Cole, Stephen Gilmore and Jane Hillston, Electronic Notes in Theoretical Computer Science 190(3),
167183, Elsevier, 2007.
 Reliable DAG Scheduling with Rewinding and Migration, Israel Hernandez and Murray Cole, First International Conference on Networks for Grid Applications (GridNets07), pages 18, ACM Press, 2007.
 Parallel stochastic simulation of macroscopic calcium currents,
Virginia GonzalezVelez and Horacio GonzelezVelez, Journ. of Bioinform. Comput. Biol. 5(3) pages 755772, 2007.
 A structural
approach for modelling performance of workflow systems,
Gagarine Yaikhom, Murray Cole, Stephen Gilmore and Jane Hillston, in
Proceedings of 5th International Workshop on the Quantitative Aspects of Programming Languages (QAPL 07), 2007.
 Adaptive Structured Parallelism for Computational Grids,
Horacio Gonzalez and Murray Cole, PPoPP'07: 12th ACM SIGPLAN Symp on Principles and
Practice of Parallel Programming, pages 140141, ACM Press, 2007.
 Reactive Grid Scheduling of DAG applications,
Israel Hernandez and Murray Cole, Parallel and Distributed Computing and Networks 2007,
25th IASTED International MultiConference on Applied Informatics, pages 9297, ACTA Press, 2007.
 Towards fully adaptive pipeline parallelism for heterogeneous distributed environments,
Horacio GonzalezVelez and Murray Cole, ISPA 2006, LNCS 4330, pages 916926, SpringerVerlag, 2006.
 Combining measurement and stochastic modelling to enhance scheduling decisions for a parallel Mean Value Analysis algorithm, Gagarine Yaikhom, Murray Cole, and Stephen Gilmore, Proceedings ICCS 2006, LNCS 3992, pages 929936, Springer Verlag, 2006.
 Selfadaptive skeletal task farm for computational grids,
Horacio GonzalezVelez, Parallel Computing 32(78), pages 479490, 2006.

Message Passing with Communication Structures,
Gagarine Yaikhom, PhD thesis, University of Edinburgh, 2006.

Automatic mapping of ASSIST applications using process algebra,
Marco Aldinucci and Anne Benoit,
Proceedings of the
Third International Workshop on Highlevel Parallel Programming and Applications (HLPP 2005),
July 2005, and to appear in Parallel Processing Letters.
 A gridbased stochastic simulation
of unitary and membrane Ca2+ currents in spherical cells,
Virginia GonzalezVelez and Horacio GonzalezVelez, Proceedings of CBMS 2005,
pages 171176, IEEE Press, 2005.
 Structured parallelism for the grid,
Horacio GonzalezVelez,
In Science and Supercomputing in Europe, P. Alberigo, G. Erbacci, and F. Garofano, Eds.
CINECA, Bologna, 2005,
pages 201203. ISBN: 8886037155, 2005.
 An Adaptive Skeletal Task Farm for Grids,
Horacio GonzalezVelez,
Proceedings of EuroPar 2005,
LNCS 3648, pages 401410, Springer Verlag, 2005.
 Shared Message Buffering without Intermediate Memory Copy,
Gagarine Yaikhom, in Proceedings of the
Third International Workshop on Highlevel Parallel Programming and Applications (HLPP 2005),
July 2005, and to appear in Parallel Processing Letters.

Integrating MPISkeletons with Web Services.
Jan Duennweber, Sergei Gorlatch, Anne Benoit and Murray Cole,
in Proceedings of ParCo 2005.
Malaga, 2005.
 Native Services for Grid Applications,
Jan Duennweber, Anne Benoit, Murray Cole, Sergei Gorlatch,
Proceedings of ParCo 2005.
Malaga, 2005.
 Using eSkel to implement the multiple baseline stereo application,
Anne Benoit, Murray Cole, Stephen Gilmore and Jane Hillston,
Proceedings of ParCo 2005.
Malaga, 2005.
 Flexible Skeletal Programming with eSkel,
Anne Benoit, Murray Cole, Stephen Gilmore and Jane Hillston, Proceedings of EuroPar 2005.
LNCS 3648, pages 761770, Springer Verlag, 2005.

Buffered Branching Channels with Rendezvous Message Passing,
Gagarine Yaikhom, in Parallel and Distributed Computing and Networks 2005,
23rd IASTED International MultiConference on Applied Informatics, pages 184192, ACTA Press, 2005.
 On the Abstraction of MessagePassing
Communications using Algorithmic Skeletons: A Case Study,
Horacio GonzalezVelez, ISSADS
2005, LNCS 3563, pages 4350, SpringerVerlag, 2005.

Componentbased grid programming. A case study on wavelets,
Jan Duennweber, Sergei Gorlatch, Anne Benoit and Murray Cole,
HPCEuropa project report, April 2005.
 Enhancing the effective utilisation
of Grid clusters by exploiting online performability analysis,
Anne Benoit, Murray Cole Stephen Gilmore and Jane Hillston,
Proceedings of CCGrid 2005, vol 1, pages 317324,
IEEE Press, 2005.
 Two fundamental concepts in skeletal parallel programming,
Anne Benoit and Murray Cole, ICCS 2005, Part II, LNCS 3515, pages 764771, Springer Verlag,
(as part of Practical Aspects of Highlevel Parallel Programming
PAPP 2005), 2005.
 Analyse quantitative de programmes applicatif à
base de squelettes algorithmiques,
(English version: Quantitative analysis
of skeletonstructured applicative programs)
Anne Benoit, Murray Cole, Stephen Gilmore and Jane Hillston,
Journées Francophones des Langages Applicatifs (JFLA05), Obernai, March 2005.
 Scheduling skeletonbased grid applications using PEPA and NWS,
Anne Benoit, Murray Cole, Stephen Gilmore and Jane Hillston,
The Computer Journal, 48(3):369378, 2005.
 Evaluating the performance of pipelinestructured parallel programs with skeletons and process algebra,
Anne Benoit, Murray Cole, Stephen Gilmore and Jane Hillston,
Scalable Computing: Practice and Experience 6(4), pages 116, 2005.
A preliminary version appeared in Practical Aspects of Highlevel Parallel Programming,
PAPP 2004.
 Evaluating the performance of skeletonbased high level parallel programs,
Anne Benoit, Murray Cole, Stephen Gilmore and Jane Hillston,
Proceedings of The International Conference on Computational Science (ICCS 2004), Part III,
LNCS vol 3038, pages 289296, Springer Verlag, 2004.
 A comparative study of intrinsic parallel programming methodologies,
GonzalezVelez, H., de Luca, A., and GonzalezVelez, V,
ICEEE: First Int Conf on Electrical and Electronics Engineering (Acapulco, Mexico, June 2004),
IEEE, pp. 200205, 2004.
 Why Skeletal Parallel Programming Matters, Murray Cole,
Proceedings of EuroPar 2004, Danelutto, Vanneschi,
Laforenza (Eds), LNCS vol 3149, page 37, Springer Verlag, 2004 (also see
slides from this keynote talk).
 Bringing Skeletons out of the Closet: A Pragmatic
Manifesto for Skeletal Parallel Programming, Murray Cole,
Parallel Computing 30(3) pages 389406, 2004.
 The Integration of Task and Data Parallel Skeletons ,
Herbert Kuchen and Murray Cole, Parallel Processing Letters 12(2), pages 141156, 2002.
(Draft appeared in Proceedings of CMPP02, Dagstuhl, 2002)
 Automated Cost Analysis of a Parallel Maximum
Segment Sum Program Derivation,
Yasushi Hayashi and Murray Cole, Parallel Processing Letters 12(1), pages 95112, 2002.
 Static Performance Prediction of Skeletal Programs ,
Yasushi Hayashi and Murray Cole, Parallel Algorithms and Applications 17(1) pages 5984, 2002.
 Shapebased Cost Analysis of Skeletal Parallel Programs ,
Yasushi Hayashi, PhD thesis, University of Edinburgh, 2001.
 Coordinating Heterogeneous Parallel Systems with Skeletons and Activity Graphs,
Murray Cole and Andrea Zavanella, Journal of Systems Integration, 10(2), pages 127143, 2001.

Frame: An Imperative Coordination Language for Parallel Programming , Murray Cole, Technical report EDIINFRR0026, 2000.
 Activity Graphs: A ModelIndependent Intermediate Layer for Skeletal Coordination,
Murray Cole and Andrea Zavanella, Proceedings of ACM Symposium on Applied
Computing, Vol 1, pages 255261, 2000.
 BSPbased Cost Analysis of Skeletal Programs ,
Yasushi Hayashi and Murray Cole, Proceedings of Scottish Workshop on Functional
Programming 1999, pages 2028, Intellect, 2000.
 Algorithmic Skeletons, Murray Cole, which is
chapter 13 (pages 289303) of Research Directions in Parallel Functional Programming,
K. Hammond & G. Michaelson (Eds.), SpringerVerlag, 1999.
 Practical Structured Parallelism 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,
Proceedings of EuroPar 97, LNCS 1300, pages 650661,
Lengauer, Griebl, Gorlatch (Eds), Springer Verlag, 1997.

On Dividing and Conquering Independently,
Murray Cole, Proceedings of EuroPar 97, LNCS 1300, pages 634637,
Lengauer, Griebl, Gorlatch (Eds), Springer Verlag, 1997.
(The link is to a longer version which appeared as a University of Edinburgh
Computer Science technical report, ECSCSG3197).
 Recursive 3D Mesh Indexing with Improved Locality,
George Chochia and Murray Cole, Proceedings of HPCN '97,
Hertzberger, Sloot (Eds), pages 10141015, LNCS 1225, Springer Verlag, 1997.

Compiletime Cost Analysis for Parallel Programming ,
Roopa Rangaswami,
presented at EuroPar 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.

HOPP  A HigherOrder 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 HigherOrder Parallel Programming Model
,
Roopa Rangaswami, PhD thesis, University of Edinburgh, 1996.

Synchronizing Arbitrary Processor Groups in Dynamically
Partitioned 2D Meshes,
George Chochia, Murray Cole and Todd Heywood, which is
CSG report ECSCSG2596, July 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,
Proceedings of the Workshop on Randomized Parallel Computing at the IPPS 96, 1996.

Implementing the Hierarchical PRAM on the
2D Mesh: Analyses and Experiments,
George Chochia, Murray Cole and Todd Heywood,
Proceedings IEEE SPDP 95, pages 587595, 1995.

Hierarchical Skeletons and adhoc Parallelism,
Marcus Marr and Murray Cole,
Proceedings of ParCo 95, D'Hollander et al (Eds.),
Advances in Parallel Computing, vol. 11, pages 673676, Elsevier Press,
1996.

Parallel Programming with List Homomorphisms, Murray Cole,
Parallel Processing Letters 5(2), pages 191203, 1995.

A survey of PRAM simulation techniques,
Tim J. Harris, ACM Computing Surveys 26(2), pages 187206, 1994.

List Homomorphic Parallel Algorithms for Bracket Matching, Murray Cole,
which is technical report CS2993, a preliminary version of the ParCo 93 paper above.

Parallel Programming, List Homomorphisms and the Maximum Segment Sum
Problem, Murray Cole,
which is technical report CS2593.

Parallel Programming, List Homomorphisms and the Maximum Segment Sum Problem,
, Murray Cole, Proceedings of ParCo 93 pages 489492, Trystram (Ed.),
Elsevier Press, 1993. (A short conference paper based on the technical report above).

The Parameterized PRAM, Tim Harris and Murray Cole,
Proceedings of the Workshop on Parallel and Distributed Processing,
Boyonov (Ed.), Elsevier Press, 1993.

Parallel Software Paradigms, Murray Cole, chapter 1 of
Advances in Parallel Algorithms L. Kronsjo & D. Shumsheruddin (Eds.),
pp 125, Blackwell Scientific, 1992.

DoitYourself Shared Memory Instruction Sets in occam, Murray Cole,
Proceedings of Tools and Techniques for Transputer Applications pages 110,
S.J. Turner (Ed.), IOS Press, 1990.

Algorithmic Skeletons: Structured Management of Parallel Computation , Murray Cole,
MIT Press & Pitman, 1989. (Derived from my PhD thesis and now
available on the web by kind permission of the publishers. Also
see its entry on the MIT Press website.
There are some minor formatting changes from the published version, since the original
Latex style is no longer available to me. The text itself is unchanged.

A Skeletal Approach to the Exploitation of Parallelism, Murray Cole,
Proceedings of CONPAR 88 , pages 667675,
C. Jesshope (Ed.), Cambridge University Press, 1989.

Recursive Splitting as a General Purpose Skeleton for Parallel
Computation , Murray Cole,
Proceedings of the Second International Conference on
Supercomputing ,
L.P. & S.I. Kartashev (Eds), vol 3, pp. 133140, 1987.
Murray Cole, questions to <mic@inf.ed.ac.uk>
Last modified: Wed Sep 22 12:23:30 BST 2010
Please contact our
webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is
copyright © The University of Edinburgh.