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

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

---

1. Merging Arrays

// 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

Colum order:

store first colum, then second colum, then third….

Example:
– 6x6 array A
– Each element 1 word
– Block size: 4 word
– For i=1 to 6; X+= a[1,i]; how many blocks are loaded into cache

For final
you need to know how many misses in this pic
and prof will give the code

Row order:

store first row, then second row, then third….

Example:
– 6x6 array A
– Each element 1 word
– Block size: 4 word
– For i=1 to 6; X+= a[1,i]; how many blocks are loaded into cach

2. Loop Interchange Example

Assume the array storage is in row order

for (k = 0; k < 100; k = k+1)
	for (j = 0; j < 100; j = j+1)
		for (i = 0; i < 5000; i = i+1)
			x[i][j] = 2 * x[i][j];

/* After */
for (k = 0; k < 100; k = k+1)
	for (i = 0; i < 5000; i = i+1)
		for (j = 0; j < 100; j = j+1)
			x[i][j] = 2 * x[i][j];

• Sequential accesses instead of striding through memory every 100 words; improved spatial locality

3. Loop Fusion Example

/* Before */
for (i = 0; i < N; i = i+1)
	for (j = 0; j < N; j = j+1)
		a[i][j] = 1/b[i][j] * c[i][j];
        
for (i = 0; i < N; i = i+1)
	for (j = 0; j < N; j = j+1)
		d[i][j] = a[i][j] + c[i][j];

• Many programs have separate loops that operate on the same data
• Combining these loops allows a program to take advantage of temporal locality by grouping operations on the same (cached) data together.

 /* After */
for (i = 0; i < N; i = i+1)
	for (j = 0; j < N; j = j+1)
		{ a[i][j] = 1/b[i][j] * c[i][j];
		  d[i][j] = a[i][j] + c[i][j];}

• 2 misses per access to a & c vs. one miss per access; improve temporal locality

4. Blocking

행렬 곱셈처럼 큰 데이터를 쓰는 작업에서, 행이나 열을 끝까지 쭉 훑지 않고 캐시에 쏙 들어가는 작은 정사각형 조각(블록) 을 하나 정해요. 그 조각을 여러 번 다 쓴 다음에 다음 조각으로 넘어가요.

비유: 시험공부할 때 책 10권을 동시에 펴서 한 줄씩 왔다 갔다 하지 않고, 한 챕터를 책상에 펴 놓고 끝낸 뒤 다음 챕터로 가는 것.

---

Prefetching

Idea: fetch data into the cache before processors request them

• Can address cold misses
• Can be done by the programmer, compiler, or hardware

필요해지기 전에 미리 캐시로 가져오는 것이에요. 프로그래머, 컴파일러, 하드웨어 누구든 할 수 있어요. 처음 쓰는 데이터라서 어차피 나는 미스(cold miss)도 막을 수 있어요.

Characteristics of ideal prefetching

You only prefetch data that are truly needed
- Avoid bandwidth waste

You issue prefetch requests early enough
- To hide the memory latency

You don’t issue prefetch requests too early
- To avoid cache pollution

Prefetching relies on having extra memory bandwidth that can be used without penalty

Prefetching Terminology

• Prefetch Hit: Prefetched line that was hit in the cache before being replaced (miss avoided)
• Prefetch Miss: Prefetched line that was replaced before being accessed
• Prefetch Rate: Prefetches per instruction (or 1000inst.)
  Accuracy: Percentage of prefetch hits to all prefetches
• Coverage: Percentage of misses avoided due to prefetching
  100 x (Prefetch Hits / (Prefetch Hits + Cache
  Misses))

Classification of Prefetched Lines

Useful Prefetch

• Prefetch hit before being replaced
• Results in avoiding a cache miss

Useless Prefetch

• Prefetch is replaced before being accessed (prefetch miss)
• Downside: Increases demand for cache bandwidth, power

Harmful Prefetch

• Prefetch is replaced before being accessed AND
• Prefetch replaces a line that is requested later (cache pollution)
• Results in an additional cache miss
• power