DevBasic/Concept

[컴퓨터구조] locality 개념

locality 정의, locality란, spatial locality, temporal locality, 알고리즘 면접

안녕하세요. 이번 글에서는 Locality에 대해서 알아보겠습니다.

호기심을 더하기 위해서 문제 하나 내 볼께요. 두 가지 중에 어느 것이 더 빠를까요?

1
2
3
4
5
6
7
8
9
10
11
// 1번

int a[100][100];

for(i=0; i<100; i++)
 {
    for(j=0; j<100; j++)
    {
        a[i][j] = 10;    
    }
 }

Or

1
2
3
4
5
6
7
8
9
// 2번

for(i=0; i<100; i++)
 {
    for(j=0; j<100; j++)
    {
       a[j][i] = 10;    
    }
 }

고민을 조금 해보셨나요? 정답은…

1번, Spatial locality와 관련이 있습니다. 본론으로 넘어가볼께요.

locality 정의

  • 기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한순간에 특정 부분을 집중적으로 참조하는 특성

제가 조금 더 쉽게 예를 들어 보겠습니다. 저에게는 짝사랑하는 여자사람이 있어요. 그 여자분은 ‘A 카페’ 의 수박 주스를 아주 좋아한다는 정보를 얻었어요. 마침 운이 좋게 데이트 신청을 하였는데 이번 주 주말에 시간이 될 것 같다고 하는 거예요. 그렇다면 저는 여러 계획을 세울 거예요..

  • ‘a카페’에서 수박주스 먹기
  • ‘a카페’ 근처의 맛집 찾아보기
  • 등등

이제 조금 이해가 되셨나요? 결론적으로는 CPU가 Memory로부터 Data를 가져오는 데 있어서 가장 최근 영역에, 가장 접근하기 가까운 영역에 Data를 저장하면 훨씬 효과적이라는 것입니다.

대표적인 Locality의 종류

1. Temporal locality
  • 설명
    • 최근 사용되었던 기억 장소들이 집중적으로 엑세스되는 경향.
    • 프로그램 실행시 한번 접근이 이루어진 주소의 메모리 영역은 자주 접하게 된다는 프로그램 성격 표현.
  • 예
    • 순환, Sub program, Stack 등등.
2. Spatical locality
  • 설명
    • 특정 클레스터의 기억 장소들에대해 참조가 집중적으로 이루어지는 경향.
    • 프로그램 실행시 접근하는 메모리의 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현.
  • 예
    • Sequential processing, Array 등등.

Locality의 활용

1. Working Set을 통한 thrashing 방지.
  • Working Set : 어느 시점에 특정 프로세스가 접근하는 page들의 집합(프로세스의 locality).
  • Thrashing : 실행 시간보다 페이지를 찾는데 시간과 자원이 소비되는 현상.
2. Fetch 알고리즘
  • Pre-fetch : 필요한 정보와 예상 정보를 미리 인출하여 배치.
3. CDN(Contents Delivery Network)에서 공간 지역성을 활용한 지역 Cache 서버 구성
4. 등등

이상 locality에 대해서 알아보았습니다.

Share