On linearizing parallel code

ABSTRACT

We consider the problem of generating sequential code for programs written in a language which contains a Multiple GOTO operator, predicates and statements. This problem arises when compiling a parallel intermediate form (such as the PDG [3,4]) to run on a sequential machine; in a source-to-source FORTRAN translator when vectorization of a loop has failed; and when compiling logic designs written in a parallel design language for simulation on a sequential machine. It is easy to generate sequential code for this sort of parallel program if one allows either duplication of code or the insertion of guard variables at merge points; in fact, it is in general impossible without this addition. However, for a large class of parallel programs (such as those originally arising from sequential programs, even after some optimizations have been applied) it is possible to generate sequential code without duplication or the addition of guard variables. In this paper we present an efficient algorithm which will generate sequential code from a parallel program without duplication or additional guard variables for a large class of parallel programs.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 3: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program Dependence Graph and its Use in Optimization, Proceedings of the 6th Colloquium on International Symposium on Programming, p.125-132, April 17-19, 1984
• 4: 4. Ferrante, Jeanne, Ottenstein, Karl, and Warten, Joe D. The program dependence graph and its use in optimization. IBM Technical Report RC-10543 (June, 1984) 33 pages.
• 5: Jeanne Ferrante , Karl J. Ottenstein, A program form based on data dependency in predicate regions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.217-236, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567089]
• 6: 6. Ferrante, Jeanne. The program dependence graph as a basis for node splitting transformations. IBM Research Report RC 10542 June, 1984.
• 7: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 8: 8. Gustafson, R. N. and Sparacio, F. J. IBM 3081 processor unit: Design considerations and design process. IBM Journal of Research and Development 26.1 (January, 1982) 12-21.
• 9: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 10: Michael C. McFarland, On proving the correctness of optimizing transformations in a digital design automation system, Proceedings of the 18th conference on Design automation, p.90-97, June 29-July 01, 1981, Nashville, Tennessee, United States

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Languages, Performance, Theory