메모리 지역성(Locality of Reference)은 프로그램이 실행되는 동안 데이터나 명령어에 접근할 때, 특정 시간 동안 특정 영역의 메모리에 집중적으로 접근하는 경향을 의미합니다. 이러한 지역성은 CPU 캐시의 효율적인 사용을 가능하게 하며, 프로그램의 성능을 향상시키는 중요한 요소입니다.
메모리 지역성은 크게 다음 두 가지로 분류됩니다:
시간 지역성 (Temporal Locality): 한 번 접근한 메모리 위치에 대해 가까운 미래에 다시 접근할 확률이 높은 것을 의미합니다. 예를 들어, 루프에서 반복적으로 사용되는 변수나 배열은 시간 지역성이 높습니다.
공간 지역성 (Spatial Locality): 한 번 접근한 메모리 위치의 근처에 있는 메모리 위치에 가까운 미래에 접근할 확률이 높은 것을 의미합니다. 예를 들어, 배열을 순차적으로 읽는 경우나, 구조체의 필드를 참조하는 경우에 공간 지역성이 높습니다.
왜 중요한가?
메모리 지역성이 높을수록 CPU 캐시의 히트율이 높아져서 프로그램의 실행 속도가 빨라집니다. 현대의 컴퓨터 아키텍처에서는 메모리 계층이 여러 단계로 이루어져 있고, CPU 캐시와 메인 메모리 사이의 속도 차이는 상당히 큽니다. 따라서 메모리 지역성을 고려한 프로그래밍은 성능 향상에 큰 영향을 미칩니다.
최적화 방법
루프 통합, 루프 분할 등의 루프 최적화를 통해 시간 지역성을 높일 수 있습니다.
데이터 구조를 잘 설계하여 공간 지역성을 높일 수 있습니다. 예를 들어, 연결 리스트보다는 배열을 사용하는 것이 좋을 수 있습니다.
프리패치, 캐시 최적화 등의 하드웨어 특성을 고려한 최적화도 가능합니다.
메모리 지역성은 성능 최적화에서 중요한 개념이므로, 알고리즘 설계나 시스템 구현 시에 반드시 고려해야 합니다.
루프 통합 (Loop Fusion)
루프 통합은 두 개 이상의 루프가 동일한 범위를 가지고 있고, 독립적으로 동작할 때 하나의 루프로 합치는 기법입니다. 이렇게 하면 루프의 초기화와 종료 조건 계산, 그리고 인덱스 관리 등의 오버헤드를 줄일 수 있습니다.
루프 분할 (Loop Fission or Loop Splitting)
루프 분할은 하나의 루프 내에서 여러 작업을 수행하는 경우, 이를 여러 개의 루프로 나누는 기법입니다. 이렇게 하면 CPU 캐시 활용성을 높이고, 병렬 처리를 쉽게 할 수 있습니다.
루프 통합과 루프 분할은 상황에 따라 적절히 사용해야 합니다. 예를 들어, 루프 통합은 메모리 접근 패턴이 복잡해지는 경우에는 오히려 성능을 저하시킬 수 있습니다. 반면, 루프 분할은 병렬 처리를 위해 필요한 경우가 많습니다. 따라서 어떤 최적화 기법이 적합한지는 프로그램의 특성과 실행 환경에 따라 다를 수 있습니다.
