locality-of-reference
Q&A 정리: locality-of-reference
Locality of reference(참조 지역성)란 무엇인가?
프로세서가 짧은 시간 동안 같은 메모리 영역을 반복해서 접근하는 경향을 말한다. 사람이 책을 읽을 때 한 페이지 근처를 계속 왔다 갔다 하는 것과 비슷하며, 시간적 지역성과 공간적 지역성 두 가지로 나뉜다.
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference locality – temporal and spatial locality. Locality is a type of predictable behavior that occurs in computer systems.
Temporal locality란 무엇인가?
최근에 사용한 데이터를 가까운 미래에 다시 사용할 가능성이 높다는 원리다. 자주 거는 전화번호를 최근 통화 목록에서 바로 찾는 것과 같다.
Temporal locality refers to the reuse of specific data and/or resources within a relatively small time duration. Temporal locality is a special case of spatial locality, namely when the prospective location is identical to the present location.
Spatial locality란 무엇인가?
한 데이터를 사용하면 그 근처에 저장된 데이터도 곧 사용될 가능성이 높다는 원리다. 책에서 한 문장을 읽으면 바로 다음 문장도 읽게 되는 것과 같다.
Spatial locality (also termed data locality) refers to the use of data elements within relatively close storage locations.
Sequential locality란 무엇인가?
공간적 지역성의 특수한 경우로, 데이터가 순서대로 나열되어 있고 접근도 순서대로 일어나는 패턴이다. 배열을 처음부터 끝까지 차례로 읽는 것이 대표적인 예다.
Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as traversing the elements in a one-dimensional array.
캐시가 locality of reference를 활용하는 방식은?
캐시는 최근 사용한 데이터와 그 주변 데이터를 빠른 메모리에 미리 복사해 둔다. 시간적 지역성 덕분에 같은 데이터를 다시 요청할 때 빠르게 응답할 수 있고, 공간적 지역성 덕분에 주변 데이터도 미리 준비해 둘 수 있다.
A cache is a simple example of exploiting temporal locality, because it is a specially designed, faster but smaller memory area, generally used to keep recently referenced data and data near recently referenced data, which can lead to potential performance increases. Temporal locality plays a role on the lowest level, since results that are referenced very closely together can be kept in the machine registers.
캐시에 저장된 데이터는 메인 메모리에서 공간적으로 가까운 데이터끼리 모여있는가?
반드시 그렇지는 않다. 캐시는 데이터를 "캐시 라인"이라는 묶음 단위로 가져오는데, 서로 다른 캐시 라인에 담긴 데이터는 메인 메모리에서 멀리 떨어져 있을 수 있다. 같은 캐시 라인 안의 데이터만 메모리상 이웃이다.
Data elements in a cache do not necessarily correspond to data elements that are spatially close in the main memory; however, data elements are brought into cache one cache line at a time.