참조 위치

Locality of reference

컴퓨터 과학에서 참조의 국소성(國,[1]性)은 국소성의 원리로도 알려져 있으며 프로세서가 단시간에 [2]걸쳐 동일한 메모리 위치에 반복적으로 액세스하는 경향입니다.기준 지역에는 시간적 및 공간적 지역이라는 두 가지 기본적인 유형이 있습니다.시간적 국지성은 비교적 짧은 시간 내에 특정 데이터 및/또는 자원을 재사용하는 것을 말합니다.공간적 인접성(데이터[3] 인접성이라고도 함)은 비교적 가까운 저장 위치 내에서 데이터 요소를 사용하는 것을 의미합니다.순차적 국소성(sequential locality)은 공간적 국소성의 특수한 경우로, 1차원 배열의 요소를 통과하는 것과 같이 데이터 요소가 선형으로 배열되고 액세스될 때 발생합니다.

로컬리티는 컴퓨터 시스템에서 발생하는 예측 가능한 동작의 한 종류입니다.프로세서 코어의 파이프라인 단계에서 캐싱, 메모리 프리페치, 고급 분기 예측 변수 등의 기술을 사용하여 강력한 참조 인접성을 보이는 시스템은 성능 최적화를 위한 좋은 후보입니다.

지역 유형

참조 인접성에는 몇 가지 다른 유형이 있습니다.

  • 시간적 인접성:어느 시점에서 특정 메모리 위치가 참조되고 있는 경우는, 가까운 장래에 같은 장소가 다시 참조될 가능성이 있습니다.동일한 메모리 위치에 대한 인접 참조 간에는 시간적 근접성이 있습니다.이 경우 참조된 데이터의 복사본을 고속 메모리 스토리지에 저장하여 후속 참조의 지연 시간을 줄이는 것이 일반적입니다.시간적 국소성은 공간적 국소성(아래 참조)의 특수한 경우, 즉 예상 위치가 현재 위치와 동일한 경우이다.
  • 공간적 인접성:특정 시간에 특정 저장 위치를 참조할 경우 가까운 메모리 위치가 참조될 수 있습니다.이 경우 현재 참조 주변의 영역 크기와 모양을 추측하는 것이 일반적이며, 이후 참조를 위해 더 빠른 액세스를 준비하는 것이 좋습니다.
    • 메모리 인접성(또는 데이터[3] 인접성):메모리와 관련된 공간적 위치.
  • 지점 위치:시공간 좌표 공간에서 경로의 예상 부분에 대해 몇 가지 가능한 대안이 있는 경우.이것은 명령 루프가 단순한 구조를 가지거나 조건부 분기 명령의 작은 시스템의 가능한 결과가 작은 가능성 집합으로 제한되는 경우입니다.브랜치 로지컬은 일반적으로 공간 로지컬이 아닙니다.이는 몇 가지 가능성이 서로 떨어져 있을 수 있기 때문입니다.
  • 등거리 지역:공간적 지역성과 지점적 지역성의 중간.등거리 패턴의 위치에 접근하는 루프, 즉 공간-시간 좌표 공간의 경로가 점선이라고 생각해 보십시오.이 경우 간단한 선형 함수를 통해 가까운 미래에 액세스될 위치를 예측할 수 있습니다.

빈번하게 발생하는 시간적 및 공간적 위치로부터 이익을 얻기 위해, 대부분의 정보 스토리지 시스템은 계층적입니다.등거리 인접성은 보통 프로세서의 다양한 중요하지 않은 증분 명령에 의해 지원됩니다.브랜치 로컬의 경우, 현재의 프로세서는 고도의 브랜치 프레딕터를 가지며, 이 예측에 근거해 프로세서의 메모리 매니저는 타당한 대체의 데이터를 수집해 전처리하려고 한다.

관련성

