A parallel language and its compilation to multiprocessor machines or VLSI

ABSTRACT

A language <b>Crystal</b> and its compiler for parallel programming is presented. The goal of <b>Crystal</b> is to help programmers in seeking efficient parallel implementations of an algorithm, and managing the complexity that might arise in dealing with hundreds of thousands of autonomous parallel processes. In <b>Crystal,</b> a program consists of a system of recursion equations and is interpreted as a parallel system. <b>Crystal</b> views a large complex system as consisting of a hierarchy of parallel sub-systems, built upon a set of <b>Crystal</b> programs by composition and abstraction. There is no mention of explicit communications in a <b>Crystal</b> program. The <b>Crystal</b> compiler automatically incorporates pipelining into programs, and generates a parallel program that is optimal with respect to an algorithm. Each optimizing compiler, targeted for a particular machine, determines the appropriate granular size of parallelism and attains a balance between computations and communications. Based on the language, a unified theory for understanding and generating any systolic design has been devised and it constitues a part of the compiler.

REFERENCES

• 1: Burstall, R. M., <i>Proving Properties of Programs by Stuctural Induction,</i> Computing Journal, 12/1 (1969), pp. 41--48.
• 2: Chen M. C., Graham R. L., Rem M., <i>A Characterization of Deadlock-Free Resource Contention,</i> Technical Report 4684, California Institute of Technology, January 1982.
• 3: Marina Chien-Mei Chen, Space-time algorithms: semantics and methodology (crystal), 1983
• 4: Chen, M. C., The Generation of a Class of Multipliers: a Synthesis Approach to the Design of Highly Parallel Algorithms in VLSI, <i>Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers</i>, October 1985.
• 5: Chen, M. C., <i>Automatic Generation of VLSI Architectures: Synthesis by Algorithm Transformation,</i> Technical Report 427, Yale University,, October 1985.
• 6: Chen, M. C., Synthesizing Systolic Designs, <i>Proceedings of the Second International Symposium on VLSI Technology, Systems, and Applications,</i> May 1985, pp. 209--215.
• 7: Chen, M. C., <i>A Synthesis Method for Systolic Designs,</i> Technical Report 334, Yale University, January 1985.
• 8: Keller, Robert M. Davis, Alan L., <i>Data Flow Program Graphs,</i> IEEE Computer, 15/2 (1982), pp. 26--41.
• 9: Devitt, D. J., Finkel, R., Solomon, M., <i>The Crystal Mlti-computer: Design and Implementation Experience,</i> Technical Report 553, Department of Computer Science, University of Wisconsin, September 1984.
• 10: Gajski, Padua, Kuck, and Kuhn, <i>A Second Opinion on Data Flow Machines and Languages,</i> IEEE Computer, 15/2 (1982), pp. 58--69.
• 11: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 12: Inmos Corp, Occam Programming Manual, Prentice Hall Trade, 1984
• 13: Kung H. T. and Leiserson C. E., Algorithms for VLSI Processor Arrays, <i>Introduction to VLSI Systems by Mead and Conway,</i> Addison-Wesley, 1980.
• 14: Lin, T. Z., Mead, C. A., <i>The Application of Group Theory in Classifying Systolic Arrays,</i> Display File 5006, Caltech, Mar 1982.
• 15: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 16: Martin, A. J., The Torus: An Exercise in Constructing a Processing Surface, <i>Proceedings of Conference on VLSI: Architecture, Design, Fabrication,</i> 1979, pp. 52--57.
• 17: Ousterhout, J. K., Crystal: A Timing Analyzer for nMOS VLSI Circuits, <i>Third Caltech conference on Very Large Scale Integration,</i> Computer Science Press, 1983, pp. 71--86.
• 18: Scott, D. S. and Strachey, C., Toward a Mathematical Semantics for Computer Languages, Fox, J. ed., <i>Proceedings of the Symposium on Computers and Automata,</i> Polytechnic Institute of Brooklyn Press, New York, 1971, pp. 19--46.
• 19: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 20: Shapiro, Ehud, <i>Systolic Programming: A Paradigm of Parallel Processing.,</i> Technical Report cs84-16, Department of Applied Mathematics, The Weizmann Institute of Science, January 1985.