Locality

Well-written computer programs tend to exhibit good locality. That is, they tend to reference data items that are near other recently referenced data items or that were recently referenced themselves. This tendency, known as the principle of locality, is an enduring concept that has enormous impact on the design and performance of hardware and software systems.

잘 짜여진 프로그램은 좋은 지역성을 갖는 경향이 있습니다. 이는 프로그램이 최근에 사용한 데이터가 최근에 참조됐거나, 그 참조된 데이터 주변에 있는 경향성을 띕니다.
이러한 경향성은 '지역성의 원리'로 알려져 있으며, 하드웨어와 소프트웨어 시스템의 성능과 설계에 엄청난 영향을 주는 지속적인 개념입니다.

Locality is typically described as having two distinct forms: temporal locality and spatial locality. In a program with good temporal locality, a memory location that is referenced once is likely to be referenced again multiple times in the near future. In a program with good spatial locality, if a memory location is referenced once, then the program is likely to reference a nearby memory location in the near future.

지역성은 일반론적으로 시간과 공간 두 가지의 구분되는 형식이 있습니다.


Temporal locality 은 한 번 참조된 지역은 가까운 시간 내에 여러번 참조되는 것을 나타냅니다.
Spatial locality 는 한 번 참조된 메모리 지역의 근처를 가까운 시간 내에 참조하는 것을 나타냅니다.

Programmers should understand the principle of locality because, in general, programs with good locality run faster than programs with poor locality. All levels of modern computer systems, from the hardware, to the operating system, to application programs, are designed to exploit locality.

프로그래머는 지역성의 원리를 알아야 합니다. 일반론적으로, 좋은 지역성을 갖는 프로그램을 더 빨리 구동되기 때문입니다. 하드웨에어소 OS, 응용 프로그램들은 좋은 지역성을 활용하기 위해 설계되고 있습니다.

At the hardware level, the principle of locality allows computer designers to speed up main memory accesses by introducing small fast memories known as cache memories that hold blocks of the most recently referenced instructions and data items. At the operating system level, the principle of locality allows the system to use the main memory as a cache of the most recently referenced chunks of the virtual address space.

하드웨어 레벨에서, 지역성은 가장 최근에 사용된 데이터를 담는 캐시 메모리라고 불리는 작고 빠른 메모리를 도입함으로써 메인 메모리 접근속도를 높혔습니다.


운영체제 레벨에서는, 지역성의 원리는 메인 메모리를 가장 최근에 사용한 가상 주소 공간블록의 캐시로 사용될 수 있게 해줍니다.

Similarly, the operating system uses main memory to cache the most recently used disk blocks in the disk file system. The principle of locality also plays a crucial role in the design of application programs. For example, Web browsers exploit temporal locality by caching recently referenced documents on a local disk.

이와 유사하게, OS는 메인 메모리를 가장 최근에 사용한 디스크의 파일 블록을 캐시하기 위해 사용합니다. 지역성의 원리는 프로그램 개발에 있어 중요한 역할을 합니다. 예를 들어, 웹 브라우저는 디스크 상의 가장 최근에 참조한 문서들을 캐싱해서 시간적 지역성을 활용합니다.

6.2.1 Locality of References to Program Data

Stride-1 (순차참조패턴)

위의 함수는 벡터의 원소들이 메모리에 저장된 것 과 같은 순서로 접근하기 때문에 좋은 지역성을 갖고 있다.

위의 함수는 배열이 한 row의 cols를 순서대로 접근하기 때문에 좋은 지역성을 갖고 있다.

stride-N

위의 함수는 배열이 한 col을 기준으로 rows를 접근하고 있기에 나쁜 지역성을 갖고 있다.

6.2.2 Locality of Instruction Fetches

Since program instructions are stored in memory and must be fetched (read) by the CPU, we can also evaluate the locality of a program with respect to its instruction fetches. For example, in Figure 6.17 the instructions in the body of the for loop are executed in sequential memory order, and thus the loop enjoys good spatial locality. Since the loop body is executed multiple times, it also enjoys good temporal locality. An important property of code that distinguishes it from program data is that it is rarely modified at run time. While a program is executing, the CPU reads its instructions from memory. The CPU rarely overwrites or modifies these instructions.

프로그램의 인스트럭션들은 메모리에 저장되고 CPU에 의해 선입(읽어야) 하기 때문에 인스트럭션 선입에 관한 프로그램의 지역성도 평가할 수 있다. 예를 들어, 위의 벡터를 탐색하는 예제를 다시 상기해보자. 해당 예제에서는 메모리 순서대로 실행되기 때문에 좋은 공간 지역성을 갖는다고 할 수 있으며, for문에 의해 여러번 실행되기에 좋은 시간 지역성을 갖고 있다.


코드와 프로그램 데이터를 구분짓는 가능 큰 특징은 코드는 런타임중 거의 수정되지 않는다. 프로그램이 실행되는 동안 CPU는 메모리로부터 인스트럭션을 읽는다. 이 때 CPU는 인스트럭션을 거의 수정하거나 지우지 않는다.