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. A. Aho, R. Sethi, and J. Ullman,"Compilers: Principles, Techniques, and Tools", Addison-Wesley, Reading, MA, 1986.
2. R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and F. Zadeck, "Efficiently computing static single assign-ment form and the control dependency graph", ACM Trans. Program. Lang. Syst., 13(4), October 1991.
3. P. Dubey, K. O'Brien, K. M. O'Brien, and C. Barton, "Single-Program Speculative Multithreading (SPSM) Architecture: Compiler-assisted Fine-Grained Multi-threading", Proc. Int'l Conf. on Parallel Architecture and Compilation Techniques (PACT '95).
4. M. Franklin and G. Sohi, "ARB: A Hardware Mechanism for Dynamic Reordering of Memory References", IEEE Transactions on Computers, Vol. 45, No. 5, pp. 552--571, May 1996.
5. M. W. Hall, J. M. Anderson, S. P. Amarasinghe, B. R. Murphy, S. W. Liao, E. Bugnion, and M. S. Lam, "Maximizing Multiprocessor Performance with the SUIF Compiler", IEEE Computer, December 1996.
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. K. Olukotun, et al. "A Chip-Multiprocessor Architecture with Speculative Multithreading", IEEE Transac-tions on Computers, September 1999.
10. M. D. Smith and G. Holloway, "An Introduction to Machine SUIF and Its Portable Libraries for
11. X. Tang, "Compiling For Multithread Architectures", Ph.D. Thesis, Dept. of Electrical Eng., Univ. of Dela-ware, 1999.
12. J-Y. Tsai and P-C. Yew. "The Superthreaded Architecture: ThreadPipelining with Run-Time Data Dependence Checking and Control Speculation", Proc. Int'l Conf. on Parallel Architectures and Compilation Techniques (PACT '96).
13. T. N. Vijaykumar and G. S. Sohi. "Task Selection for a Multiscalar Processor", Proc. 31st Int'l Symposium on Microarchitecture (MICRO-31), 1998.
14. K. Wang and M. Franklin, "Highly Accurate Data Value Prediction using Hybrid Predictors", Proc. Int'l Symposium on Microarchitecture (MICRO-30), 1997.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

• Software and its engineering

  • Software notations and tools

    • Compilers