Service level agreement for multithreaded processors

ABSTRACT

Multithreading is widely used to increase processor throughput. As the number of shared resources increase, managing them while guaranteeing predicted performance becomes a major problem. Attempts have been made in previous work to ease this via different fairness mechanisms. In this article, we present a new approach to control the resource allocation and sharing via a service level agreement (SLA)-based mechanism; that is, via an agreement in which multithreaded processors guarantee a minimal level of service to the running threads. We introduce a new metric, C_SLA, for conformance to SLA in multithreaded processors and show that controlling resources using with SLA allows for higher gains than are achievable by previously suggested fairness techniques. It also permits improving one metric (e.g., power) while maintaining SLA in another (e.g., performance). We compare SLA enforcement to schemes based on other fairness metrics, which are mostly targeted at equalizing execution parameters. We show that using SLA rather than fairness based algorithms provides a range of acceptable execution points from which we can select the point that best fits our optimization target, such as maximizing the weighted speedup (sum of the speedups of the individual threads) or reducing power. We demonstrate the effectiveness of the new SLA approach using switch-on-event (coarse-grained) multithreading. Our weighted speedup improvement scheme successfully enforces SLA while improving the weighted speedup by an average of 10% for unbalanced threads. This result is significant when compared with performance losses that may be incurred by fairness enforcement methods. When optimizing for power reduction in unbalanced threads SLA enforcement reduces the power by an average of 15%. SLA may be complemented by other power reduction methods to achieve further power savings and maintain the same service level for the threads. We also demonstrate differentiated SLA, where weighted speedup is maximized while each thread may have a different throughput constraint.

REFERENCES

