Parallel compilation of Ada units

ABSTRACT

Parallel compilation—compiling independent Ada units or files in parallel—offers a potentially enormous savings in the total compilation time of a program or library. The speedup realized depends primarily on the inter-unit dependency structure and the number of processors available. We have developed a tool, AdaExpress™, which exploits the opportunities for parallelizing compilations that are inherent in Ada libraries. AdaExpress is currently targeted to a Sequent Symmetry™ multiprocessor environment. The compilation engine is a Sequent Ada compiler, a Software Leverage product that is derived from the Verdix Ada Development System (VADS®). AdaExpress automatically determines Ada dependencies from sources. It then applies scheduling heuristics to the dependency structure to obtain a schedule with good, though suboptimal, overall compilation time. AdaExpress implements this schedule as streams of parallel compilation processes. We present the details of AdaExpress's graph-based scheduling algorithm. We also give an example using AdaExpress on an actual program library, and we show the speedup achieved with four processors.

REFERENCES

• ARM: Reference Manual for the Ada Proarammina m, ANSl/MIL-STD-L815A-1983.
• Coffman82: Coffman, E.G. , G.N. Frederickson and G.S. Lueker, "Probabilistic Analysis of the L-PT Processor Scheduling Heuristic," "Deter,omostoc amd Stpcjastoc M.A.H. Dempster, J.K. Lenstra, A.H.G. Rinnooy Kan (eds.), D. Reidel Publishing Company, Dordrecht (1982).
• Feldman83: Feldman, S., "Make - A Program for Maintaining Computer Programs," Unix Proarammer's Manual (4.2 Berkeley Software Distribution), Volume II, Berkeley 1983.
• Garey79: Garey, MR. and D.S. Johnson, j&mp&rs and Intrw, W.H. Freeman, San Francisco (1979).
• Jaffe83: Jaffe, Jeffrey M., "Parallel Computation: Synchronization, Scheduling and Schemes," Ph.D. Thesis, Department of E.E. and Computer Science, MIT, 1979.
• Kunde81: Kunde, Manfred, "Non Preemptive Scheduling on Homogeneous Multiprocessor Systems," SIAM Journal On Computing, Vol. 10, No. 1, February 1981.
• Lloyd80: E. L. Lloyd, SCHEDULING TASK SYSTEMS WITH RESOURCES, Massachusetts Institute of Technology, Cambridge, MA, 1980

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Ada

General Terms:
Design, Languages