TIL 230924

CSAPP (p.640 ~ 645)

6.2 Locality

지역성의 원리(Principle of Locality)

프로그램은 최근에 참조했던 데이터 항목이나 그 근처 데이터 항목을 참조하는 경향을 가지는데, 이를 지역성의 원리라고 함

좋은 시간 지역성을 가지는 프로그램은 참조한 메모리 주소를 가까운 미래에 여러 번 다시 참조함
좋은 공간 지역성을 가지는 프로그햄은 참조한 메모리 주소 근처 메모리 주소를 가까운 미래에 참조함

좋은 지역성을 가지는 프로그램은 그렇지 않은 프로그램보다 빠르게 실행됨

지역성 활용 예시

모든 레벨의 컴퓨터 시스템은 지역성을 활용하도록 설계되어 있음

1. 하드웨어 레벨
   가장 최근에 참조한 명령어와 데이터 항목의 블록을 저장하는 캐시 메모리를 도입함으로써 메인 메모리 액세스 속도를 높일 수 있음
2. 운영체제 레벨
   메인 메모리를 가상 주소 공간에서 가장 최근에 참조한 청크(chunk)들을 보관하는 캐시로서 활용할 수 있음
   비슷하게, 메인 메모리를 디스크 파일 시스템에서 가장 최근에 참조된 디스크 블록을 캐시하는 데 사용함
3. 애플리케이션 레벨
   웹 브라우저는 시간 지역성을 활용해서 최근에 참조한 문서를 로컬 디스크에 캐시함
   high-volume 웹 서버는 최근 요청된 문서를 프론트엔드 디스크 캐시에 보관하고 나중에 해당 문서에 대한 요청이 들어오면 서버 개입 없이 응답을 줄 수 있음

데이터/명령어 지역성

stride-k reference pattern을 가지는 프로그램은 stride가 작을수록 더 좋은 공간 지역성을 가짐
루프는 명령어 인출(fetch)와 관련해 좋은 시간/공간 지역성을 가지는데, 루프 body가 작을수록, iteration이 많을수록 지역성이 더 좋아짐