분기 예측 변수

Branch predictor
분기 지정과 혼동하지 마십시오.

컴퓨터 아키텍처에서 분기 예측기(branch[1][2][3][4][5] predictor)는 분기(if-then-else structure)가 최종적으로 알려지기 전에 어느 방향으로 갈 것인지를 추측하는 디지털 회로입니다.분기 예측 변수의 목적은 명령 파이프라인의 흐름을 개선하는 것입니다.분기 예측 변수는 x86과 같은 많은 최신 파이프라인 마이크로프로세서 아키텍처에서 고성능을 달성하는 데 중요한 역할을 합니다.

4단계 파이프라인의 예.색칠된 상자는 서로 독립적인 지침을 나타냅니다.

쌍방향 분기는 보통 조건부 점프 명령과 함께 구현된다.조건부 점프는 프로그램 메모리의 다른 위치로 "점프"하여 점프할 수도 있고, "점프" 후 즉시 실행을 계속할 수도 있습니다.조건이 계산되고 조건부 점프가 명령 파이프라인의 실행 단계를 통과할 때까지 조건부 점프가 수행될지 여부는 확실히 알려져 있지 않다(그림 1 참조).

분기 예측이 없으면 프로세서는 조건부 점프 명령이 실행 단계를 통과할 때까지 기다려야 다음 명령이 파이프라인의 가져오기 단계에 들어갈 수 있습니다.브랜치 프레딕터는 조건부 점프가 실행될 가능성이 가장 높은지 여부를 추측함으로써 이러한 시간 낭비를 회피하려고 합니다.다음으로 가장 가능성이 높다고 생각되는 브런치를 가져와 추측적으로 실행합니다.추정이 잘못된 것이 나중에 검출되면 추측적으로 실행되거나 부분적으로 실행된 명령이 폐기되고 파이프라인이 올바른 분기로 다시 시작되므로 지연이 발생합니다.

브랜치가 잘못 판단된 경우 낭비되는 시간은 가져오기 단계부터 실행 단계까지의 파이프라인의 단계 수와 동일합니다.최신 마이크로프로세서는 파이프라인이 상당히 긴 경향이 있기 때문에 오배정 지연은 10~20클럭 사이클입니다.따라서 파이프라인을 더 길게 만들면 고급 분기 [6]예측 변수의 필요성이 증가합니다.

조건부 점프 명령이 처음 발견되었을 때, 예측의 기초가 되는 정보가 많지 않습니다.그러나 분기 예측 변수는 분기를 가져갔는지 여부를 기록합니다.이전에 여러 번 보였던 조건부 점프를 만났을 때, 그것은 이력을 바탕으로 예측을 할 수 있다.예를 들어 분기 예측 변수는 조건부 점프가 자주 수행되거나 매초 수행된다는 것을 인식할 수 있습니다.

분기 예측이 분기 대상 예측과 같지 않습니다.분기 예측은 조건부 점프를 수행할지 여부를 추측하려고 시도합니다.분기 목표 예측은 명령 자체를 디코딩하고 실행함으로써 계산되기 전에 취해진 조건부 또는 무조건적인 점프의 목표를 추측하려고 시도합니다.브랜치 예측과 브랜치타깃 예측은 많은 경우 같은 회로에 결합됩니다.

실행

정적 분기 예측

정적 예측은 코드 실행의 동적 이력에 대한 정보에 의존하지 않기 때문에 가장 간단한 분기 예측 기법입니다.대신 분기 [7]명령만을 기반으로 분기의 결과를 예측합니다.

SPARC 및 MIPS(최초의 상용 RISC 아키텍처의 2개)의 초기 실장에서는 단방향 스태틱브런치 예측이 사용되었습니다.이러한 예측은 항상 조건부 점프가 이루어지지 않을 것으로 예측되기 때문에 항상 다음 시퀀셜명령어를 가져옵니다.분기 또는 점프가 평가되고 취해진 것으로 판명된 경우에만 명령 포인터가 비순차 주소로 설정됩니다.

모두들은 CPU와 단일 순환 지시 전달인지 가지고 있는decode 무대에 지점을 평가한다.결과적으로, 표적 재발 2사이클 정도 되는 분량은 기계가 항상 어떠한 찍은 가지 직후 명령을 가지고 있다.이들fetched 지침을 활용할 두 아키텍처들 가지 지연 슬롯을 정의한다.

