Cache Sensitive Instruction Scheduling

Abstract

The processor speeds continue to improve at a faster rate than the memory access times. The issue of data locality is still unsolved, and continues to be a problem given the widening gap between processor speeds and memory access times. Compiler research has chosen to address this problem in many directions including source code transformations of loops, static data reorganization, dynamic data reorganization, and optimized instruction scheduling. This paper presents Cache Sensitive Scheduling(CSS). CSS is an instruction scheduling algorithm that relies on a rank function to choose operations in the proper order. The CSS rank function is built on the latency of the operation, the impact of this operation on other operations in the program, and the latency of operations that this operation is dependent on in some way. Our premise is based on the hypothesis that careful scheduling of load instructions can increase ILP and decrease execution times by overlaying the latency of load instructions with other useful instructions. This is particular useful on EPIC and VLIW types of machines, where increased ILP is always a benefit. Our rank function is designed to find these opportunities and exploit them. We will show that these techniques can be used to improve the performance of programs with a range of memory access patterns spanning the regular to irregular.