지역적인 이유에는 여러 가지가 있다.이러한 이유는 측면에 따라 달성해야 할 목표 또는 수용해야 할 상황 중 하나입니다.다음 이유는 분리되지 않습니다.실제로 아래 목록은 가장 일반적인 경우에서 특수한 경우로 넘어갑니다.

  • 예측 가능성:로컬리티는 컴퓨터 시스템에서 예측 가능한 동작의 한 종류일 뿐입니다.
  • 프로그램 구조:로컬리티는 중대한 문제를 처리하기 위해 컴퓨터 프로그램이 생성되는 방식 때문에 자주 발생합니다.일반적으로 관련 데이터는 가까운 장소에 저장된다.컴퓨팅의 일반적인 패턴 중 하나는 여러 항목을 한 번에 하나씩 처리하는 것입니다.즉, 많은 처리를 하면 단일 항목에 한 번 이상 액세스하여 참조의 시간적 위치를 얻을 수 있습니다.게다가 다음 항목으로 이동하는 것은 메모리 위치가 일반적으로 일괄적으로 읽히기 때문에 다음 항목이 읽히고, 따라서 참조의 공간적 위치가 읽히는 것을 의미한다.
  • 선형 데이터 구조:인접성은 종종 코드에 인덱스로 배열 또는 기타 데이터 구조를 참조하는 경향이 있는 루프가 포함되어 있기 때문에 발생합니다.순차적 지역성은 공간적 지역성의 특수한 경우로, 관련 데이터 요소가 선형으로 배열되고 액세스될 때 발생합니다.예를 들어, 기본 주소에서 최상위 요소까지 1차원 배열의 요소를 단순 트래버설하면 메모리 [4]내 배열의 순차적 인접성을 이용할 수 있습니다.등거리 로컬리티는 선형 트래버설이 구조 및 크기가 동일한 인접 데이터 구조의 더 긴 영역에 걸쳐 각 구조가 아닌 각 구조의 서로 대응하는 요소에 액세스할 때 발생합니다.행렬이 행의 순차 행렬로 표현되고 행렬의 단일 열에 액세스해야 하는 경우입니다.
  • 메모리 계층 사용 효율성:랜덤 액세스 메모리는 프로그래머에게 언제 어디서나 읽거나 쓸 수 있는 기능을 제공하지만 실제로는 캐시 효율에 의해 지연과 throughput이 영향을 받습니다.이것은 참조의 인접성을 높임으로써 개선됩니다.참조 인접성이 낮으면 캐시 스레싱 및 캐시 오염이 발생하며, 이를 방지하기 위해 인접성이 낮은 데이터 요소를 캐시에서 바이패스할 수 있습니다.

일반적인 사용법

참조의 상당 부분이 클러스터로 집약되어 이 클러스터 시스템의 형태를 잘 예측할 수 있다면 퍼포먼스 최적화에 사용할 수 있습니다.최적화 기술을 사용하여 로컬로부터 이익을 얻는 방법은 여러 가지가 있습니다.일반적인 기술은 다음과 같습니다.

  • 참조 인접성 증가(일반적으로 소프트웨어 측)
  • 참조 인접성을 이용하는 중:일반적으로 하드웨어 측에서 실현되는 시간적 및 공간적 인접성은 계층적 스토리지 하드웨어에 의해 자본화될 수 있습니다.등거리 로컬은 프로세서의 적절한 전문 명령어로 사용할 수 있습니다.이러한 가능성은 하드웨어뿐만 아니라 소프트웨어도 담당합니다.또한 해당 구조가 해당 전문 명령을 호출하는 바이너리 프로그램을 컴파일하는 데 적합한지 여부입니다.지점은 더 정교한 가능성이 있기 때문에 더 많은 개발 노력이 필요하지만, 이러한 지점은 나머지 지역보다 훨씬 더 많은 미래 탐사를 위한 예비력이 있다.

공간적 및 시간적 지역성 사용

계층 메모리

주요 기사:메모리 계층

계층형 메모리는 공간적 및 시간적 로컬리티의 이점을 활용하는 하드웨어 최적화로 메모리 계층의 여러 수준에서 사용할 수 있습니다.호출은 시간적, 공간적 위치로부터 분명히 이익을 얻는다.캐시는 특별히 설계되고 빠르지만 작은 메모리 영역이기 때문에 시간적 로컬리티를 이용하는 간단한 예입니다. 일반적으로 캐시는 최근에 참조된 데이터와 데이터를 최근에 참조된 데이터 근처에 보관하기 위해 사용되므로 성능이 향상될 수 있습니다.