정적의 예상 보다 향상된 형태가 낙후된 나뭇가지와 그 전방 가지 않을 거야 취할 것으로 보고 있다.한 낙후된 줄기 하나는 자신의 주소보다다 낮은 표적 주소를 가지고 있다.이 기술은 보통 가지 backward-pointing은 루프, 예측 정확도로, 그리고 자주 만나지 않지 않은 도울 수 있다.

어떤 프로세서 분기 예측 힌트를 코드로 이 정적 예측 또는지 않은 될 삽입할 수 있도록 한다.그 인텔 펜티엄 4로는 나눠지지만 이 기능을 나중에 인텔 프로세서에 방치돼 분기 예측한 조언을 받아들인다.[8]

정적 예측 기술만큼 역동적인 분기 예측과 함께 동적이 향상 충분한 정보를 사용해야 하지 않은 일부 프로세서에서 사용된다.한 fall-back로 모두 모토로라 MPC7450(G4e)과 인텔 펜티엄 4사용 기술입니다.[9]

정적 예측에서, 모든 결정은 컴파일 시간에, 이 프로그램의 실행하기 전에 만들어진다.[10]

동적 분기 예측

동적 가지 prediction[2]또는지 않은 가지 런타임에서 나뭇가지의 결과를 예측하기 위해 모였다에 대한 정보를 사용한다.[1]

랜덤 분기 예측

무작위로 또는pseudorandom 비트(순수한 추측)를 사용하여 모든 분야는(또는 악화되었다)가 저장되어 있는 순서 지시하고 있다.(" 걸리다"의 가장 단순한 정적 예측으로 컴파일러는 것보다 50%정확한 예측을 얻기 위해 지침을 선택할 수 있다.)이 개선될 수 없는 50%정확한 예측률을 보장할 것이다.또한, 타이밍[훨씬 더 많은]비결 정적임이 될 것이다.

다음 줄 예측

