Carnegie Mellon University Technical Report CMU-CS-02-113, March 2002.
Stavros Harizopoulos and Anastassia Ailamaki
School of Computer Science
Carnegie Mellon University
5000 Forbes Ave.
Pittsburgh, PA 15213
http://www.pdl.cmu.edu/
Modern servers typically process request streams by assigning a worker thread to a request, and rely on a round robin policy for context-switching. Although this programming paradigm is intuitive, it is oblivious to the execution state and ignores each software module’s affinity to the processor caches. As a result, resumed threads of execution suffer additional delays due to conflict and com-pulsory misses while populating the caches with their evicted working sets. Alternatively, the staged programming paradigm divides computation into stages and allows for stage-based (rather than request thread-based) cohort scheduling that improves module affinity.
This technical report introduces (a) four novel cohort scheduling techniques for staged software servers that follow a "production-line" model of operation, and (b) a mathematical framework to methodically quantify the performance trade-offs when using these techniques. Our Markov chain analysis of one of the scheduling techniques matches the simulation results. Using our model on a staged database server, we found that the proposed policies exploit data and instruction locality for a wide range of workload parameter values and outperform traditional techniques such as FCFS and processor-sharing. Consequently, our results justify the restructuring of a wide class of software servers to incorporate the staged programming paradigm. \\
KEYWORDS: DBMS, databases, performance, staged server, scheduling, cache-conscious.
FULL PAPER: postscript / pdf