Peng-Sheng Chen
ABSTRACT
Speculative multithreading (SpMT) architecture can exploit thread-level parallelism that cannot be identified statically. Speedup can be obtained by speculatively executing threads in parallel that are extracted from a sequential program. However, performance degradation might happen if the threads are highly dependent, since a recovery mechanism will be activated when a speculative thread executes incorrectly and such a recovery action usually incurs a very high penalty. Therefore, it is essential for SpMT to quantify the degree of dependences and to turn off speculation if the degree of dependences passes certain thresholds. This paper presents a technique that quantitatively computes dependences between loop iterations and such information can be used to determine if loop iterations can be executed in parallel by speculative threads. This technique can be broken into two steps. First probabilistic points-to analysis is performed to estimate the probabilities of points-to relationships in case there are pointer references in programs, and then the degree of dependences between loop iterations is computed quantitatively. Preliminary experimental results show compiler-directed thread-level speculation based on the information gathered by this technique can achieve significant performance improvement on SpMT.
- A. Berson, S. Smith, and K. Thearling. Building Data Mining Applications for CRM. McGraw-Hill, 1999. Google Scholar
Digital Library
- M. Burke, P. Carini, J.-D. Choi, and M. Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. In Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, Columbus, Ohio, August 1995. Google ScholarDigital Library
- M. C. Carlisle and A. Rogers. Software caching and computation migration in olden. In Proceedings of ACM SIGPLAN Conference on Principles and Practice of Parallel Programming, pages 29--39, July 1995. Google ScholarDigital Library
- R.-G. Chang, T.-R. Chuang, and J. K. Lee. Efficient support of parallel sparse computation for array intrinsic functions of Fortran 90. In Conference Proceedings of the 1998 International Conference on Supercomputing, pages 45--52, Melbourne, Australia, July 13--17, 1998. ACM SIGARCH. Google ScholarDigital Library
- R.-G. Chang, J.-S. Li, J. K. Lee, and T.-R. Chuang. Probabilistic inference schemes for sparsity structures of fortran 90 array intrinsics. In 2001 International Conference on Parallel Processing (ICPP '01, pages 61--68, Washington - Brussels - Tokyo, Sept. 2001. IEEE. Google ScholarDigital Library
- J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 232--245. ACM Press, 1993. Google ScholarDigital Library
- B. D. and T. Austin. The SimpleScalar Tool Set, Version 3.0. Unversity of Wisconsin Madison Computer Science Department.Google Scholar
- M. Das. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI-00), volume 35.5 of ACM Sigplan Notices, pages 35--46, N.Y., June ~18--21 2000. ACM Press. Google Scholar
- A. Deutsch. Interprocedural May-Alias analysis for pointers: Beyond k-limiting. SIGPLAN Notices, 29(6):230--241, June 1994. Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural Points-to analysis in the presence of function pointers. SIGPLAN Notices, 29(6):242--256, June 1994. Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- L. Hammond, B. Hubbert, M. Siu, M. Prabhu, M. Chen, and K. Olukotun. The stanford hydra cmp. IEEE MICRO Magazine, March-April 2000. Google ScholarDigital Library
- M. S. Hecht. Flow Analysis of Computer Programs. Elsevier North-Holland, New York, 1 edition, 1977. Google ScholarDigital Library
- G.-H. Hwang, J. K. Lee, and R. D.-C. Ju. A function-composition approach to synthesize Fortran~90 array operations. Journal of Parallel and Distributed Computing, 54(1):1--47, 10~Oct. 1998. Google ScholarDigital Library
- G.-H. Hwang, J. K. Lee, and R. D.-C. Ju. Array operation synthesis to optimize HPF programs on distributed memory machines. Journal of Parallel and Distributed Computing, 61(4):467--500, Apr. 2001. Google ScholarDigital Library
- Y.-S. Hwang, P.-S. Chen, J. K. Lee, and R. D.-C. Ju. Probabilistic points-to analysis. In Proceedings of the 2001 International Workshop on Languages and Compilers for Parallel Computing, August 2001. Google ScholarDigital Library
- Intel Corporation. IA-64 Application Developer's Architecture Guide, 1999.Google Scholar
- D.-C. R. Ju, J.-F. Collard, and K. Oukbir. Probabilistic memory disambiguation and its application to data speculation. In G. Lee and P.-C. Yew, editors, Third Workshop on Interaction between Compilers and Computer Architectures (INTERACT-3), San Jose, CA, Oct. 1998.Google Scholar
- B. W. Kernighan and D. M. Ritchie. The C programming language, Second Edition. Prentice Hall, 1988. Google ScholarDigital Library
- R. Krishnaiyer, D. Kulkarni, D. M. Lavery, W. Li, C.-C. Lim, J. Ng, and D. C. Sehr. An advanced optimizer for the ia-64 architecture. IEEE Micro, 20(6):60--68, November/December 2000. Google ScholarDigital Library
- V. Krishnan and J. Torrellas. A chip-multiprocessor architecture with speculative multithreading. IEEE Transactions on Computers, 48(9):866--880, 1999. Google ScholarDigital Library
- W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. SIGPLAN Notices, 27(7):235--248, July 1992. Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- J. K. Lee, D. Ho, and Y.-C. Chuang. Data distribution analysis and optimization for pointer based distributed programs. In Proceedings of the 1997 International Conference on Parallel Processing (ICPP '97), pages 56--63, Washington - Brussels - Tokyo, Aug. 1997. IEEE Computer Society Press. Google ScholarDigital Library
- Y.-J. Lin, Y.-S. Hwang, and J. K. Lee. Compiler optimizations with dsp-specific semantic descriptions. In Proceedings of the 2002 International Workshop on Languages and Compilers for Parallel Computing, July 2002. Google ScholarDigital Library
- S. S. Muchnick. Advanced compiler design and implementation. Morgan Kaufmann Publishers, 2929 Campus Drive, Suite 260, San Mateo, CA 94403, USA, 1997. Google ScholarDigital Library
- J. Oplinger, D. Heine, S.-W. Liao, B. A. Nayfeh, M. S. Lam, and K. Olukotun. Software and hardware for exploiting speculative parallelism with a multiprocessor. Technical Report CSL-TR-97-715, Stanford University, February 1997. Google ScholarDigital Library
- G. Ramalingam. Data flow frequency analysis. In Proceedings of the ACM SIGPLAN '96 conference on Programming language design and implementation, pages 267--277. ACM Press, 1996. Google ScholarDigital Library
- E. Ruf. Context-insensitive alias analysis reconsidered. SIGPLAN Notices, 30(6):13--22, June 1995. Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- R. Rugina and M. Rinard. Pointer analysis for multithreaded programs. In Proceedings of the ACM SIGPLAN '99 conference on Programming language design and implementation, pages 77--90. ACM Press, 1999. Google ScholarDigital Library
- M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In Conference Record of POPL '97: 24nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1--14, Paris, France, Jan. 1997. Google ScholarDigital Library
- M. D. Smith. The SUIF Machine Library. Division of of Engineering and Applied Science, Harvard University, March 1998.Google Scholar
- G. S. Sohi, S. E. Breach, and T. N. Vijaykumar. Multiscalar processors. In 25 Years ISCA: Retrospectives and Reprints, pages 521--532, 1998. Google ScholarDigital Library
- B. Steensgaard. Points-to analysis in almost linear time. In Conference Record of POPL '96: 23nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 32--41, St. Petersburg Beach, Florida, Jan. 1996. Google ScholarDigital Library
- B. Stroustrup. The C++ programming language. Addison-Wesley, 1991. Google ScholarDigital Library
- The Stanford SUIF Compiler Group. The SUIF Library. Stanford University, 1995.Google Scholar
- J.-Y. Tsai, J. Huang, C. Amlo, D. J. Lilja, and P.-C. Yew. The superthreaded processor architecture. IEEE Transactions on Computers, 48(9):881--902, 1999. Google ScholarDigital Library
- J.-Y. Tsai, Z. Jiang, and P.-C. Yew. Compiler techniques for the superthreaded architectures. International Journal of Parallel Programming, 27(1):1--19, 1999. Google ScholarDigital Library
- T. A. Wagner, V. Maverick, S. L. Graham, and M. A. Harrison. Accurate static estimators for program optimization. In Proceedings of the ACM SIGPLAN '94 conference on Programming language design and implementation, pages 85--96. ACM Press, 1994. Google ScholarDigital Library
- R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for c programs. In Proceedings of the conference on Programming language design and implementation, pages 1--12. ACM Press, 1995. Google ScholarDigital Library
- P. Wu, P. Feautrier, D. Padua, and Z. Sura. Instance-wise points-to analysis for loop-based dependence testing. In Proceedings of the 16th international conference on Supercomputing, pages 262--273. ACM Press, 2002. Google ScholarDigital Library
- S. H. Yong, S. Horwitz, and T. Reps. Pointer analysis for programs with structures and casting. SIGPLAN Notices, 34(5):91--103, May 1999. Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- Y.-P. You, C.-R. Lee, and J. K. Lee. Compiler analysis and supports for leakage power reduction on microprocessors. In Proceedings of the 2002 International Workshop on Languages and Compilers for Parallel Computing, July 2002. Google ScholarDigital Library
Index Terms
- Compiler support for speculative multithreading architecture with probabilistic points-to analysis
Recommendations
Compiler support for speculative multithreading architecture with probabilistic points-to analysis
Proceedings of the ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP 2003) and workshop on partial evaluation and semantics-based program manipulation (PEPM 2003)Speculative multithreading (SpMT) architecture can exploit thread-level parallelism that cannot be identified statically. Speedup can be obtained by speculatively executing threads in parallel that are extracted from a sequential program. However, ...
A thread partitioning approach for speculative multithreading
Speculative multithreading (SpMT) is a thread-level automatic parallelization technique, which partitions sequential programs into multithreads to be executed in parallel. This paper presents different thread partitioning strategies for nonloops and ...
Thread-Spawning Schemes for Speculative Multithreading
HPCA '02: Proceedings of the 8th International Symposium on High-Performance Computer ArchitectureSpeculative multithreading has been recently proposed to boost performance by means of exploiting thread-level parallelism in applications difficult to parallelize. The performance of these processors heavily depends on the partitioning policy used to ...
Comments