Criticality Stacks: Identifying Critical Threads in Parallel Programs Using Synchronization Behavior
Analyzing multi-threaded programs is quite challenging, but is necessary to obtain good multicore performance while saving energy. Due to synchronization, certain threads make others wait, because they hold a lock or have yet to reach a barrier. The authors call these critical threads, i.e., threads whose performance is determinative of program performance as a whole. Identifying these threads can reveal numerous optimization opportunities, for the software developer and for hardware. In this paper, they propose a new metric for assessing thread criticality, which combines both how much time a thread is performing useful work and how many co-running threads are waiting.