Using an architectural knowledge base to generate code for parallel computers

ABSTRACT

Code generation for existing parallel computers involves partitioning the work into schedulable units, assigning the resulting computational units to specific processors, and generating the code for interprocessor communication and synchronization. The options for partitioning and mapping depend in detail on the problem being solved and the algorithm and architecture being used. For each new combination of problem, algorithm, and architecture, a new partitioning and mapping must be created and evaluated based on the actual communication costs incurred. If a particular choice of partition and map is found to be too inefficient when the communication cost is analyzed, it is usually necessary to repeat the code generation process from the beginning. Given the complexity of this problem, it is not practical to develop a general algorithmic approach. A more promising approach is to develop restricted code generation strategies which are suitable for a class of problems and architectures, and compilers which use heuristic advice to guide code generation. In this paper we present a compiler for distributed memory parallel computers which perform automatic program partitioning, mapping and communication code generation under the guidance of a strategy rule-base. All partitioning and mapping is performed automatically, and communication primitives are generated. We describe the compiler system and present an example code generation strategy for iterative elliptic partial differential equation solvers.

REFERENCES

• 1: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975
• 2: R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
• 3: James W. Rymarczyk, Coding guidelines for pipelined processors, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.12-19, March 01-03, 1982, Palo Alto, California, United States
• 4: Roderic G.G. Cattell , Joseph M. Newcomer , Bruce W. Leverett, Code generation in a machine-independent compiler, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.65-75, August 06-10, 1979, Denver, Colorado, United States
• 5: Andrew S. Tanenbaum , Hans van Staveren , E. G. Keizer , Johan W. Stevenson, A practical tool kit for making portable compilers, Communications of the ACM, v.26 n.9, p.654-660, Sept. 1983 [doi>10.1145/358172.358182]
• 6: Harlan Mills, Victor Basili, Jqhn Gannon, and Richard Hamlet. Principles of Computer Programming: A Mathematical Approach. Allyn & Bacon Inc., Newton, Mass., 1987.
• 7: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 8: Anthony E. Terrano. On the grain-size dependence of interprocessor communication demand. IEEE Transactions on Computing, submitted.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design