A general compiler framework for speculative multithreading

ABSTRACT

Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing non-numeric programs, which tend to use irregular data structures with pointers and have complex flows of control. Proper thread formation is crucial to obtaining good speedup in an SpMT system. This paper presents a compiler framework for partitioning a sequential program into multiple threads for parallel execution in an SpMT system. This framework is very general, and supports a wide variety of threads, such as speculative threads, non-speculative threads, loop-centric threads, and out-of-order thread spawning. The compiler uses profiling, intra-procedural pointer analysis, data dependence information and control dependence information. The compiler is implemented on the SUIF-MachSUIF platform. A simulation-based evaluation of the generated threads shows that an average speedup of 3 can be obtained with 6 processing elements for non-numeric programs. This speedup reduces to 2 if we use only loop-based threads.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 3: Pradeep K. Dubey , Kevin O'Brien , Kathryn M. O'Brien , Charles Barton, Single-program speculative multithreading (SPSM) architecture: compiler-assisted fine-grained multithreading, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.109-121, June 27-29, 1995, Limassol, Cyprus
• 4: Manoj Franklin , Gurindar S. Sohi, ARB: A Hardware Mechanism for Dynamic Reordering of Memory References, IEEE Transactions on Computers, v.45 n.5, p.552-571, May 1996 [doi>10.1109/12.509907]
• 5: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 6: W. W. Hwu, R. E. Hank,D. M. Gallagher, S. A. Mahlke, D. M. Lavery, G. E. Haab, J. C. Gyllenhaal, and D. I. August, "Compiler Technology for Future Microprocessors", Proc.IEEE, 83(12):1625--1640, December 1995.
• 7: S. Jayashree and S. Vajapeyam, "Exploiting Parallelism across Basic Blocks via Decoupled Control Flow", Technical Report TR No. IISc-CSA-95-01, Dept. of Computer Science and Automation, Indian Institute of Science, March, 1995.
• 8: D. Naishlos, J. Nujman, C.-W. Tseng and U. Vishkin, "Evaluating Multithreading in Prototype XMT Environment", Proc. Workshop on Multi-Threaded Execution, Architecture and Compilation (MTEAC-2000).
• 9: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 10: M. D. Smith and G. Holloway, "An Introduction to Machine SUIF and Its Portable Libraries for
• 11: Xinan Tang , Guang R. Gao, Compiling for multithreaded architectures, 2000
• 12: Jenn-Yuan Tsai , Pen-Chung Yew, The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.35, October 20-23, 1996
• 13: T. N. Vijaykumar , Gurindar S. Sohi, Task selection for a multiscalar processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.81-92, November 1998, Dallas, Texas, United States
• 14: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States

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.4 Parallel Architectures

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
TLP compiler, control dependence, data dependence, parallelization, speculative multithreading (SpMT), thread formation, thread-level parallelism (TLP)