시작하며
저번 학기에 컴퓨터 구조를 수강하면서 간과하고 있던 로우 레벨의 지식에도 흥미가 생겼었다. 그 중 CPU와 Memory, Disk의 역할에 대해 알아볼 수 있었고 캐시는 CPU와 Memory 사이에 위치해 메모리 대신 빠르게 CPU에게 데이터를 제공하는 녀석이라고 배웠다.
이전에는 주로 캐시라고 하면 주로 CDN과 같은 네트워크에서 쓰이는 캐시들밖에 몰랐다. 그렇다보니 L1 캐시, L2 캐시 같은 얘기를 들으면 OSI 7계층과 연관 지어 ‘음..? L2 캐시는 스위치에서 쓰는 캐시인가..?’ 라는 상상을 하곤했다.
이번에는 Go를 통해 배열에 여러 차례 접근하는 프로그램을 만들어보고 벤치마킹을 통해 캐시라는 녀석이 어떤 효과를 가져다주는지 직접 확인해보려한다.
캐시란
캐시는 아주 다양한 문맥에서 사용된다. 공통적으로 “사용자가 요청할 것 같은 데이터를 작고 빠른 저장소에 저장해놓음으로써 좀 더 빨리 해당 데이터를 제공한다"는 목적을 갖는다. CDN, DB, REST API, Memory, CPU 등등 다양한 곳에서 쓰일 수 있을 것 같다. 그 중 이번에는 CPU와 메모리 사이의 캐시에 대해 알아보겠다.
CPU와 메모리 사이의 캐시는 메모리의 데이터를 얻기 위해 메모리에 직접 접근하지 않고 캐시라는 빠른 저장소를 이용해 해당 데이터를 얻게끔해준다. 예를 들어 변수 a=10 이라는 데이터가 메모리에 존재한다해도 a의 값을 얻기 위해 메모리에 직접 접근하기 보다는 가까우면서 빠르게 이용 가능한 캐시에서 데이터를 가져올 수도 있다는 것이다. 사실 캐시의 개념적인 측면에서 보면 메모리 또한 디스크 대신 빠르게 값을 전달해주기 위한 경우일 수 있으니 캐시 기능을 한다고 볼 수 있다. 그리고 CPU와 메모리 사이에 정말 캐시라는 이름을 갖는 녀석들은 프로세서 속에 있는 L1 캐시, 프로세서 옆에 있는 L2 캐시, 프로세서들이 공유하는 L3 캐시가 있긴 하지만 이는 시대가 지나면서 얼마든지 변할 수 있는 내용들이기 때문에 어떤 캐시가 어디에 있고 누구랑 누가 공유하는지와 같은 세부 내용은 크게 중요하진 않을 것 같다.
물리적인 크기나 거리는 속도와 반비례할 수 밖에 없다. 거리가 멀면 정보가 전달되는 속도가 느려지고 크기가 크면 여러 Mux나 Gate를 이용한다는 것이기 때문에 느려진다. 그렇기때문에 캐시는 작고 가까워야한다. 데이터를 요청하는 녀석은 CPU이기 때문에 캐시는 CPU 속 혹은 그 근처에 위치한다. 또한 작아야하기때문에 모든 정보를 담을 수 없고, 사용자가 요청할법한 데이터만을 담아야한다. 이 때 어떻게 사용자가 요청할 법한 데이터를 정할까? 이는 공간 지역성과 시간 지역성이라는 중요한 두 가지 성질을 기반으로 한다.
이외에도 태그나 충돌 같은 개념들이 있긴하지만 실제로 벤치마킹해보기도 쉽지 않고 다소 지엽적인 내용이라 간단히만 정리해보면 태그 없이 주소값을 모듈러(나머지)연산해서 cache line index를 결정하고 그것만을 이용해 데이터를 저장하면 한 line 내에 저장할 워드(Word)에 대한 충돌이 발생할 수 있다. cache line이 20개인 캐시는 0번지와 20번지가 같은 line이므로 충돌이 발생해 계속해서 같은 line에 서로의 데이터가 번갈아 저장될 수 있다는 것이다. 하지만 태그를 이용하면 cache line 수는 줄어들더라도 한 line내에 여러 태그의 정보를 저장할 수 있게되어 cache line이 10개인 cache의 한 line에 0번지와 20번지의 데이터가 다른 태그로 저장되어 불필요한 충돌을 방지할 수 있다는 장점이있다. 간단히 설명하기는 힘든 내용이라 좀 더 자세히 알고싶다면 Direct mapped cache나 Fully associative cache 등으로 검색해보기를 권장한다.
Spatial locality
Spatial locality(공간 지역성)이란 지금 요청 받은 데이터와 가까운 곳에 위치한 데이터는 높은 확률로 다시 요청 받게 된다는 성질이다. 예를 들어 100번지의 a=10과 108번지의 b=20이 존재할 때 변수 a를 요청하면 이후 a와 가까운 주소에 저장된 b 또한 높은 확률로 요청된다는 것이다.
package main
import (
"fmt"
)
func main() {
var (
a int = 10
b int = 20
c int = 30
)
fmt.Printf("a: %p\nb: %p\nc: %p\n", &a, &b, &c)
}
/*
Output:
a: 0xc000100010
b: 0xc000100018
c: 0xc000100020
*/
a, b, c의 크기는 8바이트로 주소값 또한 8바이트가 차이난다. (16진법이기에 20과 18의 차이는 8이다.) 즉 대체로 비슷한 시기에 할당된 변수는 근접한 메모리 주소를 갖게 된다. 우리는 비슷한 시기에 할당한 변수 혹은 연속된 배열 요소에 자주 빠른 시일 내에 접근을 하지 맨 위에서 선언한 변수와 저 멀리 맨 밑에서 선언한 변수를 마구잡이로 왔다 갔다 하면서 작업을 하지 않는 편이기 때문에 공간 지역성을 근거로한 캐시가 효력을 갖게 된다. 만약 공간적으로 먼 맨 위의 변수와 맨 아래의 변수를 자주 번갈아가며 접근한다면 그것은 시간지역성을 띄는 경우이다.
Temporal locality
Temporal locality(시간 지역성)이란 최근에 요청했던 데이터는 높은 확률로 다시 요청 받게 된다는 성질이다. 예를 들어 100번지의 a=10과 9999번지의 b=20은 서로 주소적인 거리는 멀지만 둘 다 최근에 호출됐다면 캐시에 적재하겠다는 것이다. 캐시는 주로 직사각형 형태로 생겼으며 가로(행)는 연속된 주소의 데이터를 저장하는 공간 지역성, 세로(열)는 최근에 호출된 데이터를 저장하는 시간 지역성을 담당한다.
두 지역성 비교
12칸의 캐시가 있다고 가정하자. 가로로 4칸 세로로 3칸 존재한다면 공간/시간 지역성의 균형이 잡힌 캐시라고 볼 수 있다.(경우에 따라 다르겠지만)
시간 지역성은 최근 불린 데이터는 다시 불릴 확률이 높다는 것이고 이는 연속된 공간이 아닌 다양한 공간(주소)의 데이터를 캐시에 저장한다는 말이기도 하다. 0번지 부근, 16번지 부근, 24번지 부근의 다양한 공간의 데이터를 저장할 수 있으면서 그 녀석들간의 주변 데이터도 제공하는 공간지역성도 만족한다.
두 가지 지역성에 의해 다양한 캐시들이 데이터를 적재하고 제공한다. 요점은 캐시는 빠르게 동작해야하고 그러기 위해선 크기가 작고 가까워야하며 크기가 작기 때문에 모든 데이터를 담을 수 없으니 알짜 데이터만을 담아야하는데 그 알짜는 지역성을 기반으로 선별된다는 것이다. 크기가 한정적이기 때문에 한 지역성을 키우면 한 지역성은 작아질 수밖에 없다.
공간 지역성에 치우친 캐시 구조
한정된 크기의 캐시 속에서 공간지역성을 극대화시켜버리면 당연히 인접한 공간의 자료만 이용할 수 있고, 최근에 불린 데이터들은 안중에도 없고 인접한 공간의 데이터만을 저장하게 된다. 예를 들어 다음과 같은 시간 지역성이 필요한 경우에 제대로 기능을 할 수 없다.
- 0~11번지 사이의 데이터가 한 번 접근 ⇒ 캐시에 0~11번지 적재
- 이후 12번지의 데이터에 접근 ⇒ 캐시에 데이터가 없기때문에 0~11번지의 데이터 대신 12~23번지의 데이터를 캐시에 적재
- 다시 최근에 접근했던 데이터인 0번지의 데이터에 접근 시도 ⇒ 0번 데이터는 최근에 접근했던 데이터임에도 시간 지역성이 활용되지 못함 ⇒ 캐시에서 데이터를 찾을 수 없음.
시간 지역성에 치우친 캐시 구조
위의 경우 최근에 호출된 다양한 주소의 데이터들을 캐시에 저장해준다. 하지만 캐시의 크기는 한정되어있기 때문에 세로가 길어지면 가로는 짧아진다. 즉 최근 접근을 시도한 다양한 주소의 데이터를 저장할 수 있지만 그 데이터의 인근 데이터에 대한 저장은 많이 할 수 없다는 것이다.
예를 들어 위의 그림과 같은 경우 최근 0, 3, 12, 18, 6, 20번지의 데이터에 접근했고 이후에도 해당 번지에 대한 데이터를 캐시를 통해 이용할 수 있다. 바로 내가 최근에 접근했던 데이터이기때문이다. 하지만 만약 18번지의 데이터에 접근한 경우 높은 확률로 공간지역성에 의거 19, 20, 21, … 번지의 데이터에 접근하겠지만, 이 예시는 시간지역성에 치우쳐져 19번지의 데이터만을 캐시에서 제공받을 수 있다.
프로그램을 통한 벤치마킹
저번에 Mutex, Semaphore를 직접 벤치마킹해보면서 Go의 내장 벤치마크 기능을 이용하면 좀 더 편리하게 결과를 보여줄 수 있을 것 같았기에 이번에 Go의 내장 벤치마크 기능을 이용해봤다.
1000행 1000열의 2차원 int형 배열의 어떠한 요소에 접근해서 +1 하는 작업을 1000회 수행하는 것을 하나의 싸이클로 하는 벤치마크를 작성했다. 2차원 배열은 가로로는 연속적인 주소값을 갖기에 공간 지역성을 활용할 수 있지만 세로로는 N * (int형 자료형의 크기)씩 차이 나는 주소값을 갖기 때문에 공간 지역성을 활용하기 힘들고, 최근 접근했던 주소라면 시간 지역성은 활용할 수 있다.
공간 지역성 (가로로 연속적인 데이터)
- 공간 지역성을 사용하는 경우 가로로 연속된 요소에 접근. 즉 연속된 주소를 갖는 1000개의 요소에 접근
- 공간 지역성을 사용하지 않는 경우에는 세로로 요소에 접근. 즉 1000 * int 자료형의 크기만큼 차이나는 연속되지 않은 주소의 1000개의 요소에 접근
시간 지역성 (연속적 주소와 상관없이 최근에 불린 데이터)
- 시간 지역성을 사용하는 경우 주소값이 근접하진 않지만 4개 혹은 16개의 데이터에만 계속해서 접근
- 시간 지역성을 사용하지 않은 경우에는 계속해서 처음 접근하는 데이터에만 접근
package main
import (
"testing"
)
var (
Size int = 1000
)
func generateArray() [][]int{
arr := make([][]int, Size)
for i := 0; i < Size; i++{
arr[i] = make([]int, Size)
for j := 0; j < Size; j++{
arr[i][j] = 0
}
}
return arr
}
func BenchmarkSpatialLocality(b *testing.B){
b.Run("공간지역성 사용", func(b *testing.B) {
arr := generateArray()
b.ResetTimer()
for n := 0; n < b.N; n++{
for i := 0; i < Size; i++{
arr[0][i] += 1
}
}
})
b.Run("공간지역성 X", func(b *testing.B) {
arr := generateArray()
b.ResetTimer()
for n := 0; n < b.N; n++{
for i := 0; i < Size; i++{
arr[i][0] += 1
}
}
})
}
func BenchmarkTemporalLocality(b *testing.B){
b.Run("시간 지역성 적극 사용. 최근 접근한 데이터 4개.", func(b *testing.B) {
arr := generateArray()
b.ResetTimer()
for n := 0; n < b.N; n++{
for i := 0; i < Size; i++{
arr[i%4][0] += 1
}
}
})
b.Run("시간 지역성 조금 사용. 최근 접근한 데이터 16개.", func(b *testing.B) {
arr := generateArray()
b.ResetTimer()
for n := 0; n < b.N; n++{
for i := 0; i < Size; i++{
arr[i%16][0] += 1
}
}
})
// 사실 완벽하게 새로운 데이터는 아님. 벤치마킹하는 동안 계속해서 반복되기 때문에
b.Run("시간 지역성 X. 새로운 데이터에만 접근.", func(b *testing.B) {
arr := generateArray()
b.ResetTimer()
for n := 0; n < b.N; n++{
for i := 0; i < Size; i++{
arr[i][0] += 1
}
}
})
}
goos: linux
goarch: amd64
pkg: playground/unix-socket/cache
BenchmarkSpatialLocality/공간지역성_사용 50000 894 ns/op
BenchmarkSpatialLocality/공간지역성_X 50000 6561 ns/op
BenchmarkTemporalLocality/시간_지역성_적극_사용._최근_접근한_데이터_4개. 50000 1918 ns/op
BenchmarkTemporalLocality/시간_지역성_조금_사용._최근_접근한_데이터_16개. 50000 4153 ns/op
BenchmarkTemporalLocality/시간_지역성_X._새로운_데이터에만_접근. 50000 6564 ns/op
결과를 확인해보니 간단한 배열 내의 요소들에 대한 연산인데도 꽤나 차이가 컸다.
마치며
저번 학기에 컴퓨터 구조를 수강하면서 CPU-Memory 캐시의 효과를 직접 배열에 대한 프로그램을 통해 보여주는 예시를 보고 신기했던 기억이 있어서 이렇게 벤치마킹 프로그램을 작성해봤다. 다른 CS 주요 지식들에 비해 어려울 것은 없는 편이고 우리가 쉽게 접해오던 내용이라 더 이해하기 쉽지 않았을까 싶다.
참고
- 캐시란 - https://ko.wikipedia.org/wiki/캐시
- 캐시가 동작하는 아주 구체적인 원리 - https://parksb.github.io/article/29.html
- cache mapping - https://m.blog.naver.com/jkssleeky/220478400046