몇몇 슈퍼 스칼라 processors)그 다음 대사에게 지시 사항의 있는 지시봉으로 각 선에 팔리(MIPSR8000, 알파 21264,와 알파 21464(EV8).이 next-line 예언자라고 가지 표적 예측뿐만 아니라 지점 방향 예측 작업을 처리합니다.

다음 줄 프레딕터가 2, 4, 또는8 명령으로 정렬된 그룹을 가리킬 경우 브랜치타깃은 보통 첫 번째 Import된 명령이 아니기 때문에 Import된 초기 명령어는 낭비됩니다.단순화를 전제로 하면 가져온 브랜치타깃의 균일한 분포, 0.5, 1.5 및 3.5 명령은 각각 폐기됩니다.

브랜치 자체는 일반적으로 정렬된 그룹의 마지막 명령이 아니기 때문에 취득된 브랜치(또는 그 지연 슬롯) 이후의 명령은 폐기됩니다.다시 한 번 브랜치명령어 배치의 균일한 분포를 가정하면 Import된 0.5, 1.5 및 3.5 명령은 폐기됩니다.

브랜치 회선 및 행선지 회선에서의 폐기 명령은, 단일 사이클의 넥스트 라인 프레딕터에서도, 거의 완전한 페치 사이클이 됩니다.

일레벨 분기 예측

포화 계수기

1비트 포화 카운터(기본적으로 플립 플랍)는 브랜치의 마지막 결과를 기록합니다.이것은 매우 정확하지는 않지만 가능한 가장 단순한 버전의 동적 분기 프레딕터입니다.

2비트 포화[11] 카운터는 4가지 상태를 가진 스테이트 머신입니다.

그림 2: 2비트 포화 카운터 상태도
  • 강하지 않다
  • 약하게 복용하지 않음
  • 약하게 복용하다
  • 강렬하게 받아들이다

브런치를 평가하면, 대응하는 스테이트 머신이 됩니다.미취득으로 평가된 브랜치는 상태가 강하게 미취득으로 바뀌고, 착취로 평가된 브랜치는 상태가 강하게 표시됩니다.2비트 카운터 스킴이 1비트 스킴보다 좋은 점은 예측이 변경되기 전에 조건부 점프가 과거에 가장 많이 했던 것과 2배 이상 차이가 날 필요가 있다는 것입니다.예를 들어 루프 클로징 조건부 점프는 두 번이 아니라 한 번 잘못 예측됩니다.

MMX 이외의 인텔 Pentium 프로세서는 불완전한 [8]구현이지만 포화 카운터를 사용합니다.

SPEC의 89 벤치마크에서는 대형 바이모달 예측 변수가 93.5%의 정확도로 포화되며, 각 [12]: 3 지점이 고유한 카운터에 매핑됩니다.

프로세서가 명령을 디코딩하기 전에 모든 명령에 대한 예측을 가져올 수 있도록 프레딕터 테이블이 명령 주소 비트로 인덱싱됩니다.

2-수준 예측 변수

2레벨 분기 프레딕터(상관 기반 분기 프레딕터라고도 함)는 2차원 카운터 테이블('패턴 이력 테이블'이라고도 함)을 사용합니다.테이블 엔트리는 2비트카운터입니다

2-레벨 적응 예측 변수

그림 3: 2레벨 적응형 분기 프레딕터패턴 이력 테이블의 각 엔트리는 그림 [13]2에 나타낸 타입의 2비트 포화 카운터를 나타냅니다.

이 경우,if스테이트먼트는 3회 실행되며, 3회 실행의 결정은 앞의 2회 실행 여부에 따라 달라질 수 있습니다.이러한 시나리오에서는 2-수준 적응형 예측 변수가 포화 계수기보다 더 효율적으로 작동합니다.2초마다 반복되거나 다른 주기적으로 반복되는 조건부 점프는 포화 카운터에 의해 잘 예측되지 않는다.2레벨 적응 프레딕터는 브랜치의 마지막 n개의 발생 이력을 기억하고 가능한n 2개의 이력 패턴 각각에 대해 하나의 포화 카운터를 사용한다.이 방법은 그림 3에 설명되어 있습니다.

n = 2의 예를 생각해 보십시오.이는 브랜치의 마지막 두 항목이 2비트 시프트 레지스터에 저장됨을 의미합니다.이 분기 기록 레지스터에는 00, 01, 10, 11의 네 가지 다른 이진수 값이 있을 수 있습니다. 여기서 0은 "사용하지 않음"을 의미하며, 하나는 "사용됨"을 의미합니다.패턴 이력 테이블에는 분기당 4개의 엔트리가 포함되어 있으며, 각 엔트리는 분기별로2 그림 2와 같은 유형의 2비트 포화 카운터가 포함되어 있습니다.분기 이력 레지스터는 4개의 포화 카운터 중 사용할 카운터를 선택하기 위해 사용됩니다.이력이 00인 경우 첫 번째 카운터가 사용되며 이력이 11인 경우 4개의 카운터 중 마지막 카운터가 사용됩니다.

예를 들어 조건부 점프가 3회마다 실시된다고 가정합니다.브랜치 시퀀스는 001001001...이 경우 패턴 이력 테이블의 엔트리 번호00은 "strongly taken" 상태가 됩니다.이는 2개의 0 뒤에1이 오는 것을 나타냅니다.엔트리 번호 01은 "strongly not taken" 상태가 됩니다.이는 01 뒤에 0이 있음을 나타냅니다.엔트리 번호 10도 마찬가지이지만 엔트리 번호 11은 연속되는2개가 없기 때문에 사용되지 않습니다.

n비트 이력을 가진 2레벨 적응형 프레딕터의 일반적인 규칙은 모든 n비트 서브시퀀스가 다른 [8]경우 임의의 주기로 반복 시퀀스를 예측할 수 있다는 것입니다.

2-수준 적응형 예측 변수의 장점은 임의 반복 패턴을 예측하는 방법을 빠르게 배울 수 있다는 것입니다.이 방법은 T-Y에 의해 발명되었다.미시건 [14]대학의 Yeh와 Yale Patt.1991년에 처음 출판된 이래, 이 방법은 매우 인기를 끌고 있다.이 예측 방법의 변형은 대부분의 최신 [citation needed]마이크로프로세서에 사용됩니다.

2-레벨 신경 예측 변수

두 번째 레벨이 뉴럴 네트워크로 대체되는 2-레벨 분기 예측 변수가 [15]제안되었다.

로컬 브랜치 예측

로컬 분기 프레딕터는 조건부 점프 명령별로 별도의 이력 버퍼를 가진다.2-수준 적응형 예측 변수를 사용할 수 있습니다.이력 버퍼는 각 조건부 점프 명령에 대해 분리되며, 패턴 이력 테이블도 분리되거나 모든 조건부 점프 간에 공유될 수 있다.

인텔 Pentium MMX, Pentium II 및 Pentium III에는 로컬 4비트 이력을 가진 로컬 브랜치 프레딕터와 로컬 패턴 이력 테이블이 있으며 각 조건부 점프마다 16개의 엔트리가 있습니다.

SPEC의 89 벤치마크에서는 매우 큰 로컬 예측 변수가 [12]: 6 97.1%로 포화됩니다.

글로벌 브랜치 예측

글로벌 분기 프레딕터는 조건부 점프마다 개별 이력 레코드를 보유하지 않습니다.대신 모든 조건부 점프의 이력을 공유한다.공통 이력의 장점은 서로 다른 조건부 점프 간의 상관관계가 예측의 일부라는 것이다.단점은 서로 다른 조건부 점프가 상관관계가 없는 경우 관련 없는 정보에 의해 이력이 희석되고 그 사이에 다른 브랜치가 다수 있는 경우 이력 버퍼에 같은 브랜치의 비트가 포함되지 않을 수 있다는 것입니다.2-수준 적응형 예측 변수를 사용할 수 있습니다.

이 방식은 테이블 크기가 큰 경우에만 포화 카운터 방식보다 우수하며 로컬 예측만큼 좋은 경우는 거의 없습니다.올바르게 예측하려면 이력 버퍼가 더 길어야 합니다.패턴 이력 테이블의 크기는 이력 버퍼의 크기에 따라 기하급수적으로 증가합니다.따라서 모든 조건부 점프에서 빅 패턴 기록 표를 공유해야 한다.

글로벌하게 공유된 이력 버퍼와 패턴 이력 테이블을 가진 2레벨 적응형 프레딕터는 글로벌 이력 및 브랜치 PC를 확장하면 "gshare" 프레딕터라고 불리며 이들을 연결하면 "gselect"라고 불립니다.글로벌 브랜치 예측은 AMD 프로세서 및 인텔 Pentium M, Core, Core 2, Silvermont 기반 ATOM 프로세서에서 사용됩니다.

합금 분기 예측

합금 분기[16] 프레딕터는 로컬 및 글로벌 분기 이력을 프로그램카운터의 일부 비트와 연결함으로써 로컬 및 글로벌 예측 원리를 결합합니다.테스트 결과 VIA Nano 프로세서가 이 [8]기술을 사용하고 있는 것으로 나타났습니다.

예측 변수 동의

합의 프레딕터는 글로벌하게 공유된 이력 버퍼 및 패턴 이력 테이블과 추가 로컬 포화 카운터를 가진 2레벨 적응 프레딕터입니다.로컬 및 글로벌 예측 변수의 출력을 서로 XOR하여 최종 예측을 제공합니다.그 목적은 예측이 반대인2개의 브런치가 패턴 이력 [17]테이블에서 같은 엔트리를 공유하는 패턴 이력 테이블 내의 경합을 줄이는 것입니다.

하이브리드 예측 변수

복합 예측 변수라고도 하는 하이브리드 예측 변수는 둘 이상의 예측 메커니즘을 구현합니다.최종 예측은 과거에 어떤 예측 변수가 가장 잘 예측했는지 기억하는 메타 예측 변수를 기반으로 하거나 홀수 개수의 다른 예측 변수를 기반으로 하는 다수결 함수를 기반으로 합니다.

Scott McFarling은 1993년 [12]논문에서 복합 분기 예측을 제안했다.

SPEC의 89 벤치마크에서 이러한 예측 변수는 로컬 예측 [citation needed]변수와 거의 같습니다.

gshare 등의 예측 변수는 여러 테이블엔트리를 사용하여 특정 브랜치의 동작을 추적합니다.이 엔트리의 곱셈에 의해 2개의 브런치가 같은 테이블엔트리에 매핑될 가능성이 높아지고(에일리어싱이라고 불리는 상황), 그 브런치에서는 예측의 정확도가 저하될 가능성이 높아집니다.예측 변수가 여러 개 있는 경우 각 예측 변수의 별칭 패턴이 다르도록 배열하는 것이 좋습니다. 그래야 하나 이상의 예측 변수가 별칭을 가지지 않을 가능성이 높아집니다.서로 다른 예측 변수에 대해 서로 다른 색인 함수를 가진 결합된 예측 변수를 gskew 예측 변수라고 하며, 데이터 및 명령 캐시에 사용되는 왜곡된 연관 캐시와 유사합니다.

루프 프레딕터

루프를 제어하는 조건부 점프는 특별한 루프 프레딕터를 사용하여 예측하는 것이 가장 좋습니다.루프의 바닥에서 N회 반복되는 조건부 점프는 N-1회 반복되며 한 번 반복되지 않는다.조건부 점프를 루프 상단에 배치하면, N-1회 시도하지 않고 1회 시도한다.한 방향으로 여러 번 이동한 후 다른 방향으로 한 번 이동한 조건부 점프는 루프 동작을 갖는 것으로 검출됩니다.이러한 조건부 점프는 간단한 카운터로 쉽게 예측할 수 있다.루프 프레딕터는 메타 프레딕터가 조건부 점프에 루프 동작이 있는지 여부를 검출하는 하이브리드 프레딕터의 일부입니다.

간접 분기 예측 변수

간접 점프 명령은 3개 이상의 분기 중에서 선택할 수 있다.일부 프로세서에는 특수 간접 분기 예측 [18][19]변수가 있습니다.인텔과[21] AMD의 최신[20] 프로세서는 2레벨의 적응형 프레딕터를 사용하여 간접 브랜치를 예측할 수 있습니다.이런 종류의 명령은 이력 버퍼에 여러 비트를 기여합니다.IBM의 zEC12 이상 z/Architecture 프로세서는 다음을 지원합니다.범용 레지스터의 내용을 즉시 변위 [22][23]값에 추가하여 구성된 분기 대상 주소로 주어진 명령에 대한 분기 예측기 엔트리를 프리로드할 수 있는 BRANCH PRESIDION PRELOAD 명령.

이 메커니즘이 없는 프로세서는 지난 [8]번과 같은 타겟으로 가는 간접적인 점프를 예측합니다.

함수 리턴 예측

일반적으로 함수는 호출된 위치로 돌아갑니다.리턴 명령은 콜 스택에서 타깃주소를 읽는 간접 점프입니다.많은 마이크로프로세서에는 반환 명령을 위한 별도의 예측 메커니즘이 있습니다.이 메커니즘은 콜 스택의 로컬미러인 이른바 리턴 스택버퍼에 기초하고 있습니다리턴 스택버퍼의 크기는 보통 [8]4 ~16 엔트리입니다

분기 예측을 재정의하는 중

고속 분기 예측과 양호한 분기 예측 간의 트레이드오프는 두 개의 분기 예측 변수를 갖는 것으로 처리되기도 합니다.첫 번째 분기 예측 변수는 빠르고 간단합니다.두 번째 분기 예측 변수는 더 느리고 복잡하며 테이블이 더 크므로 첫 번째 예측 변수가 잘못된 예측을 재정의할 수 있습니다.

Alpha 21264 및 Alpha EV8 마이크로프로세서는 고속 단일 사이클 넥스트 라인 프레딕터를 사용하여 분기 목표의 재발을 처리하고 단순하고 빠른 분기 예측을 제공합니다.다음 라인 프레딕터는 매우 부정확하고 분기 분해능 반복에 시간이 오래 걸리기 때문에 두 코어 모두 2사이클의 세컨더리 브랜치 프레딕터를 사용하여 단일 페치 사이클 손실의 비용으로 다음 라인 프레딕터의 예측을 덮어쓸 수 있습니다.

인텔 Core i7에는 2개의 분기 타깃 버퍼와 2개 이상의 분기 [24]프레딕터가 있습니다.

신경가지 예측

LVQ와 다층 퍼셉트론을 이용한 분기 예측을 위한 기계 학습, "신경 분기 예측"은 루시안 빈탄(Lucian Blaga University of Sibiu)[25]에 의해 제안되었다.1년 후 그는 퍼셉트론 분기 [26]예측기를 개발했다.신경지 예측 연구는 대니얼 [27]히메네즈에 의해 훨씬 더 많이 개발되었습니다.2001년에 [27]하드웨어에서 구현 가능한 최초의 퍼셉트론 예측기가 제시되었다.퍼셉트론 브랜치 프레딕터를 최초로 상용화한 것은 AMD의 Floodedriver 마이크로아키텍처였습니다.[28]

신경 예측기의 주요 장점은 선형 자원 증가만 요구하면서 긴 이력을 활용할 수 있는 능력이다.기존 예측 변수에는 기하급수적인 리소스 증가가 필요합니다.Jimenez는 McFarling 스타일의 하이브리드 [29]예측 변수보다 5.7% 향상된 글로벌 성능을 보고했습니다.또한 하이브리드 예측 [29]변수를 우선하는 gshare/perceptron을 사용했습니다.

퍼셉트론 프레딕터의 주요 단점은 지연 시간이 길다는 것입니다.고속 산술 기술을 이용한 후에도 많은 현대 마이크로아키텍처의 클럭 주기에 비해 계산 지연 시간이 상대적으로 높습니다.예측 대기 시간을 줄이기 위해 히메네즈는 2003년에 퍼셉트론 예측기가 지점의 PC가 아닌 현재 지점의 경로에 따라 체중을 선택하는 고속 경로 신경 예측기를 제안했다.많은 다른 연구자들이 이 개념을 개발했다(A. Seznec, M. Monchiero, D).Tarjan & K.Skadron, V. Desmet, Akkary et al., K. Aasaraai,[citation needed] Michael Black 등)

대부분의 최첨단 브랜치 프레딕터는 퍼셉트론 프레딕터를 사용하고 있습니다(인텔의 "챔피언십 브랜치 프레딕터"[30] 참조).인텔은 이미 IA-64의 시뮬레이터 중 하나(2003)[31]에 이 아이디어를 실장하고 있습니다.

AMD[32][33][34] Ryzen 멀티코어 프로세서의 Infinity Fabric과 Samsung Exynos 프로세서에는 퍼셉트론 기반의 신경 분기 예측기가 포함되어 있습니다.

역사

1950년대 후반에 설계된 IBM 7030 Stretch는 모든 무조건 브랜치 및 인덱스 레지스터에 의존하는 조건부 브랜치를 사전에 실행합니다.다른 조건부 브랜치의 경우, 구현된 처음 두 생산 모델은 파악되지 않은 예측을 했습니다. 후속 모델은 (오늘날의 조건 [35]코드에 해당하는) 인디케이터 비트의 현재 값을 기반으로 예측을 구현하도록 변경되었습니다.Stretch 설계자는 프로젝트 초기에 분기 명령의 정적 힌트 비트를 고려했지만 이를 거부했습니다.잘못된 예측 복구는 Stretch의 예측 장치에 의해 제공되었으며, Stretch의 성능이 별보다 낮다는 평판 중 일부는 잘못된 예측 복구에 필요한 시간 때문이라고 합니다.이후의 IBM 대형 컴퓨터 설계에서는 1985년 IBM 3090까지 분기 예측을 사용하지 않았습니다.

2비트 예측 변수는 1977년 Tom McWilliams와 Curt Widdos에 의해 Lawrence Livermore National Lab S-1 슈퍼컴퓨터에 도입되었으며 1979년 [36]CDC에서 Jim Smith에 의해 독립적으로 도입되었습니다.

1960년대부터 1980년대까지 널리 보급된 마이크로프로그래밍 프로세서는 명령당 여러 사이클이 소요되어 일반적으로 분기 예측을 필요로 하지 않았습니다.그러나 IBM 3090 외에도 분기 예측을 통합한 마이크로 프로그래밍 설계의 다른 몇 가지 예가 있습니다.

1982년경에 출시된 마이크로프로그래밍된 COBOL 기계인 Burroughs B4900은 파이프라인 방식으로 분기 예측을 사용했다.B4900 분기 예측 이력 상태는 프로그램 실행 중 메모리 내 명령에 다시 저장됩니다.B4900은 각 분기 연산자 유형을 나타내기 위해 4개의 의미상 등가 분기 연산 코드를 사용하여 4개의 상태 분기 예측을 구현합니다.사용된 opcode는 특정 분기 명령의 이력을 나타냅니다.하드웨어는 특정 브랜치의 브랜치 예측 상태를 갱신할 필요가 있다고 판단했을 경우 적절한 이력을 시사한 의미상 동등한 opcode로 opcode를 고쳐 씁니다.이 방식은 93%의 적중률을 얻습니다.미국 특허 4,435,756 및 기타 특허가 이 제도에 대해 부여되었습니다.

그 백스 9000,1989년에 발표되고, 파이프 라인, 분기 예측을 수행합니다microprogrammed 있다.[37]

첫번째 상업상의 RISC 프로세서, MIPSR2000과 R3000서 좀 더 일찍 스팍 프로세서만 사소한"not-taken"분기 예측 한다.왜냐하면 그들은 가지 지연 슬롯을 사용한다, 주기고,in-order 실행, 어떠한 공연도 손실은 단지 하나의 명령에 낙찰됐습니다.그 뒤의 R4000고, 그 나뭇가지 해상도 재발은 4사이클 시간 찍은 지점으로 두 사이클에 진 같은 사소한"not-taken"분기 예측을 사용한다.

분기 예측을 보다 인텔 펜티엄, DEC알파 21064, MIPSR8000, 그리고 IBM파워 시리즈를 파이프 라인 슈퍼 스칼라 프로세서의 도입으로 중요하게 되었다.이러한 프로세서 모두 또는 간단한 작은 바이모달이 향상에 의존한다.

그 알파 프로세서 21264(EV6)는next-line 예측이 결합하는 선택은 바이모달 예측이 만든 연합 지역 예측과 지구 대해 예측자 역할을 재정의를 사용한다.[38]

그 AMDK8이 결합하는 선택은 다른 두가지 시스템이 있는 예언자가 결합된 세계 두가지 시스템이 있는 예측자 역할을 하고 있다.이 프로세서는 L2캐시 달리 ECC에 사용되는 비트에서 기본과 선택 두가지 시스템이 있는 예언자라고 카운터 캐시 합니다.결과적으로, ECC보다는에 있는 L2캐시에 효과적으로 매우 큰 기지와 선택 예언자라고 탁자, 패리팄다.이후 어느 명령 패리티 오류 고통, 그리고 기억에서 refetched 무효화될 수 있는 패리티 디자인, 충분하다.

