[CSAPP] 6.5 Writing Cache-Friendly Code(캐시 친화적 코드 작성)

6.5 Writing Cache-Friendly Code(캐시 친화적 코드 작성)

1. 공통의 case에 대해 빠르게 해야 한다. ⇒ 프로그램에는 core function이 있을 테고, 이 함수에서 시간을 대부분 사용하게 된다.
2. 각 inner loop 안에서 cache miss 횟수를 최소화 해야 한다. ⇒ load와 store의 총 횟수를 줄일 수 있음

stride-k pattern과 cache hit

위의 코드가 cache friendly 한지를 살펴보자.

• 지역변수 i와 sum : 합리적인 컴파일러라면은 register file에 저장하게 할 것이다.
  • 다시 한번 집고 넘어가자면, register file은 memory 계층도에서 가장 높은 레벨에 있는 memory이다.
• stride-k pattern : 순회할 때 한번에 건너 뛰는 정도가 k index라고 생각하면 좋을 것 같다.
  • stride-1 pattern : 위 코드와 같이 순회하는 것을 말한다. 이 pattern으로 순회할 때의 cache hit과 cache miss를 한번 봐보자.

• 그럼 stride-k pattern으로 순회할 때를 확인해보자.
  • 우선 stride k pattern으로 순회할 시에, Block size가 B bytes인 Cache에서 하나의 루프 당 cache miss가 발생하는 평균 횟수는 다음과 같다.

• 이유는 다음과 같다.
  • 일단 적어도 한번의 cache miss가 있을 것이여서 min을 통해 최소값을 1로 보장한것
  • 그리고 word가 k개 있을 때 block size B를 넘긴다면 또한번 cache miss가 발생할 것이다.
  • 따라서 위와 같은 식이 나온다.
• 이러한 식에 의해 k가 1인 stride-1 pattern에서 이 평균 miss값이 최소가 되는 것이다.

• 요약하자면 다음과 같다.
  • 반복적인 참조가 되는 변수를 지역변수로 선언하는 것은 매우 좋다. ⇒ register file에 저장하게 될 것
  • stride-1 reference pattern은 매우 좋다. ⇒ cache block에 저장할 때, 어떠한 레벨에 있는 memory든간에 전부 연속적인 block을 저장하기 때문에 spatial locality가 좋기 때문이다.

2차원에서의 stride-k reference pattern

• 위에서의 stride-1 pattern과 동일하다. 따라서 cache miss와 cache hit을 나타내면 다음과 같다.

• 여기서의 miss-rate는 1/4임을 알 수 있다.

• stride-N pattern과 동일하다(TODO: 확인 필요). 따라서 cache miss와 cache hit을 나타내면 다음과 같다.

• 이는 array size가 cache size보다 클 경우를 보여준 것이다. 만약, 드문 경우이긴 하지만 array size가 cache size보다 작다면, stride-1 pattern과 같이 cache miss는 1/4이 될 것이다.
• 현재의 miss-rate는 1임을 알 수 있다.

이러한 이유로 프로그래머는 프로그램을 짤 때 locality를 신경써서 짜야 한다.