Temporally silent stores

ABSTRACT

Recent work has shown that silent stores--stores which write a value matching the one already stored at the memory location--occur quite frequently and can be exploited to reduce memory traffic and improve performance. This paper extends the definition of silent stores to encompass sets of stores that change the value stored at a memory location, but only temporarily, and subsequently return a previous value of interest to the memory location. The stores that cause the value to revert are called temporally silent stores. We redefine multiprocessor sharing to account for temporal silence and show that in the limit, up to 45% of communication misses in scientific and commercial applications can be eliminated by exploiting values that change only temporarily. We describe a practical mechanism that detects temporally silent stores and removes the coherence traffic they cause in conventional multiprocessors. We find that up to 42% of communication misses can be eliminated with a simple extension to the MESI protocol. Further, we examine application and operating system code to provide insight into the temporal silence phenomenon and characterize temporal silence by examining value frequencies and dynamic instruction distances between temporally silent pairs. These studies indicate that the operating system is involved heavily in temporal silence, in both commercial and scientific workloads, and that while detectable synchronization primitives provide substantial contributions, significant opportunity exists outside these references.

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: A. Alameldeen, C. Mauer, M. Xu, P. Harper, M. Martin, D. Sorin, M. Hill, and D. Wood. Evaluating non-deterministic multi-threaded commercial workloads. In Proceedings of Computer Architecture Evaluation using Commercial Workloads (CAECW-02), February 2002.
• 3: Luiz André Barroso , Kourosh Gharachorloo , Edouard Bugnion, Memory system characterization of commercial workloads, Proceedings of the 25th annual international symposium on Computer architecture, p.3-14, June 27-July 02, 1998, Barcelona, Spain
• 4: Gordon B. Bell , Kevin M. Lepak , Mikko H. Lipasti, Characterization of Silent Stores, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.133, October 15-19, 2000
• 5: J. Borkenhagen and S. Storino. 5th Generation 64-bit Power-PC-Compatible Commercial Processor Design. IBM White-paper available from http://www.rs6000.ibm.com, 1999.
• 6: H. W. Cain, R. Rajwar, M. Marden, and M. H. Lipasti. An architectural characterization of java tpc-w. In Proc. of HPCA-7, January 2001.
• 7: Marcelo Cintra , Josep Torrellas, Eliminating Squashes Through Learning Cross-Thread Violations in Speculative Parallelization for Multiprocessors, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.43, February 02-06, 2002
• 8: IBM Corporation. AIX v4.3 online documentation. http://nc-sp.upenn.edu/aix4.3html/, 2002.
• 9: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: Michel Dubois , Jonas Skeppstedt , Livio Ricciulli , Krishnan Ramamurthy , Per Stenström, The detection and elimination of useless misses in multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.88-97, May 16-19, 1993, San Diego, California, United States
• 11: J. R. Goodman , P. J. Woest, The Wisconsin multicube: a new large-scale cache-coherent multiprocessor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.422-431, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 12: Stefanos Kaxiras , James R. Goodman, Improving CC-NUMA Performance Using Instruction-Based Prediction, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.161, January 09-12, 1999
• 13: T. Keller, A. M. Maynard, R. Simpson, and P. Bohrer. Simos-ppc full system simulator. http://www.cs.utexas.edu/users/cart/simOS.
• 14: Tim Horel , Gary Lauterbach, UltraSPARC-III: Designing Third-Generation 64-Bit Performance, IEEE Micro, v.19 n.3, p.73-85, May 1999 [doi>10.1109/40.768506]
• 15: Kevin M. Lepak , Gordon B. Bell , Mikko H. Lipasti, Silent Stores and Store Value Locality, IEEE Transactions on Computers, v.50 n.11, p.1174-1190, November 2001 [doi>10.1109/12.966493]
• 16: Kevin M. Lepak , Mikko H. Lipasti, On the value locality of store instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.182-191, June 2000, Vancouver, British Columbia, Canada
• 17: Kevin M. Lepak , Mikko H. Lipasti, Silent stores for free, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.22-31, December 2000, Monterey, California, United States [doi>10.1145/360128.360133]
• 18: Milo M. K. Martin , Daniel J. Sorin , Anastassia Ailamaki , Alaa R. Alameldeen , Ross M. Dickson , Carl J. Mauer , Kevin E. Moore , Manoj Plakal , Mark D. Hill , David H. Wood, Timestamp snooping: an approach for extending SMPs, ACM SIGPLAN Notices, v.35 n.11, p.25-36, Nov. 2000 [doi>10.1145/356989.356992]
• 19: C. Moore. POWER4 system microarchitecture. In Proceedings of the Microprocessor Forum, October 2000.
• 20: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 21: J. Gregory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, Improving Value Communication for Thread-Level Speculation, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.65, February 02-06, 2002
• 22: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy