기억력해제
Memory disambiguation |
메모리 디스컴비지(Memory disambigation)는 프로그램 순서에서 벗어나 메모리 액세스 명령(로드 및 저장)을 실행하는 고성능 아웃오더 실행 마이크로프로세서에 의해 사용되는 일련의 기법이다.마이크로프로세서 코어 내부의 디지털 로직을 사용하여 구현된 메모리 분해를 수행하기 위한 메커니즘은 실행 시 메모리 작업 사이의 진정한 종속성을 감지하고 의존성을 위반했을 때 프로세서가 복구할 수 있도록 한다.그들은 또한 부하와 저장소의 안전하지 않은 실행을 허용함으로써 허위 메모리 의존성을 없애고 더 큰 명령 수준의 병렬 처리를 허용한다.
배경
종속성
명령을 순서 없이 실행하려고 시도할 때 마이크로프로세서는 명령들 사이의 진정한 의존성을 존중해야 한다.예를 들어, 다음과 같은 간단한 진정한 의존성을 고려하십시오.
1: $1, $2, $3 # R1 <= R2 + R3 2: $5, $1, $4 # R5 <= R1 + R4 (1에 따라 다름)
이 예에서는 다음과 같이 한다.add2번 라인에 대한 지침은add레지스터 R1이 라인 2의 추가 작업의 소스 피연산자이기 때문에 라인 1에 대한 지침.그add2번 라인에서는 다음이 될 때까지 실행할 수 없음add1호선이 완료됨.이 경우, 출처와 목적지가 등록되어 있기 때문에 의존성은 정적이며 마이크로프로세서에 의해 쉽게 결정된다.의 목적지 레지스터add1호선에 대한 지침(R1)는 명령 인코딩의 일부로서, 파이프라인의 디코딩 단계 중 초기에 마이크로프로세서에 의해 결정될 수 있다.마찬가지로, 의 소스 레지스터는add2호선에 대한 지침)R1그리고R4) 또한 명령 자체에 암호화되어 디코딩으로 결정된다.이러한 진정한 의존성을 존중하기 위해 마이크로프로세서의 스케줄러 논리는 지침 2가 필요할 때 1의 결과를 이용할 수 있도록 정확한 순서(먼저 지시 1에 이어 지시 2)로 이 지시사항을 공표할 것이다.
그 의존도가 정적으로 결정되지 않을 때 합병증이 발생한다.피연산자의 위치가 명령 인코딩 자체에 직접 지정되지 않고 레지스터 피연산자로 간접적으로 지정될 수 있기 때문에 그러한 비정적 의존성은 메모리 명령어(로드 및 저장)와 함께 발생한다.
1: $1, 2(2달러) # Mem[R2+2] <= R1 2: load $3, 4($4) # R3 <= Mem[R4+4] (아마도 1에 의존하며, 위와 같은 주소일 수 있음)
여기서 저장지시는 주소(R2+2)의 값으로 지정한 메모리 위치에 값을 쓰고, 로드지시는 주소(R4+4)의 값으로 지정한 메모리 위치에서 값을 읽는다.마이크로프로세서는 R2와 R4의 값에 따라 위치가 달라지기 때문에 이 두 가지 지침에 명시된 메모리 위치가 다른지 또는 동일한 위치인지 실행 전에 정적으로 판단할 수 없다.위치가 다를 경우 지침이 독립적이며 순서가 맞지 않게 성공적으로 실행될 수 있다.그러나 위치가 동일하면 부하 지침은 저장소에 의존하여 값을 산출한다.이것은 애매한 의존으로 알려져 있다.
잘못된 실행 및 메모리 액세스 작업
종속적인 부하/저장소 쌍이 순서가 잘못된 상태에서 실행된 경우 부하 및 저장소를 실행하면 잘못된 결과가 발생할 수 있다.MIPS 어셈블리에 제공된 다음 코드 조각을 고려하십시오.
1: div 27달러, 20달러 2달러: sw 27달러, 0($30) 3:lw 08달러, 0($31) 4: sw 26달러, 0 530) 5:lw 09달러, 0($31)
모든 레지스터 피연산자가 준비되면 스케줄링 논리가 실행 장치에 명령을 내릴 것이라고 가정한다.추가적으로 레지스터가$30그리고$31준비됨: 값$30그리고$31오래전에 계산되었고 변하지 않았다.그러나 가정해 보자.$27준비되지 않음: 값이 여전히 에 의해 계산되는 과정에 있음div가르침.마지막으로, 레지스터가$30그리고$31같은 값을 가지며, 따라서 모든 로드와 저장소는 동일한 메모리 워드에 액세스한다.
이런 상황에서 더.sw $27, 0($30)2번 라인에 대한 지시는 실행할 준비가 되지 않았지만lw $08, 0($31)3호선에 대한 지침이 준비되었다.프로세서가 다음을 허용하는 경우lw먼저 실행하라는 명령:sw로드는 메모리 시스템으로부터 오래된 값을 읽을 것이다. 그러나 그것은 단지 그것에 의해 쓰여진 값을 읽었어야 했다.sw. 프로그램 순서에서 실행된 로드와 스토어. 하지만 그들 사이에는 메모리 의존성이 있어 위반이 있었다.
마찬가지로, 레지스터가$26 준비되었다.그sw $26, 0($30)4번 라인에 대한 명령도 실행 준비가 되어 있으며, 선행보다 먼저 실행될 수 있다.lw $08, 0($31)3호선에이렇게 되면lw $08, 0($31)명령이 메모리 시스템에서 잘못된 값을 읽게 될 것이다. 왜냐하면 나중에 로드가 실행되기 전에 저장 명령이 그 값을 그곳에 기록했기 때문이다.
메모리 종속성 특성
메모리 의존성은 세 가지 맛으로 나온다.
- RAW(Read-After-Write) 종속성:진정한 종속성이라고도 알려진 RAW 종속성은 로드 작업이 가장 최근의 이전 저장소 작업에 의해 생성된 메모리에서 동일한 주소로 값을 읽을 때 발생한다.
- WAR(Write-After-Read) 종속성:반 의존성이라고도 하며, 저장 작업이 이전 로드가 읽은 값을 메모리에 쓸 때 WAR 종속성이 발생한다.
- WAW(Write-After-Write) 종속성:출력 종속성이라고도 하며, WAW 종속성은 두 저장 작업이 동일한 메모리 주소에 값을 쓸 때 발생한다.
앞의 코드 세그먼트에 세 가지 종속성이 표시됨(명확하게 하기 위해 재현됨):
1: div 27달러, 20달러 2달러: sw 27달러, 0($30) 3:lw 08달러, 0($31) 4: sw 26달러, 0 530) 5:lw 09달러, 0($31)
- 그
lw $08, 0($31)3번 라인에 대한 지침은 ROW에 의존한다.sw $27, 0($30)2호선에 대한 지시와lw $09, 0($31)5번 라인에 대한 지침은 ROW에 의존한다.sw $26, 0($30)4호선의 지시두 로드 명령어는 모두 앞의 저장소가 작성한 메모리 주소를 읽는다.그 상점들은 그 메모리 주소의 가장 최근의 생산자였고, 그 부하들은 그 메모리 주소의 값을 읽고 있다. - 그
sw $26, 0($30)4번 회선의 교시는 전쟁 의존도가 있다.lw $08, 0($31)이전 로드가 읽은 메모리 주소를 쓰기 때문에 3번 라인에 대한 지침. - 그
sw $26, 0($30)4번 라인에 대한 지침은 WAW에 의존한다.sw $27, 0($30)두 스토어가 동일한 메모리 주소에 쓰기 때문에 라인 2에 대한 지침
메모리 비활성화 메커니즘
현대의 마이크로프로세서는 하드웨어에서 구현된 다음과 같은 메커니즘을 사용하여 모호한 의존성을 해결하고 의존성을 위반했을 때 복구한다.
WAR 및 WAW 의존성 방지
스토어 지침의 값은 실행될 때 메모리 시스템(현대 마이크로프로세서, CPU 캐시)에 커밋되지 않는다.대신 메모리 주소와 저장 데이터를 포함한 저장 지시사항은 은퇴 지점에 도달할 때까지 저장 대기열에서 버퍼링된다.저장소가 은퇴하면 메모리 시스템에 값을 기록한다.이것은 더 늦은 저장소가 더 빠른 로드 이전에 실행될 수 있었기 때문에 더 이른 로드가 메모리 시스템으로부터 잘못된 값을 수신하는 위의 코드 조각에 나타난 WAR과 WAW 의존성 문제를 방지한다.
또한 은퇴할 때까지 스토어를 버퍼링하면 프로세서가 예외(예: 잘못된 주소의 부하, 0으로 나누기 등)를 발생시킬 수 있는 지침 또는 아직 방향을 알 수 없는 조건부 분기 지시사항을 따르는 스토어 지침을 추측적으로 실행할 수 있다.예외 발생 명령이 실행되지 않았거나 분기 방향이 잘못 예측된 경우 프로세서가 "잘못된 경로"에 대한 지침을 가져와 실행하게 된다.이러한 지시사항은 전혀 실행되어서는 안 된다. 예외 조건은 추측 명령이 실행되기 전에 발생했거나, 분기가 다른 방향으로 가서 다른 지시를 가져와 실행하도록 했어야 한다.프로세서가 예외 또는 분기의 오식을 발견할 때, 잘못된 경로, 추측으로 실행된 지시사항의 결과를 "제기"해야 한다.스토어의 복잡성은 잘못된 경로에 있는 스토어가 메모리 시스템에 값을 커밋하지 않아야 한다는 것이다. 스토어가 값을 커밋했다면 커밋을 "버림"할 수 없으며, 실행되지 않아야 하는 스토어 지침의 데이터에 의해 기계의 메모리 상태가 손상될 수 있다.edd.
따라서 스토어 버퍼링 없이 스토어는 예외 발생 가능한 이전의 모든 지침을 실행하고(예외를 초래하지 않고), 모든 이전 분기 방향을 알 수 있을 때까지 실행할 수 없다.지점 방향과 예외사항이 알려질 때까지 스토어를 기다리도록 강요하는 것은 질서 없는 공격성을 현저히 감소시키고 ILP(Instruction level parallelism)와 성능을 제한한다.스토어 버퍼링을 통해 스토어는 예외 발생 또는 확인되지 않은 분기 지시보다 먼저 실행되어 스토어 대기열에서 데이터를 버퍼링하지만 은퇴할 때까지 값을 커밋하지 않는다.이는 잘못 예측되거나 잘못된 경로에 있는 스토어가 메모리 시스템에 값을 커밋하는 것을 방지하는 동시에, 스토어의 완전한 비질서한 실행으로부터 향상된 ILP 및 성능을 여전히 제공한다.
출고할 스토어
은퇴할 때까지 상점을 버퍼링하면 WAW와 WAR 의존성은 피할 수 있지만 새로운 문제가 발생한다.다음 시나리오를 고려하십시오. 스토어는 스토어 대기열에서 주소와 데이터를 실행하고 버퍼링합니다.몇 가지 지시사항은 저장소가 방금 작성한 것과 동일한 메모리 주소에서 읽는 로드가 실행된다.로드가 메모리 시스템에서 데이터를 읽으면 이전 저장소에 의해 덮어쓰여졌을 이전 값을 읽게 된다.부하로 얻은 데이터는 정확하지 않을 것이다.
이 문제를 해결하기 위해 프로세서는 스토어 큐를 사용하는 스토어-투-로드 포워딩이라는 기술을 사용한다.은퇴할 때까지 스토어를 버퍼링하는 것 외에도, 스토어 대기열은 두 번째 목적을 제공한다. 즉, 완료되었지만 아직 회수되지 않은 저장소의 데이터를 이후의 부하로 전달하는 것이다.단순한 FIFO 대기열이 아니라, 저장소 대기열은 실제로 메모리 주소를 사용하여 검색된 Content-Addressable Memory(CAM)이다.로드가 실행되면, 프로그램 순서에서 논리적으로 이전인 동일한 주소로 스토어 대기열을 검색한다.일치하는 저장소가 존재하는 경우, 로드는 메모리 시스템 대신 해당 저장소에서 데이터 값을 얻는다.일치하는 저장소가 없는 경우 로드는 평소와 같이 메모리 시스템에 접근한다. 이전에 일치하는 저장소는 이미 은퇴하여 값을 커밋한 상태여야 한다.이 기법은 생산자 저장소가 완료되었지만 아직 폐기되지 않은 경우 부하가 정확한 데이터를 얻을 수 있도록 한다.
로드의 메모리 주소에 대한 여러 저장소가 스토어 대기열에 있을 수 있다.이 경우를 처리하기 위해, 프로그램 순서에서 로드보다 논리적으로 더 이른 최신 스토어를 선택하기 위해 스토어 대기열이 우선 인코딩된다.어떤 스토어가 "최신"인지 판단하려면, 어떤 종류의 타임스탬프를 가져오고 디코딩할 때 지시사항에 첨부하거나, 또는 스토어 대기열 내에서 가장 오래되고 최신 스토어에 대한 로드의 상대적 위치(슬롯)를 알고 있어야 한다.
RAW 종속성 위반
RAW 종속성 위반 탐지
현대적인 고장 CPU는 RAW 의존성 위반을 감지하기 위해 여러 가지 기술을 사용할 수 있지만, 모든 기술은 실행에서 폐기까지 비행 중 부하를 추적해야 한다.로드가 실행되면 메모리 시스템 및/또는 저장 대기열에 액세스하여 데이터 값을 얻은 다음, 해당 주소와 데이터는 은퇴할 때까지 로드 대기열에서 버퍼링된다.로드 대기열은 구조와 기능이 스토어 대기열과 유사하며, 실제로 일부 프로세서에서는 로드 스토어 대기열, 즉 LSQ라고 하는 단일 구조에서 스토어 대기열과 결합될 수 있다.RAW 의존성 위반을 감지하기 위해 다음과 같은 기법이 사용되거나 제안되었다.
대기열 CAM 검색 로드
이 기법으로 로드 대기열은 저장소 대기열과 마찬가지로 메모리 액세스 주소를 사용하여 CAM 검색되며, 모든 비행 중 로드를 추적한다.저장소가 실행되면, 그것은 논리적으로 나중에 프로그램 순서에 따라 동일한 주소에서 완료된 로드를 로드 대기열에서 검색한다.이와 같은 일치 부하가 존재하는 경우, 저장소에 앞서 실행한 것이므로 메모리 시스템/저장소 대기열에서 잘못된 이전 값을 읽어야 한다.부하 값을 사용한 모든 지시사항도 불량 데이터를 사용했다.이러한 위반이 감지될 경우 복구하기 위해, 하중을 은퇴 버퍼에 "위반"으로 표시한다.스토어는 스토어 큐와 은퇴 버퍼에 남아 정상적으로 은퇴하며, 은퇴할 때 메모리 시스템에 그 가치를 커밋한다.그러나 위반된 부하가 은퇴 지점에 도달하면 프로세서가 파이프라인을 플러시하고 부하 명령에서 실행을 재시작한다.이 시점에서, 이전의 모든 상점들은 메모리 시스템에 그들의 가치를 헌신했다.로드 명령은 이제 메모리 시스템에서 올바른 값을 읽으며, 모든 종속 지침은 올바른 값을 사용하여 다시 실행된다.
이 기법은 회로 전원을 소비하고 큰 부하 대기열의 타이밍 경로가 어려운 것으로 판명될 수 있는 모든 스토어 실행의 부하 대기열을 연관적으로 검색해야 한다.그러나 추가 메모리(캐시) 포트가 필요하거나 실행 중인 다른 로드 또는 스토어와 리소스 충돌을 일으키지 않는다.
퇴직시 불감증
이 기법으로, 고장난 것을 실행한 부하 지시는 은퇴 지점에 도달했을 때 다시 실행된다(메모리 시스템에 접속해 주소의 값을 두 번째로 읽음).이제 부하가 은퇴 지침이기 때문에, 그것은 아직 실행 중인 어떤 명령에도 의존하지 않는다; 그것 앞에 있는 모든 상점들은 그들의 값을 메모리 시스템에 맡겼기 때문에, 메모리 시스템에서 읽은 어떤 값도 정확하다고 보장된다.재실행 시 메모리에서 읽은 값을 로드가 처음 실행되었을 때 얻은 값과 비교한다.값이 같을 경우 원래 값이 정확하고 위반이 발생하지 않았다.재실행 값이 원래 값과 다를 경우 부하에 의존하는 지침이 잘못된 값을 사용했기 때문에 RAW 위반이 발생하고 파이프라인을 플러시해야 한다.
이 기법은 부하 대기열 검색보다 개념적으로 단순하며, 두 번째 CAM과 그 전력 소모가 많은 검색(이제 부하 대기열은 단순한 FIFO 대기열이 될 수 있다)을 없앤다.로드는 은퇴 직전에 메모리 시스템에 재접속해야 하므로 접근 속도가 매우 빨라야 하므로 이 체계는 고속 캐시에 의존한다.그러나 캐시가 아무리 빠르더라도, 모든 주문 외 부하 명령에 대한 두 번째 메모리 시스템 액세스는 명령 회수 지연 시간을 증가시키고 프로세서가 수행해야 하는 총 캐시 액세스 수를 증가시킨다.추가 사용 중지 시간 캐시 액세스는 기존 캐시 포트를 재사용함으로써 충족될 수 있지만, 이는 실행하려고 하는 프로세서의 다른 로드 및 저장소와 포트 리소스 경합이 발생하여 성능 저하를 초래할 수 있다.대신, 부하 해소를 위해서만 캐시 포트를 추가할 수 있지만, 이것은 캐시의 복잡성, 전력 및 면적을 증가시킨다.일부 최근 작업(Roth 2005)에서는 RAW 의존성 위반이 발생하지 않았음이 알려진 경우 재실행에서 많은 부하를 필터링하는 방법을 보여 주었다. 이러한 기술은 이러한 지연 시간과 리소스 경합에 도움이 되거나 제거할 수 있다.
(부하 큐 검색과 비교하여) 이 계획의 사소한 이점은 RAW 의존성 위반을 유발할 수 있는 스토어(스토어 주소가 비행 중 부하 주소와 일치)가 캐시에 이미 있는 데이터 값과 일치하는 데이터 값을 가진 경우 RAW 의존성 위반에 플래그를 지정하지 않고 파이프라인 플러시를 트리거한다는 것이다.하중-대기열 검색 방식에서는 그러한 파이프라인 플러시를 방지하기 위해 하중-대기열 검색 하드웨어에 데이터 비교를 추가해야 한다.
RAW 종속성 위반 방지
부하 및 저장소의 비순차 실행을 완전히 지원하는 CPU는 발생 시 RAW 의존성 위반을 감지할 수 있어야 한다.그러나 많은 CPU는 모든 로드와 저장소를 순서대로 실행하도록 강제하거나 제한된 형태의 로드/스토어 실행만 지원함으로써 이 문제를 회피한다.이 접근방식은 완전히 고장난 로드/스토어 실행을 지원하는 것에 비해 성능이 낮지만, 실행 코어 및 캐시의 복잡성을 현저하게 줄일 수 있다.
첫 번째 옵션인 로드와 스토어가 순서대로 정렬되도록 하는 것은 생산자 스토어 이전에 로드가 실행되어 잘못된 데이터를 얻을 가능성이 없기 때문에 RAW 의존성을 피한다.또 다른 가능성은 부하와 저장소를 주소 생성과 캐시 액세스의 두 가지 작업으로 효과적으로 세분화하는 것이다.이 두 개의 개별적이지만 연결된 작업을 통해 CPU는 이전의 모든 로드와 저장소가 LSQ에서 주소를 생성하고 버퍼링한 후에만 로드와 저장소가 메모리 시스템에 액세스할 수 있도록 할 수 있다.주소 생성 후에는 모든 주소가 알려져 있기 때문에 더 이상 모호한 종속성이 없으므로 해당 스토어가 완료될 때까지 종속 로드가 실행되지 않는다.이 계획은 여전히 일부 "순서가 맞지 않음"을 허용한다. 즉, 비행 중인 모든 부하와 저장소에 대한 주소 생성 작업은 순서가 맞지 않는 작업을 실행할 수 있으며, 일단 주소가 생성되면 각 부하 또는 저장소에 대한 캐시 액세스는 (현재 알려진) 진정한 종속성을 존중하는 어떤 순서로든 발생할 수 있다.
추가 문제
메모리 의존성 예측
고장난 로드/스토어 실행을 완전히 지원하는 프로세서는 메모리 의존성 예측이라고 불리는 추가적인 관련 기술을 사용하여 주소가 알려지기 전에 부하와 스토어 사이의 진정한 종속성을 예측할 수 있다.이 기술을 사용하면 프로세서가 기내 스토어에 종속될 것으로 예상되는 로드가 해당 스토어가 완료되기 전에 실행되지 않도록 방지하여 RAW 종속성 위반을 방지하고 따라서 발생하는 파이프라인 플러시 및 성능 저하를 방지할 수 있다.자세한 내용은 메모리 의존성 예측 문서를 참조하십시오.
