Fast and fair: data-stream quality of service

ABSTRACT

Chip multiprocessors have the potential to exploit thread level parallelism, particularly in the context of embedded server farms where the available number of threads can be quite high. Unfortunately, both per-core and overall throughput are significantly impacted by the organization of the lowest level on-chip cache. On-chip caches for CMPs must be able to handle the increased demand and contention of multiple cores. To complicate the problem, cache demand changes dynamically with phases changes, context switches, power saving features, and assignments to asymmetric cores.We propose PDAS, a distributed NUCA L2 cache design with an adaptive sharing mechanism. Each core independently measures its dynamic need, and all cache resources are managed to increase utilization, reduce migrations, and lower interference. Per-core performance degradation is bounded while overall throughput is optimized, thus qualitatively improving performance of embedded systems where quality-of-service is an important characteristic.In single thread mode, PDAS, on average, improves by 26%, 27%, and 13% over Private, Shared, and NUCA caches respectively. This improvement is achieved while reducing internal migrations on average by 82% as compared to the NUCA. With thread contention, PDAS increases its performance and power advantage over prior work. The average migration reduction over NUCA increases to over 90%, and average IPC improvements over NUCA are 30%, 14%, and 35% for 2T, 3T, and 4T scenarios.

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: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 3: Luiz André Barroso , Kourosh Gharachorloo , Robert McNamara , Andreas Nowatzyk , Shaz Qadeer , Barton Sano , Scott Smith , Robert Stets , Ben Verghese, Piranha: a scalable architecture based on single-chip multiprocessing, Proceedings of the 27th annual international symposium on Computer architecture, p.282-293, June 2000, Vancouver, British Columbia, Canada
• 4: Bradford M. Beckmann , David A. Wood, Managing Wire Delay in Large Chip-Multiprocessor Caches, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.319-330, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.21]
• 5: M. Bohr. Interconnect scaling - the real limiter to high-performance ulsi. In Tech. Dig. of the International Electron Devices Meeting, pages 241--244, December 1995.
• 6: Broadcom. Bcm1480 product brief.
• 7: D. C. Burger and T. M. Austin. The simplescalar tool set, version 2.0. Technical Report CS-TR-97-1342, U. of Wisconsin, Madison, June 1997.
• 8: Jose G. Castanos , Luis Ceze , Karin Strauss , Henry S. Warren Jr, Evaluation of a Multithreaded Architecture for Cellular Computing, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.311, February 02-06, 2002
• 9: D. Chiou, P. Jain, S. Devadas, and L. Rudolph. Dynamic cache partitioning via columnization. In Proceedings of Design Automation Conference, Los Angeles, June 2000.
• 10: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Distance Associativity for High-Performance Energy-Efficient Non-Uniform Cache Architectures, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.55, December 03-05, 2003
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, p.233, May 25-29, 2002, Anchorage, Alaska
• 13: S. Hily and A. Seznec. Standard memory hierarchy does not fit simultaneous multithreading. In Proceedings of MTEAC'98 Workshop, 1998.
• 14: H. Hofstee. Power efficient processor design and the cell processor. In Proceedings of the 8th International Symposium on High Performance Computer Architecture (HPCA), 2005.
• 15: Jaehyuk Huh , Doug Burger , Stephen W. Keckler, Exploring the Design Space of Future CMPs, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.199-210, September 08-12, 2001
• 16: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 17: Seongbeom Kim , Dhruba Chandra , Yan Solihin, Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, September 29-October 03, 2004 [doi>10.1109/PACT.2004.15]
• 18: Xianfeng Li , Hemendra Singh Negi , Tulika Mitra , Abhik Roychoudhury, Design space exploration of caches using compressed traces, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006227]
• 19: Chun Liu , Anand Sivasubramaniam , Mahmut Kandemir, Organizing the Last Line of Defense before Hitting the Memory Wall for CMPs, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.176, February 14-18, 2004 [doi>10.1109/HPCA.2004.10017]
• 20: Pierre Michaud, Exploiting the Cache Capacity of a Single-Chip Multi-Core Processor with Execution Migration, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.186, February 14-18, 2004 [doi>10.1109/HPCA.2004.10026]
• 21: 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
• 22: K. Olukotun P. Kongetira, K. Aingaran. Niagara: A 32-way multithreaded sparc processor.
• 23: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Reconfigurable caches and their application to media processing, Proceedings of the 27th annual international symposium on Computer architecture, p.214-224, June 2000, Vancouver, British Columbia, Canada
• 24: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 25: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 26: P. Shivakumar and Norman P. Jouppi. Cacti 3.0: An integrated cache timing, power, and area model. In Technical Report, 2001.
• 27: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 28: J. Stokes. Inside the xbox 360.
• 29: Harold S. Stone , John Turek , Joel L. Wolf, Optimal Partitioning of Cache Memory, IEEE Transactions on Computers, v.41 n.9, p.1054-1068, September 1992 [doi>10.1109/12.165388]
• 30: Rabin A. Sugumar , Santosh G. Abraham, Set-associative cache simulation using generalized binomial trees, ACM Transactions on Computer Systems (TOCS), v.13 n.1, p.32-56, Feb. 1995 [doi>10.1145/200912.200918]
• 31: G. Edward Suh , Srinivas Devadas , Larry Rudolph, A New Memory Monitoring Scheme for Memory-Aware Scheduling and Partitioning, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.117, February 02-06, 2002
• 32: G. E. Suh , L. Rudolph , S. Devadas, Dynamic Partitioning of Shared Cache Memory, The Journal of Supercomputing, v.28 n.1, p.7-26, April 2004 [doi>10.1023/B:SUPE.0000014800.27383.8f]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Performance

Keywords:
CMP, NUCA, PDAS, QOS, adaptive, bandwidth, cache, chip multiprocessor, cluster, data-stream, distributed, embedded, memory wall, migration, non-uniform access, partition, per thread degradation, phase