[컴퓨터 구조] 11. 캐시 성능 측정 및 향상

다단계 캐싱(multilevel caching)

여러 캐시를 계층적 구조로 사용하여 실패 손실을 줄이는 기술. 1 차 캐시에 데이터가 없다면 2차 캐시를 조회하게 되는데 2차 캐시에 데이터가 있다면 주 메모리 접근 시간보다 훨씬 작다. 보통 1차 캐시는 2차 캐시보다 작다. 1차 캐시는 CPU와 최대한 가깝도록 설계하여 적중 시간을 최소화하고 2차 캐시는 더 크게 설계하여 큰 블록에 대한 실패율을 감소시킨다.

 

적중된 캐시에 의한 정상적인 CPU 실행 시간은 다음과 같다.

 

CPU 시간 = (CPU 클럭 사이클 + 메모리 지연 클럭 사이클) x 클럭 사이클 시간

 

메모리 지연 클럭 사이클은 읽기와 쓰기 행동에 의해 걸리는 시간의 합이다.

메모리 지연 클럭 사이클 = 읽기 지연 사이클 + 쓰기 지연 사이클

 

읽기와 쓰기 지연 사이클이 비슷하다고 할 때, 메모리 지연 클럭 사이클은 다음과 같다.

 

 

혹은 명령어 용어로 사용하면 다음과 같다.

ex)캐시 실패율이 2%이고 데이터 캐시율이 4%이라고 하자. 메모리 지연이 없을 떄 CPI는 2이고 매 실패마다 실패 손실이 100 사이클 이라면 실패가 발생되지 않는 완벽한 캐시에서는 얼마나 빨라지는가? 읽기와 쓰기 빈도는 36%이다.

 

명령어 실패 사이클 = I * 0.02 * 100 = 2 * I (I는 명령어 갯수)

데이터 실패 사이클 = I * 0.36 * 0.04 * 100 = 1.44 * I

 

두 실패 사이클의 합은 3.44 I 이다. 실패가 없는 CPU는 2 CPI를 갖지만 실패가 발생하는 CPU의 성능은 3.44 + 2 CPI로 5.44 CPI를 갖는다.

 

성능 비는 다음과 같다. 5.44 CPI / 2 CPI = 2.72 배이다.

 

캐시의 성능을 평가하는 방법으로 평균 메모리 접근 시간 AMAT (average memory access time)이 사용될 수 있다.

 

AMAT = 캐시 적중 시간 + 실패율 X 실패 손실

 

만약, 캐시가 L1/L2로 2 계층 구조로 이루어져 있다면 메모리 접근 시간은 다음과 같다.

 

L1/L2 평균 메모리 접근 시간 = $L_1$캐시 적중 시간 + $L_1$실패율 $\times$ ( $L_2$캐시 적중시간 + $L_2$실패율 $\times$  $L_2$실패 손실)

 

유연한 메모리 블록 배치

 

데이터 블록 주소의 하위 비트열과 캐시 메모리 블록을 1 대 1로 맵핑하는 직접 사상 방식과 다르게 데이터 블록 대 캐시 블록을 다 대 일 구조로 설계할 수 있다. 이러한 구조를 집합 연관(set associative) 방식이라고 한다.

 

집합 연관 캐시는 블록당 들어갈 수 있는 배치 수가 고정되어 있으며 각 블록당 n개의 배치 가능한 위치를 갖는 집합 연관 캐시를 n-way 집합 연관 캐시라고 한다. 비슷한 방식으로 데이터 블록 주소에서 집합 번호를 구한뒤 집합 내 아무 공간에 데이터 블록이 배치된다.

직접 사상, 집합 연관 및 완전 연관 방식

완전 연관 방식은 각 셋에 하나의 블록만 들어가게 된다. 집합 연관 방식에서 한 집합내 여러 데이터 블록을 구분하기 위해 하드웨어적으로 모든 엔트리를 검색할 수 있도록 구현해야한다.

 

집합 연관 방식에서는 집합 마다 배치될 수 있는 데이터 블록 수가 증가하기 때문에 비슷한 캐시 인덱스 패턴으로 데이터를 접근할 시 캐시가 있을 확률이 올라가므로 캐시 적중률을 높일 수가 있다.

 

집합 연관 방식으로 인덱스 비트 수가 줄어들면 그만큼 태그 필드의 비트 수가 증가하게 된다. 2-way 집합 연관 방식에서는 인덱스 비트 수가 1 감소하고 태그 비트 수가 1증가하게 된다.

 

4-way 집합 연관 캐시 구현

