2019년 4월 29일
지역성 (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 |
About The Author
