Reducing Missed by Compiler Optimizations

The optimized software can greatly reduce the miss
rates

Instructions

• Reorder procedures in memory so as to reduce conflict misses, without affecting correctness
• Profiling to look at conflicts(using tools they developed)
• Entry point of basic block at the beginning of a block
• Branch straightening

Data

• Merging Arrays: improve spatial locality by single array of compound elements vs. 2 arrays
• Loop Interchange: change nesting of loops to access data in order stored in memory
• Loop Fusion: Combine 2 independent loops that have same looping and some variables overlap
• Blocking: Improve temporal locality by accessing “blocks” of data repeatedly vs. going down whole columns or rows

Merging Arrays Example

// Before: 2 sequential arrays //
int val[SIZE];
int key[SIZE];

//After: 1 array of stuctures //
struct merge {
	int val;
	int key;
};

struct merge merged_array[SIZE];

Reducing conflicts between val & key (they might conflict for a single block in the cache); improve spatial locality when they are accessed in a interleaved fashion