캐시 내의 데이터 요소는 메인 메모리에서 공간적으로 가까운 데이터 요소에 반드시 대응하는 것은 아니지만, 데이터 요소는 한 번에 한 줄씩 캐시로 가져옵니다.즉, 공간적 인접성이 다시 중요함을 의미합니다.즉, 하나의 요소가 참조되면 몇 개의 인접 요소도 캐시에 포함됩니다.마지막으로, 매우 밀접하게 참조되는 결과는 기계 레지스터에 보관될 수 있기 때문에 시간적 로컬리티는 가장 낮은 수준에서 역할을 합니다.일부 프로그래밍 언어(예: C)는 프로그래머가 특정 변수를 레지스터에 유지할 것을 제안할 수 있도록 합니다.

데이터 인접성은 일반 프로그램의 일반적인 메모리 참조 기능입니다(단, 많은 불규칙한 메모리 액세스 패턴이 존재합니다).계층형 메모리 레이아웃을 수익성 있게 만듭니다.컴퓨터에서 메모리는 데이터 액세스 속도를 높이기 위해 계층으로 분할됩니다.메모리 계층의 낮은 레벨은 느리지만 큰 경향이 있습니다.따라서 프로그램이 메모리 계층의 상위 레벨에 캐시되어 있는 동안 메모리를 사용하면 성능이 향상되고 나중에 사용될 데이터를 대체할 다른 데이터를 계층의 상위 레벨로 가져오는 것을 피할 수 있습니다.이것은 이상이며, 때로는 달성할 수 없습니다.

일반적인 메모리 계층(접근 시간과 캐시 크기는 2013년 기준으로 사용된 일반적인 값의 근사치입니다. 계층 내 실제 값과 실제 레벨 수는 다양합니다.)

  • CPU 레지스터(8~256 레지스터)– 프로세서의 가장 안쪽 코어의 속도로 즉시 액세스 가능
  • L1 CPU 캐시(32KB~512KB)– 각 코어가 소유한 가장 안쪽 메모리 버스의 속도를 가진 고속 액세스
  • L2 CPU 캐시(128KB~24MB)– 접근 속도가 약간 느리고 메모리 버스 속도는 쌍둥이 코어 간에 공유됩니다.
  • L3 CPU 캐시 (최대 2MB, 최대 64MB)– 같은 프로세서의 더 많은 코어 간에 메모리 버스 속도를 공유하여 접근 속도가 더 느립니다.
  • 메인 물리 메모리 (RAM) (256 MB ~64 GB)– 저속 액세스.프로세서와 메인보드 메모리 모듈 간의 공간적 거리와 일반적인 하드웨어 인터페이스에 의해 속도가 제한됩니다.
  • 디스크 (가상 메모리, 파일 시스템) (1 GB ~256 TB)– 매우 느립니다.이는 좁은 (비트 폭), 컴퓨터의 메인보드와 디스크 디바이스 사이의 데이터 채널이 물리적으로 길기 때문입니다.또한 하드웨어 인터페이스 상부에 필요한 불필요한 소프트웨어 프로토콜이 필요하기 때문입니다.
  • 리모트 메모리(기타 컴퓨터 또는 클라우드)– 속도는 매우 느린 것부터 매우 느린 것까지 다양합니다.

최신의 머신에서는, 메모리 계층의 다음 레벨에 메모리 블록이 읽혀지는 경향이 있습니다.이것에 의해, 사용 끝난 메모리가 대체되는 경우, operating system은 액세스 빈도가 낮은(또는 최신) 데이터를 예측해, 메모리 계층아래로 이동하려고 합니다.예측 알고리즘은 하드웨어의 복잡성을 줄이기 위해 단순해지는 경향이 있지만 다소 복잡해지고 있습니다.

행렬 곱셈

일반적인 예는 행렬 곱셈입니다.

위해서 i 에 0..n   위해서 j 에 0..m     위해서 k 에 0..p       C[i][j] = C[i][j] + A[i][k] * B[k][j];

루핑 순서를 바꿈으로써j그리고.k적어도 마지막 차원에 연속된 배열 요소를 배치하는 언어에서는 대규모 행렬 곱셈의 속도가 극적으로 향상됩니다.이것은 수학적인 결과를 바꾸지는 않지만 효율을 향상시킵니다.이 경우 "대형"은 각 매트릭스에 약 100,000개 이상의 요소 또는 L1 및 L2 캐시에 매트릭스가 들어가지 않도록 충분한 주소 지정 가능 메모리를 의미합니다. 

