research-article

Open access

Parallelization of divide-and-conquer in the Bird-Meertens formalism

Authors:

Sergei Gorlatch,

Christian LengauerAuthors Info & Claims

Formal Aspects of Computing, Volume 7, Issue 6

Pages 663 - 682

https://doi.org/10.1007/BF01211000

Published: 01 November 1995 Publication History

Abstract

An SPMD parallel implementation schema for divide-and-conquer specifications is proposed and derived by formal refinement (transformation) of the specification schema. The specification is in the form of a mutually recursive functional definition. In a first phase, a parallel functional program schema is constructed which consists of a communication tree and a functional program that is shared by all nodes of the tree. The fact that this phase proceeds by semantics-preserving transformations in the Bird-Meertens formalism of higher-order functions guarantees the correctness of the resulting functional implementation. A second phase yields an imperative distributed message-passing implementation of this schema. The derivation process is illustrated with an example: a two-dimensional numerical integration algorithm.

References

References

[1]

Atallah M. J., Cole R., and Goodrichs M. T. Cascading divide-and-conquer: A technique for designing parallel algorithms SIAM J. Computing 1989 18 3 499-532

Digital Library

[2]

Axford T. and Joy M. List processing primitives for parallel computation Computer Languages 1993 19 1 1-12

Digital Library

[3]

Axford, T.: The divide-and-conquer paradigm as a basis for parallel language design. In L. Kronsjo and D. Shumsheruddin, editors,Advances in Parallel Algorithms. Chapter 2. Blackwell, 1992.

[4]

Backus J. W. Can programming be liberated from the von Neumann style Communications of the ACM 1978 21 613-641

Digital Library

[5]

Bird, R. S.: Lectures on constructive functional programming. In M. Broy, editor,Constructive Methods in Computing Science, NATO ASO Series F: Computer and Systems Sciences. Vol. 55, pages 151–216. Springer Verlag, 1988.

[6]

Cox, S., Huang, S., Kelly, P., Liu, J. and Taylor, F.: An implementation of static functional process networks. In D. Etiemble and J.-C. Syre, editors,PARLE'92 Parallel Architecture and Languages Europe, Lecture Notes in Computer Science 605, pages 497–512, 1992.

[7]

Carpentieri B. and Mou G. Compile-time transformations and optimizations of parallel divide-and-conquer algorithms ACM SIGPLAN Notices 1991 20 10 19-28

Digital Library

[8]

Cole, M.: Algorithmic skeletons: A structured approach to the management of parallel computation. Ph.D. Thesis. Technical Report CST-56-88, Department of Computer Science, University of Edinburgh, 1988.

[9]

Cole, M.: Parallel programming, list homomorphisms and the maximum sum problem. Technical Report CSR-25-93, Department of Computer Science, University of Edinburgh, May 1993.

[10]

Darlington, J., Field, A., Harrison, P., Kelly, P., Sharp, D., Wu, Q. and While, R.: Parallel programming using skeleton functions. In A. Bode, M. Reeve, and G. Wolf, editors,PARLE '93 Parallel Architectures and Languages Europe, Lecture Notes in Computer Science 694, pages 146–160. 1993.

[11]

de Guzman I. P., Harrison P. G., and Medina E. Pipelines for divide-and-conquer functions The Computer Journal 1993 36 3 254-268

[12]

Dijkstra, E. W. and Scholten,C. S.:Predicate Calculus and Program Semantics. Texts and Monographs in Computer Science. Springer-Verlag, 1990.

[13]

Fokkinga M. An exercise in transformational programming: Backtracking and branch-and-bound Science of Computer Programming 1991 16 19-48

Digital Library

[14]

Feldcamp, D., Sreekantaswamy, H., Wagner, A. and Chanson, S.: Towards a skeleton-based parallel programming environment. In A. Veronis and Y. Parker, editors,Transputer Research and Applications, pages 104–115. IOS Press, 1992.

[15]