• 1: Haitham Akkary , Srikanth T. Srinivasan , Rajendar Koltur , Yogesh Patil , Wael Refaai, Perceptron-Based Branch Confidence Estimation, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.265, February 14-18, 2004 [doi>10.1109/HPCA.2004.10002]
• 2: Avi-Itzhak, B. and Levy, H. 2004. On measuring fairness in queues. Adv. Appl. Probab. 36, 3, 919--936.
• 3: Bennett, J. and Zhang, H. 1996. WF2Q: worst-case fair weighted fair queueing. In Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies. IEEE, 1.
• 4: Borkenhagen, J. M., Eickemeyer, R. J., Kalla, R. N., and Kunkel, S. R. 2000. A multi-threaded PowerPC processor for commercial servers. IBM J. Res. Dev. 44, 6, 885--898.
• 5: David Brooks , Margaret Martonosi, Dynamic Thermal Management for High-Performance Microprocessors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.171, January 20-24, 2001
• 6: Cazorla, F., Fernandez, E., Ramirez, A., and Valero, M. 2003. Improving memory latency aware fetch policies for SMT processors. In Proceedings of the 5th International Symposium on High-Performance Computing. Springer.
• 7: Francisco J. Cazorla , Peter M. W. Knijnenburg , Rizos Sakellariou , Enrique Fernandez , Alex Ramirez , Mateo Valero, Predictable Performance in SMT Processors: Synergy between the OS and SMTs, IEEE Transactions on Computers, v.55 n.7, p.785-799, July 2006 [doi>10.1109/TC.2006.108]
• 8: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Peter M. W. Knijnenburg , Rizos Sakellariou , Enrique Fernández, QoS for High-Performance SMT Processors in Embedded Systems, IEEE Micro, v.24 n.4, p.24-31, July 2004 [doi>10.1109/MM.2004.37]
• 9: Cazorla, F. J., Knijnenburg, P. M., Sakellariou, R., Fernandez, E., Ramirez, A., and Valero, M. 2004. Feasibility of QoS for SMT by resource allocation. In Proceedings of the International Euro-Par Conference. Springer, 535--540.
• 10: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Enrique Fernandez, Dynamically Controlled Resource Allocation in SMT Processors, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.171-182, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.17]
• 11: 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]
• 12: Chen, S. and Ma, P. 2007. FROCM: A fair and low-overhead method in SMT processor. In Proceedings of the 3rd International Conference on High-Performance Computing and Communications. Springer.
• 13: Cooksey, R., Jourdan, S., and Grunwald, D. 2002. A stateless, content-directed data prefetching mechanism. SIGOPS Oper. Syst. Rev. 36, 5, 279--290.
• 14: CPU2000. Standard Performance Evaluation Corporation, Spec CPU2000.
• 15: Richard J. Eickemeyer , Ross E. Johnson , Steven R. Kunkel , Beng-Hong Lim , Mark S. Squillante , Ching-Farn Eric Wu, Evaluation of Multithreaded Processors and Thread-Switch Policies, Proceedings of the International Symposium on High Performance Computing, p.75-90, November 04-06, 1997
• 16: Ayose Falcon , Jared Stark , Alex Ramirez , Konrad Lai , Mateo Valero, Prophet/Critic Hybrid Branch Prediction, ACM SIGARCH Computer Architecture News, v.32 n.2, p.250, March 2004
• 17: Matthew K. Farrens , Andrew R. Pleszkun, Strategies for achieving improved processor throughput, Proceedings of the 18th annual international symposium on Computer architecture, p.362-369, May 27-30, 1991, Toronto, Ontario, Canada
• 18: 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]
• 19: Ron Gabor , Shlomo Weiss , Avi Mendelson, Fairness enforcement in switch on event multithreading, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.3, p.15-es, September 2007 [doi>10.1145/1275937.1275939]
• 20: Golestani, S. 1994. A self-clocked fair queueing scheme for broadband applications. In Proceedings of the 13th Annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM'94). IEEE, 636--646.
• 21: Pawan Goyal , Simon S. Lam , Harrick M. Vin, Determining end-to-end delay bounds in heterogeneous networks, Multimedia Systems, v.5 n.3, p.157-163, May 1997 [doi>10.1007/s005300050052]
• 22: 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]
• 23: Gwennap, L. 1995. Intel's P6 uses decoupled superscalar design. Micro-processor Rep. 9, 2.
• 24: Halfhill, T. R. 2006. Intel goes quad. Micro-processor Rep.
• 25: 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]
• 26: 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]
• 27: 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
• 28: Jain, R., Chiu, D., and Hawe, W. 1998. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Arxiv preprint cs.NI/9809099. http://adsabs.harvard.edu/abs/1998cs........9099J
• 29: 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]
• 30: Masaaki Kondo , Hiroshi Sasaki , Hiroshi Nakamura, Improving fairness, throughput and energy-efficiency on a chip multiprocessor through DVFS, ACM SIGARCH Computer Architecture News, v.35 n.1, March 2007 [doi>10.1145/1241601.1241609]
• 31: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 32: Krewell, K. 2006. Intel looks to core for success. Micro-processor Rep.
• 33: Jae W. Lee , Krste Asanovic, METERG: Measurement-Based End-to-End Performance Estimation Technique in QoS-Capable Multiprocessors, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, p.135-147, April 04-07, 2006 [doi>10.1109/RTAS.2006.29]
• 34: Luo, K., Gummaraju, J., and Franklin, M. 2001. Balancing throughput and fairness in SMT processors. In Proceedings of the International Symposium on Performance Analysis of Systems and Software. IEEE, 164--171.
• 35: McGregor, J. 2007. The New x86 Landscape. Micro-processor rep.
• 36: Cameron McNairy , Rohit Bhatia, Montecito: A Dual-Core, Dual-Thread Itanium Processor, IEEE Micro, v.25 n.2, p.10-20, March 2005 [doi>10.1109/MM.2005.34]
• 37: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 38: 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]
• 39: 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
• 40: Steve Pawlowski, Petascale Computing Research Challenges - A Manycore Perspective, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.96, February 10-14, 2007 [doi>10.1109/HPCA.2007.346188]
• 41: Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
• 42: Raasch, S. E. and Reinhardt, S. K. 1999. Applications of thread prioritization in SMT processors. In Proceedings of the Workshop on Multi-threaded Execution and Compilation. ACM.
• 43: Steven E. Raasch , Steven K. Reinhardt, The Impact of Resource Partitioning on SMT Processors, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.15, September 27-October 01, 2003
• 44: 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]
• 45: David Raz , Hanoch Levy , Benjamin Avi-Itzhak, A resource-allocation queueing fairness measure, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
• 46: Mendel Rosenblum , Tal Garfinkel, Virtual Machine Monitors: Current Technology and Future Trends, Computer, v.38 n.5, p.39-47, May 2005 [doi>10.1109/MC.2005.176]
• 47: Singhal, R., Venkatraman, K., Cohn, E., Holm, J., Koufaty, D., Lin, M.-J., Madhav, M., Mattwandel, M., Nidhi, N., Pearce, J., and Seshadri, M. 2004. Performance analysis and validation of the Intel Pentium4 processor on 90nm technology. Intel Tech. J. 8.
• 48: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous mutlithreading processor, ACM SIGPLAN Notices, v.35 n.11, p.234-244, Nov. 2000 [doi>10.1145/356989.357011]
• 49: Tarjan, D., Thoziyoor, S., and Jouppi, N. 2006. CACTI 4.0. Tech. rep. HP Laboratories.
• 50: Radhika Thekkath , Susan J. Eggers, The effectiveness of multiple hardware contexts, ACM SIGPLAN Notices, v.29 n.11, p.328-337, Nov. 1994
• 51: Nathan Tuck , Dean M. Tullsen, Initial Observations of the Simultaneous Multithreading Pentium 4 Processor, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.26, September 27-October 01, 2003
• 52: Dean M. Tullsen , Jeffery A. Brown, Handling long-latency loads in a simultaneous multithreading processor, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 53: Yung-Terng Wang , R. J. T. Morris, Load Sharing in Distributed Systems, IEEE Transactions on Computers, v.34 n.3, p.204-217, March 1985 [doi>10.1109/TC.1985.1676564]
• 54: Adam Wierman , Mor Harchol-Balter, Classifying scheduling policies with respect to unfairness in an M/GI/1, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 55: Thomas Y. Yeh , Glenn Reinman, Fast and fair: data-stream quality of service, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086328]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

General Terms:
Design, Performance

Keywords:
Service level agreement, fairness, performance, power, throughput