[저장 기술] 국부성(시간 국부성, 공간 국부성)

CSAPP 6.2 부분성
문서 목록

1. 국부적 분류

1)시간 국부성

2) 공간 국부성

3) 국부적 원리 예

2. 프로그램 데이터 인용의 국부성

3. 국부성 평가

질문: 왜 좋은 국부적인 프로그램이 국부적인 프로그램보다 빨리 실행됩니까?

참조

1. 부분적 분류
국부적인 원리는 하드웨어와 소프트웨어 시스템의 설계와 성능에 지대한 영향을 미친다.국부성은 일반적으로 시간 국부성과 공간 국부성으로 나뉜다.
1) 시간적 국부적
시간 국부성이란 한 번 인용된 메모리 위치가 멀지 않은 미래에 여러 번 인용될 가능성이 높다는 것을 말한다.
2) 공간 부분성
공간 국부성이란 만약에 하나의 메모리 위치가 한 번 인용된다면 프로그램은 멀지 않은 미래에 그 부근의 메모리 위치를 인용할 가능성이 높다는 것을 말한다.
3) 국부적 원리 예

하드웨어 층에서 국부적인 원리는 컴퓨터 디자이너가 작고 빠른 고속 캐시 메모리를 도입하여 최근에 인용된 지령과 데이터 항목을 저장함으로써 메인 메모리에 대한 접근 속도를 높일 수 있도록 한다.

운영체제급에서 국부적인 원리는 시스템이 가상 주소 공간으로 최근에 인용된 블록의 고속 캐시를 사용할 수 있도록 허용한다.

운영체제는 디스크 파일 시스템에서 최근에 사용된 디스크 블록을 메모리로 캐시하는 것과 유사하다.

웹 브라우저가 최근에 요청한 문서를 로컬 디스크에 놓는 등 응용 프로그램의 디자인은 시간의 국부성을 이용한다.대용량의 웹 서버는 최근에 요청한 문서를 전방 디스크 캐시에 넣고 서버의 간섭 없이 이 문서에 대한 요구를 충족시킬 수 있다.

2. 프로그램 데이터 인용의 국부성
예를 들어 하나의 다차원수 그룹은 우리가 줄을 우선적으로 훑어보는 방법에 따라 한 줄이 끝나고 다음 줄이 되는 방식은 좋은 공간 국부성을 가진다. 컴퓨터가 이런 데이터를 저장할 때도 줄을 우선하는 방식에 따라 진행되기 때문에 줄을 우선적으로 훑어보는 것은 바로 이웃 위치의 데이터를 차례대로 방문하는 것이다.열로 우선적으로 훑어보면, 공간의 국부적 특성이 매우 떨어진다. 왜냐하면 이것은 인접 단원에 접근하는 데이터가 아니기 때문이다.
3. 국부성 평가

같은 변수를 반복적으로 인용하는 프로그램은 좋은 시간 국부성을 가진다.다음과 같은 수조 구화 프로그램은 for순환에 매번sum를 사용해야 한다. 이것은 좋은 시간 국부적인 프로그램이고 수조 v의 데이터에 대해 순서대로 접근하며 컴퓨터에 저장된 순서와 같기 때문에 공간 국부적도 좋다.

int sumvec(int v[N])
{
     
	int i, sum = 0;
	for(i = 0; i < N; i++)
		sum += v[i];
	return sum;
}

걸음걸이가 k인 인용 모드의 프로그램은 걸음걸이가 작을수록 공간의 국부성이 좋다.바로 다차원수 그룹의 예로 메모리에서 이리저리 뛰어다니는 프로그램 공간의 국부성이 매우 떨어진다.

질문: 왜 좋은 국부적인 프로그램이 국부적인 프로그램보다 빨리 실행됩니까?
다음 편에서 해답을 드리겠습니다.
참고 자료
《컴퓨터 시스템을 깊이 이해하라》 제6장.기억 장치 차원 구조