알파 21464[38](EV8, 설계 시 나중에 취소)14주기의 최소 가지 misprediction 처벌 했다.그것은 하지만 빠른 복잡한next-line 예언자라고는 혼합majority-voting 두가지 시스템이 있는 예언자에 의해 재정의될 때 사용하는 것이었다.대다수 투표는 이정과 두 gskew을 예측 변수 사이에 있었다.

2018년에서 파국적인 보안 취약성 스펙 트레라고 불리는 공공 구글의 프로젝트 0그리고 다른 연구원들에 의해 만들어졌다.사실상 모든 현대 CPU에게 영향을 미치며, 취약점을 가지 mispredictions의 남은 데이터 캐시에서 개인 데이터를 추출을 포함한다.[39]

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Malishevsky, Alexey; Beck, Douglas; Schmid, Andreas; Landry, Eric. "Dynamic Branch Prediction". Archived from the original on 2019-07-17. Retrieved 2017-03-22.
  2. ^ a b Cheng, Chih-Cheng. "The Schemes and Performances of Dynamic Branch predictors" (PDF).
  3. ^ Parihar, Raj. "Branch Prediction Techniques and Optimizations" (PDF). Archived from the original (PDF) on 2017-05-16. Retrieved 2017-04-02.
  4. ^ Mutlu, Onur (2013-02-11). "18-447 Computer Architecture Lecture 11: Branch Prediction" (PDF).
  5. ^ Michaud, Pierre; Seznec, André; Uhlig, Richard (September 1996). "Skewed branch predictors". S2CID 3712157. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  6. ^ Eyerman, S.; Smith, J.E.; Eeckhout, L. (2006). "Characterizing the branch misprediction penalty". 2006 IEEE International Symposium on Performance Analysis of Systems and Software. IEEE: 48–58. doi:10.1109/ispass.2006.1620789. ISBN 1-4244-0186-0. S2CID 72217.
  7. ^ Shen, John P.; Lipasti, Mikko (2005). Modern processor design: fundamentals of superscalar processors. Boston: McGraw-Hill Higher Education. pp. 455. ISBN 0-07-057064-7.
  8. ^ a b c d e f Fog, Agner (2016-12-01). "The microarchitecture of Intel, AMD, and VIA CPUs" (PDF). p. 36. Retrieved 2017-03-22.
  9. ^ Pentium 4와 G4e: 아키텍처 비교, Ars Technica
  10. ^ Plusquellic, Jim. "CMSC 611: Advanced Computer Architecture, Chapter 4 (Part V)".
  11. ^ "Dynamic Branch Prediction". web.engr.oregonstate.edu. Archived from the original on 2019-07-17. Retrieved 2017-11-01.
  12. ^ a b c McFarling, Scott (June 1993). "Combining Branch Predictors" (PDF). Digital Western Research Lab (WRL) Technical Report, TN-36.
  13. ^ "New Algorithm Improves Branch Prediction: 3/27/95" (PDF). Carnegie Mellon University. Retrieved 2016-02-02.
  14. ^ Yeh, T.-Y.; Patt, Y. N. (1991). "Two-Level Adaptive Training Branch Prediction". Proceedings of the 24th annual international symposium on Microarchitecture. Albuquerque, New Mexico, Puerto Rico: ACM. pp. 51–61.
  15. ^ Egan, Colin; Steven, Gordon; Quick, P.; Anguera, R.; Vintan, Lucian (December 2003). "Two-Level Branch Prediction using Neural Networks". Journal of Systems Architecture. 49 (12–15): 557–570. doi:10.1016/S1383-7621(03)00095-X.
  16. ^ Skadron, K.; Martonosi, M.; Clark, D. W. (October 2000). "A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions". Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Philadelphia.
  17. ^ Sprangle, E.; et al. (June 1997). "The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference". Proceedings of the 24th International Symposium on Computer Architecture. Denver.
  18. ^ "Cortex-A15 MPCore Technical Reference Manual, section 6.5.3 "Indirect predictor"". ARM Holdings.
  19. ^ Driesen, Karel; Hölzle, Urs (1997-06-25). "Limits of Indirect Branch Prediction" (PDF).
  20. ^ Stokes, Jon (2004-02-25). "A Look at Centrino's Core: The Pentium M". pp. 2–3.
  21. ^ Kanter, Aaron (2008-10-28). "Performance Analysis for Core 2 and K8: Part 1". p. 5.
  22. ^ "z/Architecture Principles of Operation" (PDF). IBM. March 2015. pp. 7–40, 7–43. SA22-7832-10.
  23. ^ "IBM zEnterprise BC12 Technical Guide" (PDF). IBM. February 2014. p. 78.
  24. ^ WO 2000/014628, Yeh, Tse-Yu & Sharangpani, H. P., "2단계 분기예측표를 이용한 분기예측방법 및 장치", 2000-03-16 발행
  25. ^ Vintan, Lucian N. (1999). Towards a High Performance Neural Branch Predictor (PDF). Proceedings International Journal Conference on Neural Networks (IJCNN). Archived from the original (PDF) on 2019-07-13. Retrieved 2010-12-02.
  26. ^ Vintan, Lucian N. (2000). "Towards a Powerful Dynamic Branch Predictor" (PDF). Romanian Journal of Information Science and Technology. Bucharest: Romanian Academy. 3 (3): 287–301. ISSN 1453-8245.
  27. ^ a b Jimenez, D. A.; Lin, C. (2001). Dynamic Branch Prediction with Perceptrons. Proceedings of the 7-th International Symposium on High Performance Computer Architecture (HPCA-7). Monterrey, NL, Mexico. pp. 197–296.
  28. ^ Walton, Jarred (2012-05-15). "The AMD Trinity Review (A10-4600M): A New Hope". AnandTech.
  29. ^ a b Jimenez, Daniel A. (December 2003). Fast Path-Based Neural Branch Prediction (PDF). The 36th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-36). San Diego, USA. Retrieved 2018-04-08.
  30. ^ "Championship Branch Prediction".
  31. ^ Brekelbaum, Edward; Rupley, Jeff; Wilkerson, Chris; Black, Bryan (December 2002). Hierarchical scheduling windows. Proceedings of the 34th International Symposium on Microarchitecture. Istanbul, Turkey.
  32. ^ James, Dave (2017-12-06). "AMD Ryzen reviews, news, performance, pricing, and availability". PCGamesN.
  33. ^ "AMD Takes Computing to a New Horizon with Ryzen™ Processors". www.amd.com. Retrieved 2016-12-14.
  34. ^ "AMD's Zen CPU is now called Ryzen, and it might actually challenge Intel". Ars Technica UK. Retrieved 2016-12-14.
  35. ^ IBM Stretch(7030) -- 어그레시브 유니프로세서 병렬화
  36. ^ S-1 슈퍼컴퓨터
  37. ^ VAX 9000의 마이크로 아키텍처
  38. ^ a b 세즈넥, 펠릭스, 크리슈난, 사제이데스Alpha EV8 조건부 분기 예측 변수의 설계 트레이드오프
  39. ^ Gibbs, Samuel (2018-01-04). "Meltdown and Spectre: 'worst ever' CPU bugs affect virtually all computers". the Guardian. Retrieved 2018-05-18.

외부 링크