지역성 (Locality)

I. 집중적 액세스, Locality의 개념

가. Locality의 의미

  • CPU가 기억장치의 특정 부분에 위치한 데이터나 프로그램 코드를 집중적으로 액세스하는 현상
  • 컴퓨터의 구성요소 간 속도 차이로 인한 병목현상이 발생하지만 Locality의 특성을 이용하여 고비용/고속 저장장치의 효율적 사용 및 속도 향상 가능

나. Locality의 목표

목표설명
빠른 접근 시간– Cache Access Time의 최소화
적중률 최대화– Cache Hit Rate의 최대화
  • Cache Hit Rate = Hit 수 / 기억장치 접근의 총 수

 

II. Locality의 유형

유형설명사례
Temporal
Locality
(시간적
지역성)

– 최근 액세스 된 기억 장소가 가까운 미래에 다시 액세스 가능성 높음
반복 루프
서브 루틴
공통 변수
LRU
Spatial
Locality
(공간적
지역성)

– 액세스된 기억장소와 인접한 기억장소가 액세스될 가능성 높음
배열(Array)
Pre-Fetch
Sequential
Locality
(순차적
지역성)
– 분기가 발생하지 않는 한, 명령어들은 기억장치에 저장된 순서대로 인출되어 실행되는 특성 
  • Sequential Locality(순차적 지역성)는 별도의 유형으로 구분하지 않고 공간적 지역성에 포함시키기도 함

 

III. Locality 활용 사례

가. Cache Memory 활용 사례

사례설명유형
LRU (Least
Recently Used)
– 캐시 교체 알고리즘 구현
– 참조 시간 기준 교체 블록 선정
– 가장 오랫동안 미사용 블록 교체
시간적
공간적
선인출
(Pre-Fetch)
– 캐시 인출 알고리즘 구현
– 향후 필요 예측 정보의 블록을 미리 캐시로 인출하여 배치
공간적
시간적
  • Cache Memory는 Locality 특성을 이용하여 적중율(Hit Rate)을 높여 고속 기억장치 효율적 이용

나. Virtual Memory 활용 사례

사례설명유형
워킹셋
(Working Set)

– Thrashing 해결 기법
– 특정 시간 실행 프로그램의 최근 참조 페이지 집합
시간적
지역성

다. Network 활용 사례

사례설명유형
CDN
(Content Delivery Network)

– 콘텐츠의 효율적 전달 위해 여러 노드에 데이터 저장하여 제공
– 서비스 요청자와 가까운 서버에서 콘텐츠 제공
공간적
지역성

 

IV. Locality 소스코드 사례

소스코드설명
for (i=0; i<10; i++)
data[i+1] = data[i] + 1;
[실행]
data[1] = data[0] + 1;
data[2] = data[1] + 1;
[시간적 지역성]
– data[1]는 다음 순환에서 read
 
[공간적 지역성]
– data[0]부터 data[9] 까지 read

 

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^