Architectural support for scalable speculative parallelization in shared-memory multiprocessors

ABSTRACT

Speculative parallelization aggressively executes in parallel codes that cannot be fully parallelized by the compiler. Past proposals of hardware schemes have mostly focused on single-chip multiprocessors (CMPs), whose effectiveness is necessarily limited by their small size. Very few schemes have attempted this technique in the context of scalable shared-memory systems. In this paper, we present and evaluate a new hardware scheme for scalable speculative parallelization. This design needs relatively simple hardware and is efficiently integrated into a cache-coherent NUMA system. We have designed the scheme in a hierarchical manner that largely abstracts away the internals of the node. We effectively utilize a speculative CMP as the building block for our scheme. Simulations show that the architecture proposed delivers good speedups at a modest hardware cost. For a set of important non-analyzable scientific loops, we report average speedups of 4.2 for 16 processors. We show that support for per-word speculative state is required by our applications, or else the performance suffers greatly.

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: 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 ]
• 3: 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 ]
• 4: 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
• 5: 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
• 6: 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 ]
• 7: 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
• 8: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 9: 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]
• 10: 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
• 11: 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 ]
• 12: 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
• 13: Shun-Tak Leung , John Zahorjan, Improving the performance of runtime parallelization, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.83-91, May 19-22, 1993, San Diego, California, United States
• 14: 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]
• 15: 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
• 16: 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
• 17: J. G. Steffan and T. C. Mowry. "Architectural Support for Thread- Level Data Speculation." Tech. Rep. CMU-CS-97-188, Carnegie Mellon University, November 1997.
• 18: 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
• 19: M. Tremblay. "MAJC: Microprocessor Architecture for Java Computing." Presentation at Hot Chips, August 1999.
• 20: 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 ]
• 21: 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
• 22: 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
• 23: Y. Zhang , L. Rauchwerger , J. Torrellas, Hardware for Speculative Parallelization of Partially-Parallel Loops in DSM Multiprocessors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.135, January 09-12, 1999
• 24: Ye Zhang , Josep Torrellas, Hardware for speculative run-time parallelization in distributed shared-memory multiprocessors, 1999

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Parallel

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design