Spatio-temporal memory streaming

ABSTRACT

Recent research advocates memory streaming techniques to alleviate the performance bottleneck caused by the high latencies of off-chip memory accesses. Temporal memory streaming replays previously observed miss sequences to eliminate long chains of dependent misses. Spatial memory streaming predicts repetitive data layout patterns within fixed-size memory regions. Because each technique targets a different subset of misses, their effectiveness varies across workloads and each leaves a significant fraction of misses unpredicted.

In this paper, we propose Spatio-Temporal Memory Streaming (STeMS) to exploit the synergy between spatial and temporal streaming. We observe that the order of spatial accesses repeats both within and across regions. STeMS records and replays the temporal sequence of region accesses and uses spatial relationships within each region to dynamically reconstruct a predicted total miss order. Using trace-driven and cycle-accurate simulation across a suite of commercial workloads, we demonstrate that with similar implementation complexity as temporal streaming, STeMS achieves equal or higher coverage than spatial or temporal memory streaming alone, and improves performance by 31%, 3%, and 18% over stride, spatial, and temporal prediction, respectively.

REFERENCES

• 1: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 2: Ioana Burcea , Stephen Somogyi , Andreas Moshovos , Babak Falsafi, Predictor virtualization, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 3: Jason F. Cantin , Mikko H. Lipasti , James E. Smith, Stealth prefetching, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 4: Chi F. Chen , Se-Hyun Yang , Babak Falsafi , Andreas Moshovos, Accurate and Complexity-Effective Spatial Pattern Prediction, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.276, February 14-18, 2004 [doi>10.1109/HPCA.2004.10010]
• 5: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 6: Yuan Chou, Low-Cost Epoch-Based Correlation Prefetching for Commercial Applications, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.301-313, December 01-05, 2007 [doi>10.1109/MICRO.2007.23]
• 7: Pedro Diaz , Marcelo Cintra, Stream chaining: exploiting multiple levels of correlation in data prefetching, Proceedings of the 36th annual international symposium on Computer architecture, June 20-24, 2009, Austin, TX, USA
• 8: Michael Ferdman , Thomas F. Wenisch , Anastasia Ailamaki , Babak Falsafi , Andreas Moshovos, Temporal instruction fetch streaming, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.1-10, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771774]
• 9: Craig G. Nevill-Manning and Ian H. Witten. Identifying hierarchical structure in sequences: A linear-time algorithm. Journal of Artificial Intelligence Research, 7, 1997.
• 10: Richard A. Hankins , Trung Diep , Murali Annavaram , Brian Hirano , Harald Eri , Hubert Nueckel , John P. Shen, Scaling and Charact rizing Database Workloads: Bridging the Gap between Research and Practice, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.151, December 03-05, 2003
• 11: Nikos Hardavellas, Ippokratis Pandis, Ryan Johnson, Naju G. Mancheril, Anastassia Ailamaki, and Babak Falsafi. Database servers on chip multiprocessors: Limitations and opportunities. In Proceedings of the 3rd Conference on Innovative Data Systems Research, Jan. 2007.
• 12: Ibrahim Hur , Calvin Lin, Memory Prefetching Using Adaptive Stream Detection, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.397-408, December 09-13, 2006 [doi>10.1109/MICRO.2006.32]
• 13: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 14: 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
• 15: Sanjeev Kumar , Christopher Wilkerson, Exploiting spatial locality in data caches using spatial footprints, Proceedings of the 25th annual international symposium on Computer architecture, p.357-368, June 27-July 02, 1998, Barcelona, Spain
• 16: Jack L. Lo , Luiz André Barroso , Susan J. Eggers , Kourosh Gharachorloo , Henry M. Levy , Sujay S. Parekh, An analysis of database workload performance on simultaneous multithreaded processors, Proceedings of the 25th annual international symposium on Computer architecture, p.39-50, June 27-July 02, 1998, Barcelona, Spain
• 17: Kyle J. Nesbit , James E. Smith, Data Cache Prefetching Using a Global History Buffer, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.96, February 14-18, 2004 [doi>10.1109/HPCA.2004.10030]
• 18: Minglong Shao , Anastassia Ailamaki , Babak Falsafi, DBmbench: fast and accurate database workload representation on modern microarchitecture, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.254-267, October 17-20, 2005, Toranto, Ontario, Canada
• 19: Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States [doi>10.1145/360128.360135]
• 20: Yan Solihin , Jaejin Lee , Josep Torrellas, Using a user-level memory thread for correlation prefetching, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 21: Stephen Somogyi , Thomas F. Wenisch , Anastassia Ailamaki , Babak Falsafi , Andreas Moshovos, Spatial Memory Streaming, Proceedings of the 33rd annual international symposium on Computer Architecture, p.252-263, June 17-21, 2006
• 22: Pedro Trancoso , Josep-L. Larriba-Pey , Zheng Zhang , Josep Torrellas, The Memory Performance of DSS Commercial Workloads in Shared-Memory Multiprocessors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.250, February 01-05, 1997
• 23: Thomas F. Wenisch , Anastasia Ailamaki , Babak Falsafi , Andreas Moshovos, Mechanisms for store-wait-free multiprocessors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 24: Thomas F. Wenisch, Michael Ferdman, Anastasia Ailamaki, Babak Falsafi, and Andreas Moshovos. Temporal streams in commercial server applications. In Proceedings of the International Symposium on Workload Characterization, Sep. 2008.
• 25: Thomas F. Wenisch, Michael Ferdman, Anastasia Ailamaki, Babak Falsafi, and Andreas Moshovos. Practical off-chip meta-data for address-correlated prefetching. In Proceedings of the 15th Symposium on High-Performance Computer Architecture, Feb. 2009.
• 26: Thomas F. Wenisch , Stephen Somogyi , Nikolaos Hardavellas , Jangwoo Kim , Anastassia Ailamaki , Babak Falsafi, Temporal Streaming of Shared Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.222-233, June 04-08, 2005
• 27: Thomas F. Wenisch , Roland E. Wunderlich , Michael Ferdman , Anastassia Ailamaki , Babak Falsafi , James C. Hoe, SimFlex: Statistical Sampling of Computer System Simulation, IEEE Micro, v.26 n.4, p.18-31, July 2006 [doi>10.1109/MM.2006.79]
• 28: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 29: Weifeng Zhang , Brad Calder , Dean M. Tullsen, A Self-Repairing Prefetcher in an Event-Driven Dynamic Optimization Framework, Proceedings of the International Symposium on Code Generation and Optimization, p.50-64, March 26-29, 2006 [doi>10.1109/CGO.2006.4]
• 30: Weifeng Zhang , Dean M. Tullsen , Brad Calder, Accelerating and Adapting Precomputation Threads for Effcient Prefetching, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.85-95, February 10-14, 2007 [doi>10.1109/HPCA.2007.346187]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Design, Experimentation, Performance

Keywords:
prefetching, spatial correlation, temporal correlation