지역성의 원리 (Locality of Reference)
쉽게 풀면
책상 위에서 작업할 때를 떠올려 봅시다. 방금 참고한 책을 잠시 후 또 펼쳐볼 가능성이 높고(시간적 지역성), 그 책 옆에 꽂힌 관련 자료도 이어서 꺼내 볼 가능성이 높습니다(공간적 지역성). 그래서 자주 쓰는 책들을 서랍이 아니라 책상 위 가까운 곳에 미리 꺼내 두면 훨씬 효율적입니다. 컴퓨터 프로그램도 마찬가지 패턴을 보입니다. 반복문 안의 코드는 짧은 시간 안에 계속 재실행되고(시간적 지역성), 배열의 원소들은 메모리 상에서 서로 가까운 주소에 이어서 접근됩니다(공간적 지역성). 이 규칙성이 있기 때문에, 자주 접근하는 데이터를 빠른 저장장치에 미리 옮겨두는 캐시 전략이 실제로 효과를 발휘하는 것입니다.
왜 중요한가
지역성의 원리는 컴퓨터 시스템 설계 전반에서 성능 최적화의 이론적 근거로 쓰이기 때문에 논문에서 자주 다뤄집니다. 캐시 구조, 메모리 계층, 데이터베이스 인덱싱, 딥러닝 가속기의 메모리 접근 최적화 등 서로 다른 연구 주제들이 결국 이 원리를 얼마나 잘 활용하느냐로 성능이 갈립니다. 그래서 새로운 알고리즘이나 시스템을 제안할 때, 지역성을 얼마나 개선했는지가 성능 향상의 핵심 근거로 제시되는 경우가 많습니다.
논문에서는 이렇게 쓰입니다
이 문장은 "데이터를 메모리에 배치하는 방식을 바꿔서, 서로 가까이 쓰이는 데이터를 실제로도 가깝게 배치했더니 캐시에서 원하는 데이터를 찾는 성공률이 올라갔다"는 뜻입니다.
큰 행렬을 작은 덩어리로 나눠 계산하면서, 그 작은 덩어리를 잠깐 동안 계속 재사용하도록 만들어 매번 큰 메모리에서 다시 가져오는 비용을 줄였다는 의미입니다.
그래프 데이터는 배열처럼 순서대로 접근되지 않고 여기저기 흩어진 정점을 오가며 접근되기 때문에, 캐시가 기대하는 규칙적인 패턴이 잘 나타나지 않아 성능 최적화가 어렵다는 뜻입니다.
조금 더 깊게 보면
지역성은 흔히 시간적 지역성(temporal locality)과 공간적 지역성(spatial locality) 두 가지로 나뉘며, 실제 시스템에서는 이를 정량적으로 측정하기 위해 캐시 적중률(cache hit rate), 미스율(miss rate), 작업집합(working set) 크기 같은 지표를 함께 사용합니다. 작업집합은 특정 시간 구간 동안 프로그램이 실제로 자주 접근하는 데이터의 범위를 의미하며, 이 크기가 캐시 용량보다 작을수록 지역성을 활용하기 유리합니다. 최근에는 그래프 처리나 희소 행렬 연산처럼 접근 패턴이 불규칙한 워크로드를 위해, 데이터 재배치(data layout transformation)나 프리페칭(prefetching) 기법으로 지역성을 인위적으로 끌어올리려는 연구도 활발히 이루어지고 있습니다.
주의할 점
지역성의 원리는 캐시가 왜 잘 작동하는지를 설명하는 "이유"이고, 캐시 메모리 계층구조는 그 원리를 활용해 실제로 만들어진 "저장 구조"입니다. 두 개념이 짝을 이루지만 서로 같은 것을 가리키는 말은 아니므로 혼동하지 않도록 주의해야 합니다.