The susceptibility of programs to context switching

Modern memory systems are composed of several levels of caching. The design of these levels is largely an empirical practice. One highly-effective empirical method is the single-pass method wherein all caches in a broad design space are evaluated in one pass over the trace. Multiprogramming degrades memory system performance since context switching reduces the effectiveness of cache memories. Few single-pass methods exist which account for multiprogramming effects. This paper uses a general model of single-pass algorithms, the recurrence/conflict model, and extends the model for recording the effects due to both voluntary context switches and involuntary context switches. Involuntary context switches are modeled using the distribution of lengths between a reference to an address and the re-reference to the same address. The paper makes the assumptions that involuntary context switches are equally likely to occur between each reference, and that one can independently estimate f_CS, the fraction of a cache´s contents flushed between context switches. The case where f_CS=1 is used to measure the effect of worst-case context switch penalty (the susceptibility) of several members of the SPEC89 benchmark set to context switching. Some empirical results of F_CS are presented to illustrate the case where f_CS<1. The model is validated against its assumptions by comparing its results with more restrictive methods