Removing architectural bottlenecks to the scalability of speculative parallelization

ABSTRACT

Speculative thread-level parallelization is a promising way to speed up codes that compilers fail to parallelize. While several speculative parallelization schemes have been proposed for different machine sizes and types of codes, the results so far show that it is hard to deliver scalable speedups. Often, the problem is not true dependence violations, but sub-optimal architectural design. Consequently, we attempt to identify and eliminate major architectural bottlenecks that limit the scalability of speculative parallelization. The solutions that we propose are: low-complexity commit in constant time to eliminate the task commit bottleneck, a memory-based overflow area to eliminate stall due to speculative buffer overflow, and exploiting high-level access patterns to minimize speculation-induced traffic. To show that the resulting system is truly scalable, we perform simulations with up to 128 processors. With our optimizations, the speedups for 128 and 64 processors reach 63 and 48, respectively. The average speedup for 64 processors is 32, nearly four times higher than without our optimizations.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: J. Barnes. ftp://hubble.ifa.hawaii.edu/pub/barnes/treecode/. University of Hawaii, 1994.
• 3: M. Berry et al. The Perfect Club Benchmarks: Effective Performance Evaluation of Supercomputers. International Journal of Supercompurer Applications, 3(3):5--40, Fall 1989.
• 4: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 5: Marcelo Cintra , José F. Martínez , Josep Torrellas, Architectural support for scalable speculative parallelization in shared-memory multiprocessors, Proceedings of the 27th annual international symposium on Computer architecture, p.13-24, June 2000, Vancouver, British Columbia, Canada
• 6: 1. Duff, R. Schreiber, and P. Havlak. HPF-2 Scope of Activities and Motivating Applications. Technical Report CRPC-TR94492, Rice University, November 1994.
• 7: S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
• 8: Manish Gupta , Rahul Nim, Techniques for speculative run-time parallelization of loops, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
• 9: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.58-69, October 02-07, 1998, San Jose, California, United States
• 10: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 11: Tom Knight, An architecture for mostly functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.105-112, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319854]
• 12: V. Krishnan , J. Torrellas, An Direct-Execution Framework for Fast and Accurate Simulation of Superscalar Processors, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.286, October 12-18, 1998
• 13: 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]
• 14: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 15: Pedro Marcuello , Antonio González, Clustered speculative multithreaded processors, Proceedings of the 13th international conference on Supercomputing, p.365-372, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305214]
• 16: A. Nowatzyk, G, Aybay, M. Browne, E. Kelly, M. Parkin, B. Radke, and S. Vishin. The S3.mp Scalable Shared Memory Multiprocessor. In Proceedings of the 1995 International Conference on Parallel Processing, pages I1-I10, August 1995.
• 17: Jeffrey T. Oplinger , David L. Heine , Monica S. Lam, In Search of Speculative Thread-Level Parallelism, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.303, October 12-16, 1999
• 18: M. Prvulovic. Removing Architectural Bottlenecks to the Scalability of Speculative Parallelization. Masters Thesis, Computer Science Department, University of lllinois at Urbana-Champaign, November 2000.
• 19: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.218-232, June 18-21, 1995, La Jolla, California, United States
• 20: P. Rundberg and P. Stenstrom. Low-Cost Thread-Level Data Dependence Speculation on Multiprocessors. In Fourth Workshop on Multithreaded Execution, Architecture and Compilation, December 2000.
• 21: 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
• 22: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 23: M. Tremblay, MAJC: Microprocessor Architecture for Java Computing. Hot Chips, August 1999.
• 24: Jenn-Yaun Tsai , Jian Huang , Christoffer Amlo , David J. Lilja , Pen-Chung Yew, The Superthreaded Processor Architecture, IEEE Transactions on Computers, v.48 n.9, p.881-902, September 1999 [doi>10.1109/12.795219]
• 25: Jack E. Veenstra , Robert J. Fowler, MINT: A Front End for Efficient Simulation of Shared-Memory Multiprocessors, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.201-207, January 31-February 02, 1994
• 26: Y. Zhang, L. Rauchwerger, and J. Torrellas. A Unified Approach to Speculative Parallelization of Loops in DSM Multipi-ocessors. Technical Report 1542, University of Illinois at Urbana-Champaign, Center for Supercomputing Research and Development, October 1998.
• 27: L. Rauchwerger Y. Zhan , J. Torrellas, Hardware for Speculative Run-Time Parallelization in Distributed Shared-Memory Multiprocessors, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.162, January 31-February 04, 1998

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

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