A light-weight fairness mechanism for chip multiprocessor memory systems

ABSTRACT

Chip Multiprocessor (CMP) memory systems suffer from the effects of destructive thread interference. This interference reduces performance predictability because it depends heavily on the memory access pattern and intensity of the co-scheduled threads. In this work, we confirm that all shared units must be thread-aware in order to provide memory system fairness. However, the current proposals for fair memory systems are complex as they require an interference measurement mechanism and a fairness enforcement policy for all hardware-controlled shared units. Furthermore, they often sacrifice system throughput to reach their fairness goals which is not desirable in all systems.

In this work, we show that our novel fairness mechanism, called the Dynamic Miss Handling Architecture (DMHA), is able to reduce implementation complexity by using a single fairness enforcement policy for the complete hardware-managed shared memory system. Specifically, it controls the total miss bandwidth available to each thread by dynamically manipulating the number of Miss Status Holding Registers (MSHRs) available in each private data cache. When fairness is chosen as the metric of interest and we compare to a state-of-the-art fairness-aware memory system, DMHA improves fairness by 26% on average with the single program baseline. With a different configuration, DMHA improves throughput by 13% on average compared to a conventional memory system.

REFERENCES

• 1: Nathan L. Binkert , Ronald G. Dreslinski , Lisa R. Hsu , Kevin T. Lim , Ali G. Saidi , Steven K. Reinhardt, The M5 Simulator: Modeling Networked Systems, IEEE Micro, v.26 n.4, p.52-60, July 2006 [doi>10.1109/MM.2006.82]
• 2: Ramazan Bitirgen , Engin Ipek , Jose F. Martinez, Coordinated management of multiple interacting resources in chip multiprocessors: A machine learning approach, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.318-329, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771801]
• 3: Jichuan Chang , Gurindar S. Sohi, Cooperative cache partitioning for chip multiprocessors, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275005]
• 4: Vinodh Cuppu , Bruce Jacob , Brian Davis , Trevor Mudge, A performance comparison of contemporary DRAM architectures, Proceedings of the 26th annual international symposium on Computer architecture, p.222-233, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Stijn Eyerman , Lieven Eeckhout, System-Level Performance Metrics for Multiprogram Workloads, IEEE Micro, v.28 n.3, p.42-53, May 2008 [doi>10.1109/MM.2008.44]
• 6: K. I. Farkas , N. P. Jouppi, Complexity/performance tradeoffs with non-blocking loads, Proceedings of the 21st annual international symposium on Computer architecture, p.211-222, April 18-21, 1994, Chicago, Illinois, United States
• 7: Ron Gabor , Shlomo Weiss , Avi Mendelson, Fairness and Throughput in Switch on Event Multithreading, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.149-160, December 09-13, 2006 [doi>10.1109/MICRO.2006.25]
• 8: Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.157-168, August 28-30, 1996, Palo Alto, California, United States
• 9: Fei Guo , Yan Solihin , Li Zhao , Ravishankar Iyer, A Framework for Providing Quality of Service in Chip Multi-Processors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.343-355, December 01-05, 2007 [doi>10.1109/MICRO.2007.6]
• 10: Lisa R. Hsu , Steven K. Reinhardt , Ravishankar Iyer , Srihari Makineni, Communist, utilitarian, and capitalist cache policies on CMPs: caches as a shared resource, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152161]
• 11: Ravi Iyer, CQoS: a framework for enabling QoS in shared caches of CMP platforms, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006246]
• 12: Ravi Iyer , Li Zhao , Fei Guo , Ramesh Illikkal , Srihari Makineni , Don Newell , Yan Solihin , Lisa Hsu , Steve Reinhardt, QoS policies and architecture for cache/memory in CMP platforms, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 13: JEDEC Solid State Technology Association. DDR2 SDRAM Specification, May 2006.
• 14: 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]
• 15: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 16: K. Luo, J. Gummaraju, and M. Franklin. Balancing Throughput and Fairness in SMT Processors. ISPASS, 2001.
• 17: Onur Mutlu , Thomas Moscibroda, Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.146-160, December 01-05, 2007 [doi>10.1109/MICRO.2007.40]
• 18: Onur Mutlu , Thomas Moscibroda, Parallelism-Aware Batch Scheduling: Enhancing both Performance and Fairness of Shared DRAM Systems, Proceedings of the 35th International Symposium on Computer Architecture, p.63-74, June 21-25, 2008
• 19: Kyle J. Nesbit , Miquel Moreto , Francisco J. Cazorla , Alex Ramirez , Mateo Valero , James E. Smith, Multicore Resource Management, IEEE Micro, v.28 n.3, p.6-16, May 2008 [doi>10.1109/MM.2008.43]
• 20: Kyle J. Nesbit , Nidhi Aggarwal , James Laudon , James E. Smith, Fair Queuing Memory Systems, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.208-222, December 09-13, 2006 [doi>10.1109/MICRO.2006.24]
• 21: Kyle J. Nesbit , James Laudon , James E. Smith, Virtual private caches, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 22: Nauman Rafique , Won-Taek Lim , Mithuna Thottethodi, Architectural support for operating system-driven CMP cache management, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152160]
• 23: Nauman Rafique , Won-Taek Lim , Mithuna Thottethodi, Effective Management of DRAM Bandwidth in Multicore Processors, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.245-258, September 15-19, 2007 [doi>10.1109/PACT.2007.29]
• 24: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 25: 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
• 26: SPEC CPU 2000 Web Page. http://www.spec.org/cpu2000/.
• 27: D. Tarjan, S. Thoziyoor, and N. P. Jouppi. CACTI 4.0 Technical Report. 2006.
• 28: Li Zhao , Ravi Iyer , Ramesh Illikkal , Jaideep Moses , Srihari Makineni , Don Newell, CacheScouts: Fine-Grain Monitoring of Shared Caches in CMP Platforms, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.339-352, September 15-19, 2007 [doi>10.1109/PACT.2007.19]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

General Terms:
Design, Performance

Keywords:
chip multiprocessor, dynamic miss handling architecture, fairness, interference, mechanism, miss status holding register