ABSTRACTCarnegie Mellon, School of Computer ScienceAffinity scheduling in staged server architectures Stavros Harizopoulos, Anastassia Ailamaki Carnegie Mellon University 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 extremely intuitive, it is oblivious to the state of the execution and ignores each software component’s affinity to the processor caches. As a result, resumed threads of execution experience high delays in order to restore context, for example to populate the caches with their evicted working sets, due to additional conflict and compulsory cache misses. Alternatively, the staged server is a programming paradigm that divides the computation that a server performs in response to a request into stages and performs stage (rather than individual request) scheduling, thus allowing for locality-aware algorithms. This paper examines the staged server paradigm in the context of database systems, and studies various locality-aware scheduling policies through analysis and simulation. We developed a framework that models incoming queries served by a series of modules in a database server, and applied six different scheduling policies, varying the system and module parameters. Our results show that the proposed policies (a) achieve up to a 7-fold response time improvement in most configurations when compared to processor-sharing, and (b) better exploit data and instruction locality for a wide range of workload parameter values. FULL PAPER: pdf |