Cluster prefetch: tolerating on-chip wire delays in clustered microarchitectures

ABSTRACT

The growing dominance of wire delays at future technology points renders a microprocessor communication-bound. Clustered microarchitectures allow most dependence chains to execute without being affected by long on-chip wire latencies. They also allow faster clock speeds and reduce design complexity, thereby emerging as a popular design choice for future microprocessors. However, a centralized data cache threatens to be the primary bottle-neck in highly clustered systems. The paper attempts to identify the most complexity-effective approach to alleviate this bottleneck. While decentralized cache organizations have been proposed, they introduce excessive logic and wiring complexity. The paper evaluates if the performance gains of a decentralized cache are worth the increase in complexity. We also introduce and evaluate the behavior of Cluster Prefetch - the forwarding of data values to a cluster through accurate address prediction. Our results show that the success of this technique depends on accurate speculation across unresolved stores. The technique applies for a wide class of processor models and most importantly, it allows high performance even while employing a simple centralized data cache. We conclude that address prediction holds more promise for future wire-delay-limited processors than decentralized cache organizations.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: A. Aggarwal and M. Franklin. An Empirical Study of the Scalability Aspects of Instruction Distribution Algorithms for Clustered Processors. In Proceedings of ISPASS, 2001.
• 3: Aneesh Aggarwal , Manoj Franklin, Hierarchical Interconnects for On-Chip Clustering, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.173, April 15-19, 2002
• 4: P. Ahuja, J. Emer, A. Klauser, and S. Mukherjee. Performance Potential of Effective Address Prediction of Load Instructions. In Proceedings of Workshop on Memory Performance Issues (in conjunction with ISCA-28), June 2001.
• 5: Rajeev Balasubramonian , Sandhya Dwarkadas , David H. Albonesi, Dynamically managing the communication-parallelism trade-off in future clustered processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 6: Amirali Baniasadi , Andreas Moshovos, Instruction distribution heuristics for quad-cluster, dynamically-scheduled, superscalar processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.337-347, December 2000, Monterey, California, United States [doi>10.1145/360128.360165]
• 7: Rajeev Barua , Walter Lee , Saman Amarasinghe , Anant Agarwal, Maps: a compiler-managed memory system for raw machines, Proceedings of the 26th annual international symposium on Computer architecture, p.4-15, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Michael Bekerman , Stephan Jourdan , Ronny Ronen , Gilad Kirshenboim , Lihu Rappoport , Adi Yoaz , Uri Weiser, Correlated load-address predictors, Proceedings of the 26th annual international symposium on Computer architecture, p.54-63, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Bryan Black , Brian Mueller , Stephanie Postal , Ryan Rakvic , Noppanunt Utamaphethai , John Paul Shen, Load execution latency reduction, Proceedings of the 12th international conference on Supercomputing, p.29-36, July 1998, Melbourne, Australia [doi>10.1145/277830.277842]
• 10: D. Burger and T. Austin. The Simplescalar Toolset, Version 2.0. Technical Report TR-97-1342, University of Wisconsin-Madison, June 1997.
• 11: R. Canal, J. M. Parcerisa, and A. Gonzalez. Dynamic Cluster Assignment Mechanisms. In Proceedings of HPCA-6, pages 132--142, January 2000.
• 12: Jean-Loup Baer , Tien-Fu Chen, Effective Hardware-Based Data Prefetching for High-Performance Processors, IEEE Transactions on Computers, v.44 n.5, p.609-623, May 1995 [doi>10.1109/12.381947]
• 13: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 14: Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The multicluster architecture: reducing cycle time through partitioning, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.149-159, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: Enric Gibert , Jesús Sánchez , Antonio González, Effective instruction scheduling techniques for an interleaved cache clustered VLIW processor, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 16: Enric Gibert , Jesús Sánchez , Antonio González, Flexible Compiler-Managed L0 Buffers for Clustered VLIW Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.315, December 03-05, 2003
• 17: José González , Antonio González, Speculative execution via address prediction and data prefetching, Proceedings of the 11th international conference on Supercomputing, p.196-203, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263631]
• 18: G. Hinton, D. Sager, M. Upton, D. Boggs, D. Carmean, A. Kyker, and P. Roussel. The Microarchitecture of the Pentium 4 Processor. Intel Technology Journal, Q1, 2001.
• 19: The Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.282, September 16-18, 2002
• 20: Stephem W. Keckler , William J. Dally, Processor coupling: integrating compile time and runtime scheduling for parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.202-213, May 19-21, 1992, Queensland, Australia
• 21: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 22: E. J. McLellan , D. A. Webb, The Alpha 21264 Microprocessor Architecture, Proceedings of the International Conference on Computer Design, p.90, October 05-05, 1998
• 23: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 24: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 25: Ramadass Nagarajan , Karthikeyan Sankaralingam , Doug Burger , Stephen W. Keckler, A design space evaluation of grid processor architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 26: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 27: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 28: Joan-Manuel Parcerisa , Antonio González, Reducing wire delay penalty through value prediction, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.317-326, December 2000, Monterey, California, United States [doi>10.1145/360128.360163]
• 29: Joan-Manuel Parcerisa , Julio Sahuquillo , Antonio González , José Duato, Efficient Interconnects for Clustered Microarchitectures, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.291, September 22-25, 2002
• 30: Paul Racunas , Yale N. Patt, Partitioned first-level cache design for clustered microarchitectures, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782820]
• 31: Narayan Ranganathan , Manoj Franklin, An empirical study of decentralized ILP execution models, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.272-281, October 02-07, 1998, San Jose, California, United States
• 32: Glenn Reinman , Brad Calder, Predictive techniques for aggressive load speculation, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.127-137, November 1998, Dallas, Texas, United States
• 33: Jesús Sánchez , Antonio González, Modulo scheduling for a fully-distributed clustered VLIW architecture, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.124-133, December 2000, Monterey, California, United States [doi>10.1145/360128.360142]
• 34: Yiannakis Sazeides , Stamatis Vassiliadis , James E. Smith, The performance potential of data dependence speculation & collapsing, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.238-247, December 02-04, 1996, Paris, France
• 35: P. Shivakumar and N. P. Jouppi. CACTI 3.0: An Integrated Cache Timing, Power, and Area Model. Technical Report TN-2001/2, Compaq Western Research Laboratory, August 2001.
• 36: J. Tendler, S. Dodson, S. Fields, H. Le, and B. Sinharoy. Power4 System Microarchitecture. Technical report, Technical White Paper, IBM, October 2001.
• 37: Dongning Liang, Dynamic Prediction of Critical Path Instructions, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.185, January 20-24, 2001
• 38: Victor V. Zyuban , Peter M. Kogge, Inherently Lower-Power High-Performance Superscalar Architectures, IEEE Transactions on Computers, v.50 n.3, p.268-285, March 2001 [doi>10.1109/12.910816]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.m Miscellaneous

General Terms:
Design

Keywords:
clustered microarchitectures, communication-bound processors, data prefetch, distributed caches, effective address and memory dependence prediction, processor