SHPC 11 - Cache Coherence and Tiling

Cache Coherence Problem

• Single memory location에 대해 가장 최신의 값을 읽어야 하는 문제
• 여러 프로세서가 private cache를 가지고 있기 때문에 발생 가능
  • 쓰기를 해도 write-back과 같은 policy를 사용하면 다른 프로세서는 stale value를 읽게 된다.
  • Shared cache에서는 발생하지 않음

Solutions to the Cache Coherence Problem

• Software based vs Hardware based
  • Software based
    • 하드웨어 방식과 혼합되어 사용되기도 함
    • 병렬성과 앨리어싱(다른 이름으로 동일한 메모리에 접근하는 것)을 포함해 메모리 접근에 대한 정보를 모두 알고 있어야 한다
  • Hardware based
    • 더 일반적임
    • Snoopy, directory-based protocol 등이 존재
      • e.g. MSI, MESI, MOESI …
      • M: Modified, S: Shared, I: Invalid, E: Exclusive, O: Owner …
    • Coherence miss라는 개념이 등장함
      • Invalidation-based 솔루션의 경우, 다른 프로세서에서 invalidation을 해서 미스가 발생할 수 있음

Snooping

• 모든 프로세서가 다른 프로세서의 메모리 접근을 감시(snoop)하는 방식
  • Memory bus에 어떤 address가 주어지는지를 바탕으로 감시
  • 누군가 읽기 요청을 했는데, 자신이 해당 address의 dirty copy를 캐시 블록에 가지고 있으면 메모리 접근을 abort 시키고 read requestor에게 직접 캐시 블록을 제공함

Dirty copy를 만들기 전에 읽어서 저장해 둔 값이 있을 수 있는데 이 경우 어떻게 invalidate하지?

값을 수정할 때 다른 캐시한테 알리는 여러 버전들이 존재한다. 예를 들어 invalidate based snooping의 경우, 한 프로세서가 특정 데이터를 수정하고자 할 때 버스를 통해 해당 데이터를 수정할 것임을 다른 프로세서에게 알린다. 다른 프로세서들은 그 데이터를 invalidate하는 방식으로 이를 반영한다.

Coherence and Write through Caches

• 쓰기를 할 때 전역 버스 쓰기가 이루어지니 상대적으로 간편함
  • 해당 정보를 보고 다른 캐시를 invalidate하거나 update해야 함
• 모든 메모리가 up to date value를 가지고 있음

False Sharing

• Invalidation based cache coherence 프로토콜이 퍼포먼스가 떨어지는 원인이 됨
  • 불필요한 invalidation이 필요
• Write back, write allocate 캐시를 생각해 보자
  • 아래와 같이, 실제로는 서로 다른 영역을 사용하고 있는데 캐시 라인이 겹치는 바람에 불필요하게 invalidate됨
  • 
  • 
• Invalidation based protocol에서 발생하는 문제
  • 메모리 레이아웃을 수정하면 해결된다
  • 데이터 배치를 조정하는 것
• Update based protocol에서는 값 전달만 하므로 일어나지 않는다

Tiling

Strip mining

• Operation의 granularity를 조정하는 것
  • Loop를 여러개로 나누는 등
  • 주로 1차원 데이터에 대해 granularity를 조정하면 사용하는 용어이다
• Vectorization에 주로 사용된다
  • Vector register는 길이가 한정적이므로 딱 맞게 수정하는 것

Tiling for Matrix multiply

Naïve implementation

• 캐시가 최소 하나의 row나 column을 담을 수 있다고 가정하자. m이 캐시라인의 원소 수라고 할 때, 위와 같은 구현에서 캐시 미스의 수는?
  • $c[i][j]$ 계산에는 a에서 $\frac{N}{m}$ 회, b에서 $N$ 회 미스가 발생
  • i는 N회 → a에서 $\frac{N^2}{m}$ 회 미스 (a는 적어도 j Loop에서는 재사용됨)
  • i, j는 각각 N회 → b에서 $N^3$회 미스
  • 이게 피피티 계산인데 약간 이상하다
    • 1. 최소 하나의 row or column을 담을 수 있는 캐시인데, 만약 딱 하나의 row만 담을 수 있다면 a의 row는 j loop에서 재사용되지 못할 것임 (b나 c를 담으면서 쫒겨날 것이기 때문) 그런데 계산은 a의 row가 재사용된다고 가정함
    • 2. 설령 하나가 넘는 row or column을 담을 수 있는 캐시라고 해도 c에서 나오는 미스를 계산하지 않았음. 답은 $2\frac{N^2}{m}+N^3$ 이어야 함
• +) 만약 원소 하나가 캐시블록 사이즈이고, 캐시 하나가 row 전체를 담지 못한다면 캐시 미스의 수는?
  • a, b, c 각각 $N^3$ 미스, 총 $3N^3$
  • c를 inner loop 밖에서 접근한다면 $2N^3+N^2$
• 각 루프에 대해 strip mining을 적용한다면?

Tiling

• 3개의 B X B는 캐시가 다 담을 수 있어야 한다

for (kk=0; kk<N; kk += B)
	for (i=0; i<N; i++)
		for (j=0; j<N; j++)
			for (k=kk; k< MIN(kk+B, N); k++)
				c[i][j] += a[i][k] * b[k][j]

for (jj=0; jj<N; jj += B)
	for (kk=0; kk<N; kk += B)
		for (i=0; i<N; i++)
			for (j=jj; j<MIN(jj+B, N); j++)
				for (k=kk; k< MIN(kk+B, N); k++)
					c[i][j] += a[i][k] * b[k][j]

for (ii=0; ii<N; ii += B)
	for (jj=0; jj<N; jj += B)
		for (kk=0; kk<N; kk += B)
			for (i=ii; i<MIN(ii+B, N); i++)
				for (j=jj; j<MIN(jj+B, N); j++)
					for (k=kk; k< MIN(kk+B, N); k++)
						c[i][j] += a[i][k] * b[k][j]

• 각 서브블록이 스칼라처럼 계산되는 것이라 볼 수 있다

Evaluation

• 캐시가 세개의 BXB 블록을 담을 수 있다고 가정하면
  • a, b 각각에 대해 하나의 블록을 로드하는 데에 필요한 미스 $2\frac{B^2}{m}$
  • 총 $(\frac{N}{B}{)}^3$ 회 로드하므로 $\frac{2N^3}{mB}$
  • 마찬가지로 c는 계산하지 않음
• 아까보다 $N^3$에 곱하는 수가 작아져서 좋음