Abstract
We describe a mechanism for generating families of process interconnection structures. Parallel programming environments that support individually programmed processor elements should allow the programmer to explicitly specify the necessary channels of communication at the level of logical abstraction of the algorithm. For highly parallel processors, the specification of this structure with traditional methods can be tedious and error-prone. Aggregate rewriting graph grammars provide a framework for describing families of regular graphs. Using this scheme, the difficulty of specifying an algorithm's communication structure is independent of its size. In addition, we note that scripts of derivation sequences generating different members of a family of structures can suggest an intra-family contracting map.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Duane A. Bailey and Janice E. Cuny. Graph Grammar Based Specification of Interconnection Structures. Technical Report 87-23, University of Massachusetts at Amherst, March 1987.
Duane A. Bailey and Janice E. Cuny. The Use of Shape Grammars in Processor Embeddings. Technical Report A-86-23, University of Massachusetts at Amherst, July 1986.
H. Ehrig, M. Pfender, and H. J. Schneider. Graph grammars: an algebraic approach. In 14th Conference on Switching and Automata Theory, pages 167–179, 1973.
John P. Fishburn and Raphael A. Finkel. Quotient networks. IEEE Transactions on Computers, C-31(4):288–295, April 1982.
Rodney L. Goke. Banyan Networks for Partitioning Multiprocessor Systems. PhD thesis, University of Florida, 1976.
D. Janssens and G. Rozenberg. Graph grammars with neighbourhood-controlled embedding. Theoretical Computer Science, 21:55–74, 1982.
D. Janssens and G. Rozenberg. On the structure of node-label-controlled graph languages. Information Sciences, 20:191–216, 1980.
Hungwen Li, Ching-Chy Wang, and Mark Lavin. Structured process: a new language attribute for better interaction of parallel architecture and algorithm. In 1985 International Conference on Parallel Processing, pages 247–254, August 1985.
Franco P. Preparata and Jean Vuillemin. The cube-connected cycles: a versatile network for parallel computation. Communications of the ACM, 300–309, May 1981.
H. J. Schneider. Graph Grammars, pages 314–331. Lecture Notes in Computer Science, Springer-Verlag, Berlin, September 1977.
Lawrence Snyder. Introduction to the configurable highly parallel computer. Computer, 15(1):47–56, January 1982.
Harold S. Stone. Parallel processing with the perfect shuffle. IEEE Transactions on Computers, C-20(2):153–161, February 1971.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bailey, D.A., Cuny, J.E. (1987). An approach to programming process interconnection structures: Aggregate rewriting graph grammars. In: de Bakker, J.W., Nijman, A.J., Treleaven, P.C. (eds) PARLE Parallel Architectures and Languages Europe. PARLE 1987. Lecture Notes in Computer Science, vol 259. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-17945-3_6
Download citation
DOI: https://doi.org/10.1007/3-540-17945-3_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17945-0
Online ISBN: 978-3-540-47181-3
eBook Packages: Springer Book Archive