[CSAPP] 6.2 Locality(지역성)

6.2 Locality(지역성)

• 잘 작성된 컴퓨터 프로그램은 좋은 지역성(Locality)을 보이는 경향이 있다.
  • 즉 최근에 참조된 데이터 항목을 참조하는 경향을 가진다.
• 지역성(Locality)의 원칙으로 알려진 이러한 경향은 하드웨어 및 소프트웨어 시스템의 설계와 성능에 막대한 영향을 미치는 지속적인 개념이다.
• 지역성(Locality)은 일반적으로 두 가지 다른 형태를 갖는다.
  • 시간적 지역성(temporal locality): 시간적 지역성이 좋으면 한 번 참조된 메모리 위치는 가까운 미래에 여러 번 다시 참조될 가능성이 높다.
  • 공간적 지역성(spatial locality) 공간적 지역성이 좋으면 메모리 위치가 참조되는 경우 다른 데이터 항목에 가깝거나 최근에 참조된 데이터 항목을 참조하는 경향이 있다.
• 지역성(Locality)이 좋은 프로그램은 지역성(Locality)이 나쁜 프로그램 보다 빠르게 실행되기 때문에 프로그래머는 지역성(Locality)의 원리를 이해해야 한다.
• 하드웨어에서 운영 체제, 응용 프로그램에 이르기까지 모든 수준의 최신 컴퓨터 시스템은 지역성(Locality)을 활용하도록 설계되어 있다.
• 하드웨어 수준에서 지역성(Locality)원리는 컴퓨터 설계자가 가장 최근에 참조된 instruction과 데이터 항목의 블록을 보유하는 캐시 메모리로 알려진 작은 고속 메모리를 도입하여 주 메모리 엑세스 속도를 높이는 것이다.
• 운영체제 수준에서 지역성(Locality) 원리는 시스템이 주 메모리를 가상 주소 공간의 가장 최근에 참조된 캐시를 사용하는 것이다. 또한, 운영 체제는 메인 메모리를 사용하여 디스크 파일 시스템에서 가장 최근에 사용한 디스크 블록을 캐시하는 것이다. 
• 응용 프로그램의 설계에서 지역성(Locality) 원리는 예를 들어, 웹 브라우저 경우 최근에 참조된 문서를 로컬 디스크에 캐시하여 시간적 지역성(temporal locality)을 이용한다. 따라서 대용량 웹 서버는 서버의 개입 없이 문서에 대한 요청을 충족하는 최근 요청된 문서를 프론트 엔드 디스크 캐시에 보관한다.

6.2.1 Locality of References to Program Data(프로그램 데이터 참조의 지역성)

• 위 그림 (a)의 간단한 함수를 예시로 보자
• 이 함수는 지역성(Locality)이 좋은가?
  • 이 질문에 대답 하기 위해 각 변수에 대한 참조 패턴을 살펴보자.
    • sum 변수는 각 루프 반복에서 한 번씩 참조되므로, sum 변수와 관련하여 좋은 시간적 지역성(temporal locality)이 있다.
    • 반면에, sum은 스칼라이므로 sum에 대한 공간적 지역성(spatial locality)은 없다.
    • 그림 (b)에서 볼 수 있듯이, 벡터 v의 요소는 메모리에 저장된 순서대로 차례로 읽힌다.따라서 변수 v와 관련하여 각 벡터 요소가 정확히 한 번 엑세스 되기 때문에 공간적 지역성(spatial locality)은 좋지만(데이터 항목에 가까운 곳에 위치하기 때문에) 시간적 지역성(temporal locality)은 좋지 않다(다른 메모리 위치를 참조하고 있기 때문에) 
    • 전체적으로 함수는 루프 본체의 각 변수에 대한 좋은 시간적 지역성(temporal locality) 또는 공간적 지역성(spatial locality)을 갖고 있기 때문에, 우리는 sumvec함수가 좋은 지역성을 가지고 있다고 결론을 내릴 수 있다.
• 벡터의 각 요소를 순차적으로 방문하는 sumvec과 같은 함수는 stride-1 참조 패턴을 갖는다고 한다. 앞으로 때때로 stride-1 기준 패턴을 순차적 기준 패턴으로 언급할 것이다. 
• 연속 벡터의 모든 보폭이 k인 요소를 방문하는 것은 stride-k 참조 패턴이라고 한다. 
• stride-1 참조 패턴은 프로그램에서 공간적 지역성(spatial locality)의 공통적으로 중요한 소스이다. 
• 일반적으로 간격이 증가하면 공간적 지역성(spatial locality)이 감소한다. 

• stride는 다차원 배열을 참조하는 프로그램에서도 중요한 문제이다.
  • 예를 들어, 2차원 배열의 요소를 합한 위 그림 (a)의 sumarrayrow 함수의 경우, 이중 중첩 루프로 배열 요소를 행 ~ 열 순서로 읽는다. 즉 내부 루프는 첫번째 행의 요소들을 읽고 난 후 두번째 행의 요소들을 읽는다.
  • sumarrayrows 함수는 배열이 저장되는 동일한 행의 열 요소들을 읽기 때문에 공간적 지역성(spatial locality)이 좋다. 그림 (b)
  • 결과적으로 공간적 지역성(spatial locality)가 좋은 stride-1 참조 패턴이 된다. 

• 사소한 프로그램 변경이 프로그램의 지역성(Locality)에 큰 영향을 끼칠 수 있다.
• 위 그림 (a) sumarraycols 함수는 그림 6.18(a) sumarrayrows 함수와 동일한 결과를 반환한다.
• 유일한 차이점을 i 루프와 j루프를 교환한 것이다. 
• 이는 열 단위로 배열을 검색하기 때문에 공간적 지역성(spatial locality)이 좋지 않다. (실제 배열 구조에서는 일렬로 나열되어 저장되어 있는 형태이기 때문에 열 단위로 접근할 경우 간격이 넓어지기 때문이다)

6.2.2 Locality of Instruction Fetches

• 프로그램 instruction은 메모리 저장되며 CPU에 의해 가져오기(읽기)되어야 하기 때문에 instruction 가져오기와 관련된 프로그램의 지역성(Locality)도 평가할 수 있다. 
  • 예를 들어 그림 6.17에서 for 루프 본문의 instruction은 순차적인 메모리 순서로 실행되므로 루프는 좋은 공간적 지역성(spatial locality)을 갖는다. (jmp 없이 순서대로 실행되기 때문에 좋다)
  • 루프 본체는 여러 번 실행되므로 시간적 지역성(temporal locality)도 좋다.

6.2.3 Summary of Locality(지역성 요약)

• 동일한 변수를 반복적으로 참조하는 프로그램은 좋은 시간적 지역성(temporal locality)을 갖는다.
• stride-k 참조 패턴이 있는 프로그램은 stride(간격)가 작을 수록 공간적 지역성(spatial locality)가 좋다.
• instruction fetch와 관련하여 루프는 시간적 지역성(temporal locality) 및 공간적 지역성(spatial locality)이 좋다. 루프 body가 작고 루프 반복 횟수가 많을수록 지역성(Locality)이 향상된다. 
• 이 장의 뒷부분에서는 캐시 메모리와 캐시 메모리의 작동 방식에 대해 학습하고 cache hits and misses 측면에서 지역성(temporal locality)을 높이는 방법을 보일 것이다.