Characterizing and modeling the behavior of context switch misses

ABSTRACT

One of the essential features in modern computer systems is context switching, which allows multiple threads of execution to time-share a limited number of processors. While very useful, context switching can introduce high performance overheads, with one of the primary reasons being the cache perturbation effect. Between the time a thread is switched out and when it resumes execution, parts of its working set in the cache may be perturbed by other interfering threads, leading to (context switch) cache misses to recover from the perturbation.

The goal of this paper is to understand how cache parameters and application behavior influence the number of context switch misses the application suffers from. We characterize a previously-unreported type of context switch misses that occur as the artifact of the interaction of cache replacement policy and an application's temporal reuse behavior. We characterize the behavior of these "reordered misses" for various applications, cache sizes, and the amount of cache perturbation. As a second contribution, we develop an analytical model that reveals the mathematical relationship between cache design parameters, an application's temporal reuse pattern, and the number of context switch misses the application suffers from. We validate the model against simulation studies and find that it is accurate in predicting the trends of context switch misses. The mathematical relationship provided by the model allows us to derive insights into precisely why some applications are more vulnerable to context switch misses than others. Through a case study, we also find that prefetching tends to aggravate the number of context switch misses.

REFERENCES

• 1: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 2: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 3: Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782836]
• 4: Calin Cascaval , Luiz De Rose , David A. Padua , Daniel A. Reed, Compile-Time Based Performance Prediction, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.365-379, August 04-06, 1999
• 5: Francis M. David , Jeffrey C. Carlyle , Roy H. Campbell, Context switch overheads for Linux on ARM platforms, Proceedings of the 2007 workshop on Experimental computer science, p.3-es, June 13-14, 2007, San Diego, California [doi>10.1145/1281700.1281703]
• 6: R. Fromm and N. Treuhaft. Revisiting the Cache Interference Costs of Context Switches. http://citeseer.ist.psu.edu/252861.html, 1996.
• 7: G. Edward Suh , Srinivas Devadas , Larry Rudolph, Analytical cache models with applications to cache partitioning, Proceedings of the 15th international conference on Supercomputing, p.1-12, June 2001, Sorrento, Italy [doi>10.1145/377792.377797]
• 8: 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, (1Q), 2001.
• 9: Fei Guo , Yan Solihin, An analytical model for cache replacement policy performance, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 10: IBM. IBM Power4 System Architecture White Paper, 2002.
• 11: 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
• 12: P. Koka and M. H. Lipasti. Opportunities for Cache Friendly Process Scheduling. In Workshop on Interaction Between Operating Systems and Computer Architecture, 2005.
• 13: Hantak Kwak , Ben Lee , Ali R. Hurson , Suk-Han Yoon , Woo-Jong Hahn, Effects of Multithreading on Cache Performance, IEEE Transactions on Computers, v.48 n.2, p.176-184, February 1999 [doi>10.1109/12.752659]
• 14: Chuanpeng Li , Chen Ding , Kai Shen, Quantifying the cost of context switch, Proceedings of the 2007 workshop on Experimental computer science, p.2-es, June 13-14, 2007, San Diego, California [doi>10.1145/1281700.1281702]
• 15: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 16: R. L. Mattson, J. Gecsei, D. Slutz, and I. Traiger. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal, 9(2):78--117, 1970.
• 17: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• 18: Standard Performance Evaluation Corporation. Spec cpu2006 benchmarks. http://www.spec.org, 2006.
• 19: 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
• 20: Dominique Thiebaut , Harold S. Stone, Footprints in the cache, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.305-329, Nov. 1987 [doi>10.1145/29868.32979]
• 21: Dan Tsafrir, The context-switch overhead inflicted by hardware interrupts (and the enigma of do-nothing loops), Proceedings of the 2007 workshop on Experimental computer science, p.4-es, June 13-14, 2007, San Diego, California [doi>10.1145/1281700.1281704]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
analytical model, context switch misses, prefetching, stack distance profiling