캐시-친화 알고리즘 Cache-Friendly Algorithms

캐시-친화 알고리즘 Cache-Friendly Algorithms

Cache-Friendly Algorithms 는 CPU 캐시 메모리의 작동 방식을 최대한 활용하여 성능을 최적화한 알고리즘입니다.

현대 CPU의 성능은 캐시를 얼마나 효과적으로 활용하느냐에 크게 의존하므로, 캐시 친화적인 알고리즘은 연산 속도와 메모리 접근 속도를 크게 향상시킬 수 있습니다.

---

1. 캐시 메모리와 지역성의 이해

캐시 메모리는 CPU와 RAM 사이의 고속 메모리로, 자주 사용되는 데이터를 저장해 CPU가 빠르게 접근할 수 있도록 합니다.

캐시를 잘 활용하려면 다음 두 가지 "지역성(Locality)" 원칙을 이해해야 합니다:

• 시간적 지역성 (Temporal Locality):
  최근에 접근한 데이터는 가까운 미래에 다시 접근될 가능성이 높다.

  예: 루프(loop)에서 반복적으로 사용하는 변수.

• 공간적 지역성 (Spatial Locality):
  최근에 접근한 데이터의 주변 데이터도 곧 접근될 가능성이 높다.

  예: 배열(array)의 연속된 요소 접근.

캐시 친화적인 알고리즘은 이 두 원칙을 활용하여 데이터를 효율적으로 배치하고 접근합니다.

---

2. Cache-Friendly Algorithm 설계 원칙

1. 연속적인 메모리 접근
   데이터를 배열과 같이 연속적인 메모리에 저장하여 캐시 미스(miss)를 줄입니다.

   • 배열(Array): 연속적이므로 캐시 효율이 높음.
   • 링크드 리스트(Linked List): 노드가 분산되어 있어 캐시 비효율적.

2. 블록 처리 (Blocking or Tiling)
   큰 데이터를 작은 블록으로 나누어 캐시 크기 내에서 작업을 처리합니다.

   예: 행렬 곱셈에서, 행렬을 블록 단위로 처리해 캐시 재사용성을 극대화.

3. 데이터 재사용 극대화
   메모리에 접근할 때, 동일한 데이터에 여러 번 접근하도록 설계합니다.

   예: 한 번 로드한 데이터가 여러 계산에서 사용되도록 알고리즘 설계.

4. 데이터 구조 최적화
   데이터 구조를 캐시 친화적으로 설계합니다.

   예: 트리 구조를 배열로 표현하거나, BFS 탐색에서 큐 대신 배열 사용.

---

3. Cache-Friendly Algorithm 사례

(1) 행렬 곱셈 (Matrix Multiplication)

기본 행렬 곱셈 알고리즘은 캐시 효율이 낮습니다.

cpp

// 비효율적 행렬 곱셈
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

개선된 캐시 친화적 알고리즘: Blocking
행렬을 작은 블록으로 나눠 연속적으로 작업합니다.

cpp

int blockSize = 16;
for (int ii = 0; ii < N; ii += blockSize) {
    for (int jj = 0; jj < N; jj += blockSize) {
        for (int kk = 0; kk < N; kk += blockSize) {
            for (int i = ii; i < ii + blockSize; i++) {
                for (int j = jj; j < jj + blockSize; j++) {
                    for (int k = kk; k < kk + blockSize; k++) {
                        C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
    }
}

• 효과: 블록 내 데이터가 캐시에 적재된 상태로 반복 사용되므로 캐시 미스가 감소합니다.

---

(2) 병렬 퀵소트 (Parallel QuickSort)

기본 퀵소트는 재귀 호출이 깊어질수록 비캐시 친화적입니다.

• 개선: 작은 서브배열에서는 재귀 대신 반복문으로 전환하거나, 배열 대신 연속된 메모리 블록을 사용합니다.

---

(3) 트리 순회 (Tree Traversal)

기본 트리 순회는 비캐시 친화적입니다. 이유는 트리가 포인터 기반으로 설계되어 메모리가 비연속적이기 때문입니다.

• 개선: Cache-Oblivious Layout
  트리를 메모리 레이아웃 상에서 순차적 접근이 가능하도록 재구성합니다.

---

4. Cache-Friendly 알고리즘의 장단점

장점:

• 성능 향상: 캐시 미스를 줄여 연산 속도가 크게 증가.
• 효율적인 메모리 사용: 캐시 크기와 대역폭을 최대로 활용.
• 전력 소비 감소: 메모리 접근이 줄어들어 전력 효율이 높아짐.

단점:

• 복잡성 증가: 캐시 친화적으로 설계하는 데 추가적인 노력이 필요.
• 하드웨어 의존성: 캐시 크기, 계층 구조 등 하드웨어 특성에 따라 성능이 다를 수 있음.

---

5. Cache-Friendly 알고리즘 설계 시 고려사항

1. 캐시 크기와 계층 구조
   알고리즘 설계 시, L1/L2/L3 캐시 크기 및 라인 크기를 고려해야 합니다.

2. 데이터 배치 최적화
   데이터 구조의 메모리 레이아웃을 재구성하여 캐시 효율을 높입니다.

3. 워크로드 분석
   데이터 접근 패턴을 분석해 캐시 친화적인 방식으로 최적화합니다.

---

Cache-Friendly Algorithms는 하드웨어와 알고리즘 설계를 밀접히 연결하여, CPU 캐시를 최대한 활용하는 효율적인 방식입니다.

특히 대규모 데이터 처리, 고성능 컴퓨팅, 게임 개발 등에서 핵심적인 성능 최적화 기법으로 사용됩니다.

view raw Cache-Friendly Algorithms.ko.md hosted with ❤ by GitHub

---

• https://j2doll.tistory.com/979/
  • 캐시 히트와 캐시 미스: 캐시 성능 이해하기
• https://j2doll.tistory.com/975
  • 캐시-친화 알고리즘 Cache-Friendly Algorithm

view raw cache.link.ko.md hosted with ❤ by GitHub