Space-time scheduling of instruction-level parallelism on a raw machine

ABSTRACT

Increasing demand for both greater parallelism and faster clocks dictate that future generation architectures will need to decentralize their resources and eliminate primitives that require single cycle global communication. A Raw microprocessor distributes all of its resources, including instruction streams, register files, memory ports, and ALUs, over a pipelined two-dimensional mesh interconnect, and exposes them fully to the compiler. Because communication in Raw machines is distributed, compiling for instruction-level parallelism (ILP) requires both spatial instruction partitioning as well as traditional temporal instruction scheduling. In addition, the compiler must explicitly manage all communication through the interconnect, including the global synchronization required at branch points. This paper describes RAWCC, the compiler we have developed for compiling general-purpose sequential programs to the distributed Raw architecture. We present performance results that demonstrate that although Raw machines provide no mechanisms for global communication the Raw compiler can schedule to achieve speedups that scale with the number of available functional units.

REFERENCES

• 1: Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, p.207, June 12-14, 1996
• 2: Saman P. Amarasinghe , Jennifer M. Anderson , Christopher S. Wilson , Shih-Wei Liao , Brian R. Murphy , Robert S. French , Monica S. Lam , Mary W. Hall, Multiprocessors from a Software Perspective, IEEE Micro, v.16 n.3, p.52-61, June 1996 [doi>10.1109/40.502406]
• 3: David I. August , Wen-mei W. Hwu , Scott A. Mahlke, A framework for balancing control flow and predication, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.92-103, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 4: J. Babb , M. Frank , V. Lee , E. Waingold , R. Barua , M. Taylor , J. Kim , S. Devabhaktuni , A. Agarwal, The RAW benchmark suite: computation structures for general purpose computing, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.134, April 16-18, 1997
• 5: J. Babb, R. Tessier, M. Dahl, S. Hanono, D. Hoki, and A. Agarwal. Logic emulation with virtual wires. IEEE Transactions on Computer Aided Design, 16(6):609-626, June 1997.
• 6: Sanjeev Banerjia , Thomas M. Conte, Instruction scheduling and fetch mechanisms for clustered vliw processors, 1998
• 7: Agarwal Rajeev Barua Walter Lee Saman Amarasinghe Anant, Maps: a Compiler-Managed Memory System for RAW Machines, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 8: R. Barua, W. Lee, S. Amarasinghe and A. Agarwal, Proceedings of the Fifth International Conference on High Performance Computing, p.212, December 17-20, 1998
• 9: Andrea Capitanio , Nikil Dutt , Alexandru Nicolau, Partitioned register files for VLIWs: a preliminary analysis of tradeoffs, Proceedings of the 25th annual international symposium on Microarchitecture, p.292-300, December 01-04, 1992, Portland, Oregon, United States
• 10: G. Deso}i. Instruction Assignment for Clustered VLIW DSP Compilers: A New Approach. Technical report, HP HPL- 98-13, Feb. 1998.
• 11: M. Dikaiakos, A. Rogers, and K. Steiglitz. A Comparison of Techniques Used for Mapping Parallel Algorithms to Message-Passing Multiprocessors. In Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing, Oct. 1994.
• 12: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 13: J. A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Transactions on Computers, 7(C-30):478-490, July 1981.
• 14: L. Gwennap. Digital 21264 Sets New Standard. Microprocessor Report, pages 11-16, Oct. 1996.
• 15: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 16: V. Kathail, M. Schlansker, and B. R. Rau. HPL PlayDoh Architecture Specification: Version 1.0. Technical report, HP HPL-93-80, Feb. 1994.
• 17: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 18: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 19: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 20: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 21: M. D. Smith. Extending SUIF for Machine-dependent Optimizations. In Proceedings of the First SUiF Compiler Workshop, pages 14-25, Stanford, CA, Jan. 1996.
• 22: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 23: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
• 24: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• 25: Tao Yang , Apostolos Gerasoulis, List scheduling with and without communication delays, Parallel Computing, v.19 n.12, p.1321-1344, Dec. 1993 [doi>10.1016/0167-8191(93)90079-Z]
• 26: T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994 [doi>10.1109/71.308533]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

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

General Terms:
Design, Languages, Measurement, Performance, Theory