지역성

지역성이란

지역성은 프로그램이 메모리를 골고루 쓰지 않고, 특정 위치를 집중해서 참조하는 성질이다.

방금 쓴 곳과 그 근처를 계속 다시 쓰는 편이다. 이 성질이 캐시와 가상 메모리의 성능 근거다.

두 가지 지역성

지역성은 시간 지역성과 공간 지역성으로 나뉜다.

시간 지역성은 한 번 참조한 데이터를 짧은 시간 안에 다시 참조하는 성질이다. 반복문의 변수 i가 대표 예다.

공간 지역성은 참조한 주소 근처의 데이터를 곧 참조하는 성질이다. 배열을 순서대로 훑는 코드가 전형적인 예다.

순차 지역성은 공간 지역성의 특수한 경우로, 데이터가 선형으로 배치되어 순서대로 접근되는 경우다.

캐시 접근 원리

프로세서가 주소를 참조하면 먼저 캐시를 검사한다.

캐시에 있으면 적중이고, 캐시에서 바로 값을 돌려준다.

없으면 실패다. 이때 주 기억장치에서 주소가 든 블록을 통째로 가져온다.

블록은 캐시 라인 단위라서 인접 주소가 함께 올라온다. 공간 지역성이 여기서 살아난다.

다음 접근부터는 캐시에서 해결되어 미스가 줄어든다. 블록 크기는 구현마다 다르다.

평균 접근 시간

평균 접근 시간은 적중률 h로 가중한 Tc와 Tm의 합이다.

가상의 값으로 h는 0.95, Tc는 1ns, Tm은 100ns라고 하자.

대입하면 0.95 × 1 + 0.05 × 100 이므로 5.95ns가 된다.

적중률이 조금만 떨어져도 Tm의 가중치 때문에 평균 시간이 크게 늘어난다.

h가 커지면 평균 접근 시간이 줄어든다. 그래서 적중률 향상이 성능의 핵심이다.

세 지역성 비교

두 지역성은 헷갈리기 쉽다. 표로 구분해 쓰면 채점에 유리하다.

시간 지역성은 같은 대상의 재사용이고, 공간 지역성은 인접 주소의 사용이다.

시간 지역성의 핵심은 캐시 교체 정책이고, 공간 지역성의 핵심은 캐시 라인 크기다.

행 우선 순회는 연속 주소를 차례로 접근해 공간 지역성에 맞다. 열 방향 순회는 맞지 않다.

가상 메모리와 한계

가상 메모리도 같은 원리를 쓴다. 프로세스가 짧은 기간 쓰는 페이지 집합을 워킹 셋이라 한다.

워킹 셋이 메모리에 머물면 페이지 부재가 줄어든다. 워킹 셋이 메모리보다 커지면 스래싱이 생긴다.

참조가 흩어지면 지역성은 약해진다. 포인터 추적과 해시 테이블 탐색이 대표 예다.

지역성을 높이면 항상 빨라진다고 단정하면 안 된다. 접근 패턴을 함께 봐야 한다.

정리

정리하면 지역성은 프로그램이 메모리를 집중해서 참조하는 성질이다.

시간 지역성과 공간 지역성을 구분해 설명하는 것이 채점의 핵심이다.

이 원리 덕분에 작은 고속 기억장치가 큰 저속 기억장치를 대신할 수 있다.