4-way 집합 연관 캐시는 반드시 하드웨어적으로 4개의 엔트리의 태그 필드를 검사해야한다. 이 때 일치하는 엔트리의 데이터를 선택할 수 있도록 4 대 1 멀티 플렉서를 이용해야 한다.

 

교체 정책 Replacement Policy

집합 연관에서 배치할 자리가 더 이상 없는 경우 캐시를 교체하기 위해서는 가장 마지막에 사용된 캐시를 교체하게 된다. 이러한 방식을 Least Recently Used(LRU) 방법이라 한다.

 

블로킹을 이용한 소프트웨어 최적화

배열을 다룰 때 접근 순서를 순차적으로 이루어질 수 있다면 시간적 지역성을 개선된다.

블록화 알고리즘은 배열의 전체 행과 열을 처리하는 대신 부분행렬 또는 블록 단위로 처리한다.

NXN 행렬의 C = A * B 곱셈을 수행하는 어떤 함수 DGEMM 내부 순환문은 다음과 같다.

for (int j = 0; j < n; ++j)
{
  double c_ij = C[i + j * n];
  for (int k = 0; k < n; k++)
  	c_ij += A[i + k * n] * B[k + j * n]; // c_ij += a_ik * b_kj
  C[i + j * n] = c_ij; // c_ij = c_ij
}

n=6, i=1일 때, A,B,C의 접근되는 데이터. 밝은 음영은 접근한지 오래된 배열, 짙은 음영은 새로 접근한 것을 보여준다.

 

• A: A는 한 행을 번복하여 접근하고 있다.
• B: N x N 모든 원소를 한 번씩 접근하고 있다.
• C: 한 행에 해당하는 원소 N개만큼 쓰고 있다.

캐시 용량 부족에 의한 캐시 미스는 행렬 크기 N에 영향을 미칠 수 있다. 만약 N = 32이라면, 세 행렬을 모두 저장하여 최소한의 캐시 미스를 실현할 수 있는 최소 캐시 사이즈는 32 * 32 * 3 * 8 Bytes = 24KiB가 필요하게 된다.

 

만약 N개짜리 행 하나와 NxN짜리 행렬을 하나 보관할 수 있다면, A 접근, B 접근에 대한 데이터를 캐시할 수 있다. 이보다 작을 경우 실패는 B와 C 양쪽에서 발생가능하다. 최악의 경우 N 세제곱 연산에서 A에 대한 접근 N^3, B에 대한 접근 N^3, 그리고 C에 대한 N^2 쓰기가 발생하므로 $2*N^3 + N^2$ 메모리 워드 접근이 발생할 수 있다.

 

블록화 알고리즘은 캐시의 사이즈를 고려하여 행렬 N를 결정한다. 계산된 예에서 32를 사용할 경우 A,B를 둘 다 캐시에 적재할 수 있으며 주 메모리 접근을 감소시킬 수 있다. 그러한 블로킹 인수 N을 BLOCKSIZE라 정의하고 다음과 같이 행렬의 일부분 씩 계산하는 알고리즘을 설계할 수 있다. 

#define BLOCKSIZE 32
void do_block(int n, int si, int sj, int sk, double* A, double* B, double* C)
{
	for (int i = si; i < si + BLOCKSIZE; ++i)
	{
		for (int j = sj; j < sj + BLOCKSIZE; ++j)
		{
			double cij = C[i + j * n];
			for (int k = sk; k < sk + BLOCKSIZE; k++)
			{
				cij += A[i + k * n] * B[k + j * n]; // c_ij += a_ik * b_kj
			}
			C[i + j * n] = cij; // c_ij = c_ij
		}
	}
}

void dgemm(int n, double* A, double* B, double* C)
{
	for (int sj = 0; sj < n; sj += BLOCKSIZE)
	{
		for (int si = 0; si < n; si += BLOCKSIZE)
		{
			for (int sk = 0; sk < n; sk += BLOCKSIZE)
			{
				do_block(n, si, sj, sk, A, B, C);
			}
		}
	}
}

더 작은 사이즈로 접근 할 경우 캐시의 성능을 최대화해서 행렬 데이터의 주메모리 접근을 최소화한다. 이전 $2*N^3 + N^2$ 메모리 워드 접근에서 각 A, B는 행렬 원소를 한번씩만 캐싱하면 되므로 블로킹 인수 BLOCKSIZE만큼 이득을 보게된다. 따라서 $2*N^3/BLOCKSIZE + N^2$의 향상이 기대된다.

 

블로킹은 또한 더 작은 단위의 레지스터으로 데이터 할당을 돕기 때문에 저장/적재가 레지스터 단위로 일어나서 성능 향상이 기대될 것이다.

 

참고 : Computer Organization and Design RISC-V edition