Gorlatch, S. and Lengauer,C.: Systematic development of an SPMD implementation schema for mutually recursive divide-and-conquer specifications. In H. J. Siegel, editor,Proc. Eighth Int. Paral. Proc. Symp. (IPPS'94), pages 368–375. IEEE Computer Society Press, 1994.

[16]

Gorlatch, S.: Parallel program development for a recursive numerical algorithm: A case study. Technical Report SFB 342/7/92, Institut für Informatik, TU München, March 1992.

[17]

Gorlatch, S.: Formal derivation and implementation of divide-and-conquer on a transputer network. In A. De Gloria, M. Jane, and D. Marini, editors,Transputer Applications and System '94, pages 763–776. IOS Press, 1994.

[18]

Harrison P. G. A higher-order approach to parallel algorithms The Computer Journal 1992 35 6 555-566

[19]

Huang C.-H. and Lengauer C. The automated proof of a trace transformation for a bitonic sort Theoretical Computer Science 1986 46 2–3 261-284

Digital Library

[20]

Jones, G. and Gibbons, J.: Linear-time breadth-first tree algorithms: An exercise in the arithmetic of folds and zips. Technical Report TR-31-92, Oxford University Computing Laboratory, 1992.

[21]

Lengauer, C.: Loop parallelization in the polytope model. In E. Best, editor,CONCUR '93, Lecture Notes in Computer Science 715, pages 398–416. Springer-Verlag, 1993.

[22]

Lengauer, C. and Huang, C.-H.: A mechanically certified theorem about optimal concurrency of sorting networks. InProc. 13th Ann. ACM Symp. on Principles of Programming Languages (POPL), pages 307–317, 1986.

[23]

Mou, Z. G., Constantinescu, C. and Hickey, T. J.: Divide-and-conquer on three-dimensional meshes. In W. Joosen and E. Milgrom, editors,Parallel Computing: From Theory to Sound Practice, pages 344–355. IOS Press, 1992.

[24]

Mou Z. G. and Hudak P. An algebraic model for divide-and-conquer algorithms and its parallelism Journal of Supercomputing 1988 2 3 257-278

[25]

McBurney, D. and Sleep, M.: Transputer-based experiments with the ZAPP architecture. In J. de Bakker, A. Nijman, and P. Treleaven, editors,PARLE Parallel Architectures and Languages Europe, Lecture Notes In Computer Science 258, pages 242–259. 1987.

[26]

Nation, W. G., Saghi, G. and Siegel, H. J.: Properties of inteconnection networks for large-scale parallel processing systems. In P. Tvrdík, editor,ISIPCALA'93, pages 51–79, 1993.

[27]

Pepper, P.: Deductive derivation of parallel programs. In R. Paige, J. Reif, and R. Wachter, editors,Parallel Algorithm Derivation and Program Transformation, pages 1–53. Kluwer Academic Publishers, 1993.

[28]

Swiestra, D. and de Moor, O.: Virtual data structures. In B. Moeller, H. Partsch, and S. Schuman, editors,Formal Program Development, Lecture Notes in Computer Science 755, pages 355–371.

[29]

Skillicorn D. B. Architecture-independent parallel computation IEEE Computer 1990 23 12 38-50

Digital Library

[30]

Skillicorn D. B. Deriving parallel programs from specifications using cost information Science of Computer Programming 1993 26 205-221

Digital Library

[31]

Smith, D. and Lowry, M.: Algorithm theories and design tactics. In J. L. A. van de Snepscheut, editor,Mathematics of Program Construction, Lecture Notes in Computer Science 375, pages 379–398, 1989.

[32]

Stout Q. F. Supporting divide-and-conquer algorithms for image processing Journal of Parallel and Distributed Computing 1987 4 95-115

Digital Library

[33]

Wagner, A., Sreekantaswamy, H. and Chanson, S.: Performance issues in the design of a processor farm template. In R. Grebe et al., editors,Transputer Applications and Systems. Vol. 1, pages 438–450. IOS Press, 1993.

[34]

Zenger, C.: Sparse grids. Technical Report SFB-Nr. 342/18/90 A, Institut für Informatik, TU München, October 1990.

Cited By

(2018)Automatically deriving cost models for structured parallel processes using hylomorphismsFuture Generation Computer Systems10.1016/j.future.2017.04.03579:P2(653-668)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.future.2017.04.035
Castro DHammond KSarkar S(2016)Farms, pipes, streams and reforestation: reasoning about structured parallel processes using types and hylomorphismsACM SIGPLAN Notices10.1145/3022670.295192051:9(4-17)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/3022670.2951920
Castro DHammond KSarkar SGarrigue JKeller GSumii E(2016)Farms, pipes, streams and reforestation: reasoning about structured parallel processes using types and hylomorphismsProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951920(4-17)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/2951913.2951920
Show More Cited By

Index Terms

Parallelization of divide-and-conquer in the Bird-Meertens formalism
1. Theory of computation
  1. Models of computation
    1. Concurrency

Index terms have been assigned to the content through auto-classification.

Recommendations

Tools-supported HPF and MPI parallelization of the NAS parallel benchmarks
FRONTIERS '96: Proceedings of the 6th Symposium on the Frontiers of Massively Parallel Computation

High Performance Fortran (HPF) compilers and communication libraries with the standardized Message Passing Interface (MPI) are becoming widely available, easing the development of portable parallel applications. The Annai tool environment supports ...
Divide-and-conquer programming on MIMD computers
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

We have developed a programming template to implement divide and conquer algorithms on MIMD computers. The template is based on the parallel divide and conquer function of Z.G. Mou and P. Hudak (1988). We explore the programmability and performance of ...
Grid-enabled parallel divide-and-conquer: theory and practice
SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

This paper presents a general methodology for the communication-efficient parallelization of graph algorithms using the divide-and-conquer approach. The algorithm is communication-free in the conquer stage and uses only a small amount of messages while ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Formal Aspects of Computing

Formal Aspects of Computing Volume 7, Issue 6

Nov 1995

141 pages

ISSN:0934-5043

EISSN:1433-299X

Issue’s Table of Contents

© BCS 1995.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 1995

Accepted: 15 February 1995

Received: 15 February 1994

Published in FAC Volume 7, Issue 6

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
37
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2018)Automatically deriving cost models for structured parallel processes using hylomorphismsFuture Generation Computer Systems10.1016/j.future.2017.04.03579:P2(653-668)Online publication date: 1-Feb-2018
Castro DHammond KSarkar S(2016)Farms, pipes, streams and reforestation: reasoning about structured parallel processes using types and hylomorphismsACM SIGPLAN Notices10.1145/3022670.295192051:9(4-17)Online publication date: 4-Sep-2016
Castro DHammond KSarkar SGarrigue JKeller GSumii E(2016)Farms, pipes, streams and reforestation: reasoning about structured parallel processes using types and hylomorphismsProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951920(4-17)Online publication date: 4-Sep-2016
Garrigue JKeller GSumii E(2016)Proceedings of the 21st ACM SIGPLAN International Conference on Functional ProgrammingundefinedOnline publication date: 4-Sep-2016
Fischer JGorlatch SBischof H(2003)Foundations of data-parallel skeletonsPatterns and skeletons for parallel and distributed computing10.5555/778641.778647(1-27)Online publication date: 1-Jan-2003
Gorlatch S(1998)Programming with Divide-and-Conquer SkeletonsThe Journal of Supercomputing10.1023/A:100798151158212:1-2(85-97)Online publication date: 1-Jan-1998

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents