Full-System Critical Path Analysis

Many interesting workloads today are limited not by CPU pro-cessing power but by the interactions between the CPU, mem-ory system, I/O devices, and the complex software that ties all the components together. Optimizing these workloads requires identifying performance bottlenecks across concurrent hardware components and across multiple layers of software. Common software profiling techniques cannot account for hardware bot-tlenecks or situations where software overheads are hidden due to overlap with hardware operations. Critical-path analysis is a powerful approach for identifying bottlenecks in highly concur-rent systems, but typically requires detailed domain knowledge to construct the required event dependence graphs. As a result, to date it has been applied only to isolated system layers (e.g., processor microarchitectures or message-passing applications). In this paper we present a novel technique for applying critical-path analysis to complex systems composed of numerous interacting state machines. We avoid tedious up-front modeling by using control-flow tracing to expose implicit software state machines automatically, and iterative refinement to add neces-sary manual annotations with minimal effort. By applying our technique within a full-system simulator, we achieve an inte-grated trace of hardware and software events with minimal per-turbation. As a result, we can perform this analysis across the user/kernel and hardware/software boundaries and even across multiple systems. We apply this technique to analyzing network performance, and show that we are able to find performance bot-tlenecks in both hardware and software, including some surpris-ing bottlenecks in the Linux 2.6.13 kernel.