위해서 i 에 0..n   위해서 k 에 0..p     위해서 j 에 0..m       C[i][j] = C[i][j] + A[i][k] * B[k][j];

이 속도가 빨라진 이유는 첫 번째 경우,A[i][k]캐시에 있습니다(이후로kindex는 연속된 마지막 치수입니다만,B[k][j]그렇지 않기 때문에 캐시 미스 패널티가 발생합니다.B[k][j].C[i][j]내부 루프에서 들어올릴 수 있기 때문에 관련이 없습니다.루프 변수는 다음과 같습니다.k.

위해서 i 에 0..n   위해서 j 에 0..m     임시직 = C[i][j]     위해서 k 에 0..p       임시직 = 임시직 + A[i][k] * B[k][j];     C[i][j] = 임시직

두 번째 예에서는 의 읽기와 쓰기가C[i][j]둘 다 캐시에 있습니다.B[k][j]캐시에 저장되어 있는 것 및A[i][k]내부 루프에서 들어올릴 수 있습니다. 

위해서 i 에 0..n   위해서 k 에 0..p     임시직 = A[i][k]     위해서 j 에 0..m       C[i][j] = C[i][j] + 임시직 * B[k][j];

따라서 두 번째 예에서는 내부 루프에 캐시 미스 패널티가 없고 첫 번째 예에서는 캐시 패널티가 있습니다.

2014년 프로세서에서는 두 번째 케이스가 첫 번째 케이스보다 약 5배 더 빠릅니다. C로 기술하고 컴파일하면gcc -O3(해체된 코드를 주의 깊게 조사하면 첫 번째 케이스에서는 GCC가 SIMD 명령을 사용하고 두 번째 케이스에서는 사용하지 않지만 캐시 패널티가 SIMD 게인보다 훨씬 심각하다는 것을 알 수 있습니다).[citation needed]

위의 예에서는 블로킹이라고 불리는 기술을 사용하여 시간적 인접성을 개선할 수도 있습니다.큰 행렬은 크기가 균일한 하위 행렬로 나눌 수 있으므로 메모리에 있는 동안 작은 블록을 여러 번 참조(승수)할 수 있습니다.이 예제는 SIZE x SIZE의 정사각형 행렬에 적용되지만 필요에 따라 SIZE_I, SIZE_J 및 SIZE_K를 대체하여 임의의 행렬에 쉽게 확장할 수 있습니다. 

위해서 (ii = 0; ii < > 크기; ii += 블록_사이즈)   위해서 (ㅋㅋ = 0; ㅋㅋ < > 크기; ㅋㅋ += 블록_사이즈)     위해서 (JJ = 0; JJ < > 크기; JJ += 블록_사이즈)       맥시 = 분(ii + 블록_사이즈, 크기);       위해서 (i = ii; i < > 맥시; i++)         최대 = 분(ㅋㅋ + 블록_사이즈, 크기);         위해서 (k = ㅋㅋ; k < > 최대; k++)           maxj = 분(JJ + 블록_사이즈, 크기);           위해서 (j = JJ; j < > maxj; j++)             C[i][j] = C[i][j] + A[i][k] * B[k][j];

위의 솔루션의 시간적 위치는 블록을 이동하기 전에 여러 번 사용할 수 있기 때문에 메모리 안팎으로 이동하는 빈도가 낮기 때문에 제공됩니다.연속된 메모리 주소를 가지는 요소가 메모리 계층을 함께 끌어올리는 경향이 있기 때문에 공간적 인접성이 향상됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 물리학의 국소성 원리와 혼동하지 말 것.
  2. ^ William., Stallings (2010). Computer organization and architecture : designing for performance (8th ed.). Upper Saddle River, NJ: Prentice Hall. ISBN 9780136073734. OCLC 268788976.
  3. ^ a b "NIST 빅데이터 상호운용성 프레임워크: Volume 1", [https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028/NIST.SP.1500-1r2]
  4. ^ 아호, 람, 세티, 울만."컴파일러: 원칙, 기술 및 도구" 제2판Pearson Education, Inc. 2007

참고 문헌