Tradeoffs in buffering speculative memory state for thread-level speculation in multiprocessors

ABSTRACT

Thread-Level Speculation (TLS) provides architectural support to aggressively run hard-to-analyze code in parallel. As speculative tasks run concurrently, they generate unsafe or speculative memory state that needs to be separately buffered and managed in the presence of distributed caches and buffers. Such a state may contain multiple versions of the same variable. In this paper, we introduce a novel taxonomy of approaches to buffer and manage multiversion speculative memory state in multiprocessors. We also present a detailed complexity-benefit tradeoff analysis of the different approaches. Finally, we use numerical applications to evaluate the performance of the approaches under a single architectural framework. Our key insights are that support for buffering the state of multiple speculative tasks and versions per processor is more complexity-effective than support for lazily merging the state of tasks with main memory. Moreover, both supports can be gainfully combined and, in large machines, their effect is nearly fully additive. Finally, the more complex support for storing future state in the main memory can boost performance when buffers are under pressure, but hurts performance when squashes are frequent.

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: Barnes, J. E. 1994. ftp://hubble.ifa.hawaii.edu/pub/barnes/treecode/. University of Hawaii.
• 3: 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]
• 4: 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
• 5: Rudolf Eigenmann , Jay Hoeflinger , David Padua, On the Automatic Parallelization of the Perfect Benchmarks®, IEEE Transactions on Parallel and Distributed Systems, v.9 n.1, p.5-23, January 1998 [doi>10.1109/71.655238]
• 6: Renato J. Figueiredo , José A. B. Fortes, Hardware Support for Extracting Coarse-Grain Speculative Parallelism in Distributed Shared-Memory Multiprocesors, Proceedings of the 2001 International Conference on Parallel Processing, p.214-226, September 03-07, 2001
• 7: Frank, M., Lee, W., and Amarasinghe, S. 2001. A Software Framework for Supporting General Purpose Applications on Raw Computation Fabrics. Tech. rep., MIT/LCS Technical Memo MIT-LCS-TM-619. July.
• 8: 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]
• 9: María Jesús Garzarán , Milos Prvulovic , Víctor Viñals , José María Llabería , Lawrence Rauchwerger , Josep Torrellas, Using Software Logging to Support Multi-Version Buffering in Thread-Level Speculation, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.170, September 27-October 01, 2003
• 10: 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
• 11: 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
• 12: 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
• 13: 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]
• 14: 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]
• 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: Milos Prvulovic , María Jesús Garzarán , Lawrence Rauchwerger , Josep Torrellas, Removing architectural bottlenecks to the scalability of speculative parallelization, Proceedings of the 28th annual international symposium on Computer architecture, p.204-215, June 30-July 04, 2001, Göteborg, Sweden
• 17: 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
• 18: Rundberg, P. and Stenström, P. 2000. Low-cost thread-level data dependence speculation on multiprocessors. In Fourth Workshop on Multithreaded Execution, Architecture and Compilation.
• 19: James E. Smith , Andrew R. Pleszkun, Implementing Precise Interrupts in Pipelined Processors, IEEE Transactions on Computers, v.37 n.5, p.562-573, May 1988 [doi>10.1109/12.4607]
• 20: 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
• 21: Steffan, J., Colohan, C. B., and Mowry, T. C. 1997. Architectural Support for Thread-Level Data Speculation. Tech. rep., CMU-CS-97-188, Carnegie Mellon University. November.
• 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: Tremblay, M. 1999. MAJC: Microprocessor Architecture for Java Computing. Hot Chips.
• 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: Ye Zhang , Josep Torrellas, Hardware for speculative run-time parallelization in distributed shared-memory multiprocessors, 1999
• 26: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Performance

Keywords:
Caching and buffering support, coherence protocol, memory hierarchies, shared-memory multiprocessors, thread-level speculation