Warp-Aware Trace Scheduling for GPUs

GPU performance depends not only on thread/warp level parallelism (TLP) but also on instruction-level parallelism (ILP). It is not enough to schedule instructions within ba-sic blocks, it is also necessary to exploit opportunities for ILP optimization beyond branch boundaries. Unfortunately, modern GPUs cannot dynamically carry out such optimiza-tions because they lack hardware branch prediction and can-not speculatively execute instructions beyond a branch. We propose to circumvent these limitations by adapting Trace Scheduling, a technique originally developed for mi-crocode optimization. Trace Scheduling divides code into traces (or paths), and optimizes each trace in a context-independent way. Adapting Trace Scheduling to GPU code requires revisiting and revising each step of microcode Trace Scheduling to attend to branch and warp behavior, identi-fying instructions on the critical path, avoiding warp diver-gence, and reducing divergence time. Here, we propose “Warp-Aware Trace Scheduling ” for GPUs. As evaluated on the Rodinia Benchmark Suite using dynamic profiling, our fully-automatic optimization achieves a geometric mean speedup of 1.10 × on a real system by increasing instructions executed per cycle (IPC) by a har-monic mean of 1.12 × and reducing instruction serialization and total instructions executed