맨위로가기

분기 예측

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

분기 예측은 CPU가 프로그램의 흐름을 예측하여 성능을 향상시키는 기술이다. == 역사 == IBM 7030 스트레치에서 처음 사용되었으며, 2비트 예측기, 2단계 적응형 예측기, 신경망 예측기 등 다양한 형태로 발전해 왔다. 또한, 지역, 전역, 결합 예측 등 다양한 예측 방식이 존재하며, 루프와 간접 분기, 함수 반환을 위한 특수한 예측기도 사용된다. == 구현 == 정적 예측, 동적 예측, 결합 예측 등 다양한 구현 방식이 있으며, 최근에는 신경망 예측기가 널리 사용된다. == 보안 취약점 == 2018년에는 분기 예측기를 악용한 스펙터(Spectre)라는 보안 취약점이 발견되어, CPU의 보안에 대한 중요성이 더욱 강조되었다.

2. 역사

IBM 7030 스트레치(IBM 7030 Stretch)는 1950년대 후반에 설계되었으며, 무조건 분기 및 인덱스 레지스터에 의존하는 모든 조건 분기를 미리 실행했다.[34] 다른 조건 분기의 경우, 처음 두 개의 생산 모델은 예측을 수행하지 않도록 구현했지만, 이후 모델은 오늘날의 상태 코드에 해당하는 표시기 비트의 현재 값을 기반으로 예측을 구현하도록 변경되었다.[34] 스트레치 설계자들은 프로젝트 초기에 분기 명령어에 정적 힌트 비트를 고려했지만, 이를 채택하지 않기로 결정했다.[34] 잘못된 예측 복구는 스트레치의 룩어헤드 유닛에 의해 제공되었으며, 스트레치의 그다지 훌륭하지 않은 성능에 대한 명성은 잘못된 예측 복구에 소요되는 시간에 기인했다.[34] 이후 IBM의 대형 컴퓨터 설계에서는 1985년 IBM 3090(IBM 3090)까지 추측 실행을 사용한 분기 예측을 사용하지 않았다.[34][51]

2비트 예측기는 1977년 Tom McWilliams와 Curt Widdoes에 의해 로렌스 리버모어 국립 연구소 S-1 슈퍼컴퓨터용으로 도입되었으며, 1979년 Jim Smith에 의해 CDC에서 독립적으로 도입되었다.[35][52]

1960년대부터 1980년대까지, 그리고 그 이후까지 널리 사용되었던 마이크로 프로그램 방식 프로세서는 명령어당 여러 사이클을 소요했으며, 일반적으로 분기 예측을 필요로 하지 않았다. 그러나 IBM 3090(IBM 3090) 외에도 분기 예측을 통합한 몇 가지 다른 마이크로프로그래밍 설계의 예가 있다.[52]

1982년경에 출시된 마이크로프로그래밍된 COBOL 머신인 Burroughs B4900(Burroughs B4900)은 파이프라인 방식을 사용했으며 분기 예측을 사용했다. B4900의 분기 예측 기록 상태는 프로그램 실행 중에 메모리 내 명령어에 다시 저장된다. B4900은 각 분기 연산자 유형을 나타내기 위해 4개의 의미적으로 동일한 분기 연산 코드를 사용하여 4상태 분기 예측을 구현한다. 사용된 연산 코드는 해당 특정 분기 명령어의 기록을 나타낸다. 하드웨어가 특정 분기의 분기 예측 상태를 업데이트해야 한다고 판단하면, 올바른 기록을 힌트하는 의미적으로 동일한 연산 코드로 연산 코드를 다시 쓴다. 이 방식은 93%의 적중률을 얻는다.

1989년에 발표된 DEC VAX 9000(VAX 9000)은 마이크로프로그래밍 방식과 파이프라인 방식을 모두 사용하며 분기 예측을 수행한다.[36][53]

최초의 상업용 RISC 프로세서인 MIPS R2000 및 R3000과 초기 SPARC 프로세서는 사소한 "예측 안 함" 분기 예측만 수행한다. 분기 지연 슬롯을 사용하고, 사이클당 하나의 명령어만 가져오며, 순서대로 실행하기 때문에 성능 저하가 없다. 이후의 R4000은 동일한 사소한 "예측 안 함" 분기 예측을 사용하며, 분기 해결 재발이 4 사이클이기 때문에 각 분기마다 두 사이클을 잃는다.[53]

분기 예측은 인텔 펜티엄, DEC 알파 21064, MIPS R8000, IBM POWER 시리즈와 같은 파이프라인 슈퍼스칼라 프로세서의 도입과 함께 더욱 중요해졌다. 이러한 프로세서는 모두 1비트 또는 단순 바이모달 예측기에 의존한다.

DEC 알파 21264 (EV6)는 결합된 로컬 예측기 및 글로벌 예측기에 의해 무시되는 다음 라인 예측기를 사용하며, 결합 선택은 바이모달 예측기에 의해 이루어진다.[37][54]

AMD K8은 결합된 바이모달 및 글로벌 예측기를 가지고 있으며, 결합 선택은 또 다른 바이모달 예측기이다. 이 프로세서는 ECC에 사용되는 L2 캐시 비트에 기본 및 선택 바이모달 예측기 카운터를 캐싱한다. 결과적으로, 기본 및 선택 예측기 테이블이 매우 크며, L2 캐시의 명령어에 ECC가 아닌 패리티 비트가 있다. 패리티 설계는 충분하다. 패리티 오류가 발생하는 모든 명령어를 무효화하고 메모리에서 다시 가져올 수 있기 때문이다.

알파 21464 (EV8, 설계 후반에 취소됨)는 최소 14 사이클의 분기 예측 오류 페널티를 가졌다. 결합된 바이모달 및 다수결 투표 예측기에 의해 무시되는 복잡하지만 빠른 다음 라인 예측기를 사용할 예정이었습니다. 다수결 투표는 바이모달 및 두 개의 gskew 예측기 사이에서 이루어졌다.[37][54]

2018년에는 스펙터라고 불리는 치명적인 보안 취약점이 Google의 Project Zero 및 기타 연구원에 의해 공개되었다. 사실상 모든 최신 CPU에 영향을 미치는 이 취약점은 분기 예측기를 준비하여 다른 프로세스(또는 커널)가 분기를 잘못 예측하고 비밀 데이터를 배열 인덱스로 사용하여 공격자의 캐시 라인 중 하나를 제거하는 것을 포함한다. 공격자는 자신의 배열에 대한 액세스 시간을 측정하여 어느 배열인지 알아낼 수 있으며, 이를 통해 공격자가 직접 읽을 수 없었던 값에 대한 정보를 갖는 값을 저장할 수 있는 이 CPU 내부(마이크로아키텍처) 상태를 값으로 변환한다.[38]

역사적으로 파이프라인과 분기 예측은 마이크로 프로그램 방식의 CISC 프로세서에서 태어나 발전한 기술이며, RISC를 포함한 마이크로프로세서에서의 분기 예측은 처음에는 간단한 것이었다. "마이크로 프로그램 방식의 프로세서는 분기 예측을 필요로 하지 않았다"는 설이 있지만, 이는 잘못된 것이다. 일반적으로 RISC가 파이프라인의 효과를 발휘하기 쉽기 때문에(반대로 말하면 파이프라인이 흐트러지면 성능 저하가 크기 때문에), 결과적으로 분기 예측이 중요할 뿐이다.

2. 1. 초기 분기 예측

IBM 7030 스트레치(IBM 7030 Stretch)는 1950년대 후반에 설계되었으며, 무조건 분기 및 인덱스 레지스터에 의존하는 모든 조건 분기를 미리 실행했다.[34] 다른 조건 분기의 경우, 처음 두 개의 생산 모델은 예측을 수행하지 않도록 구현했지만, 이후 모델은 오늘날의 상태 코드에 해당하는 표시기 비트의 현재 값을 기반으로 예측을 구현하도록 변경되었다.[34] 스트레치 설계자들은 프로젝트 초기에 분기 명령어에 정적 힌트 비트를 고려했지만, 이를 채택하지 않기로 결정했다.[34] 잘못된 예측 복구는 스트레치의 룩어헤드 유닛에 의해 제공되었으며, 스트레치의 그다지 훌륭하지 않은 성능에 대한 명성은 잘못된 예측 복구에 소요되는 시간에 기인했다.[34] 이후 IBM의 대형 컴퓨터 설계에서는 1985년 IBM 3090(IBM 3090)까지 추측 실행을 사용한 분기 예측을 사용하지 않았다.[34][51]

2비트 예측기는 1977년 Tom McWilliams와 Curt Widdoes에 의해 로렌스 리버모어 국립 연구소 S-1 슈퍼컴퓨터용으로 도입되었으며, 1979년 Jim Smith에 의해 CDC에서 독립적으로 도입되었다.[35][52]

1960년대부터 1980년대까지, 그리고 그 이후까지 널리 사용되었던 마이크로 프로그램 방식 프로세서는 명령어당 여러 사이클을 소요했으며, 일반적으로 분기 예측을 필요로 하지 않았다. 그러나 IBM 3090(IBM 3090) 외에도 분기 예측을 통합한 몇 가지 다른 마이크로프로그래밍 설계의 예가 있다.[52]

1982년경에 출시된 마이크로프로그래밍된 COBOL 머신인 Burroughs B4900(Burroughs B4900)은 파이프라인 방식을 사용했으며 분기 예측을 사용했다. B4900의 분기 예측 기록 상태는 프로그램 실행 중에 메모리 내 명령어에 다시 저장된다. B4900은 각 분기 연산자 유형을 나타내기 위해 4개의 의미적으로 동일한 분기 연산 코드를 사용하여 4상태 분기 예측을 구현한다. 사용된 연산 코드는 해당 특정 분기 명령어의 기록을 나타낸다. 하드웨어가 특정 분기의 분기 예측 상태를 업데이트해야 한다고 판단하면, 올바른 기록을 힌트하는 의미적으로 동일한 연산 코드로 연산 코드를 다시 쓴다. 이 방식은 93%의 적중률을 얻는다.

1989년에 발표된 DEC VAX 9000(VAX 9000)은 마이크로프로그래밍 방식과 파이프라인 방식을 모두 사용하며 분기 예측을 수행한다.[36][53]

최초의 상업용 RISC 프로세서인 MIPS R2000 및 R3000과 초기 SPARC 프로세서는 사소한 "예측 안 함" 분기 예측만 수행한다. 분기 지연 슬롯을 사용하고, 사이클당 하나의 명령어만 가져오며, 순서대로 실행하기 때문에 성능 저하가 없다. 이후의 R4000은 동일한 사소한 "예측 안 함" 분기 예측을 사용하며, 분기 해결 재발이 4 사이클이기 때문에 각 분기마다 두 사이클을 잃는다.[53]

분기 예측은 인텔 펜티엄(Pentium), DEC 알파 21064(Alpha 21064), MIPS R8000, IBM POWER 시리즈와 같은 파이프라인 슈퍼스칼라 프로세서의 도입과 함께 더욱 중요해졌다. 이러한 프로세서는 모두 1비트 또는 단순 바이모달 예측기에 의존한다.

DEC 알파 21264(Alpha 21264) (EV6)는 결합된 로컬 예측기 및 글로벌 예측기에 의해 무시되는 다음 라인 예측기를 사용하며, 결합 선택은 바이모달 예측기에 의해 이루어진다.[37][54]

AMD K8은 결합된 바이모달 및 글로벌 예측기를 가지고 있으며, 결합 선택은 또 다른 바이모달 예측기이다. 이 프로세서는 ECC에 사용되는 L2 캐시 비트에 기본 및 선택 바이모달 예측기 카운터를 캐싱한다. 결과적으로, 기본 및 선택 예측기 테이블이 매우 크며, L2 캐시의 명령어에 ECC가 아닌 패리티 비트가 있다. 패리티 설계는 충분하다. 패리티 오류가 발생하는 모든 명령어를 무효화하고 메모리에서 다시 가져올 수 있기 때문이다.

알파 21464(Alpha 21464) (EV8, 설계 후반에 취소됨)는 최소 14 사이클의 분기 예측 오류 페널티를 가졌다. 결합된 바이모달 및 다수결 투표 예측기에 의해 무시되는 복잡하지만 빠른 다음 라인 예측기를 사용할 예정이었습니다. 다수결 투표는 바이모달 및 두 개의 gskew 예측기 사이에서 이루어졌습니다.[37][54]

2018년에는 스펙터(Spectre)라고 불리는 치명적인 보안 취약점이 Google의 Project Zero 및 기타 연구원에 의해 공개되었다. 사실상 모든 최신 CPU에 영향을 미치는 이 취약점은 분기 예측기를 준비하여 다른 프로세스(또는 커널)가 분기를 잘못 예측하고 비밀 데이터를 배열 인덱스로 사용하여 공격자의 캐시 라인 중 하나를 제거하는 것을 포함한다. 공격자는 자신의 배열에 대한 액세스 시간을 측정하여 어느 배열인지 알아낼 수 있으며, 이를 통해 공격자가 직접 읽을 수 없었던 값에 대한 정보를 갖는 값을 저장할 수 있는 이 CPU 내부(마이크로아키텍처) 상태를 값으로 변환한다.[38]

2. 2. 2비트 예측기의 등장

IBM 7030 스트레치는 1950년대 후반에 설계되었으며, 무조건 분기 및 인덱스 레지스터에 의존하는 모든 조건 분기를 미리 실행했다.[34] 다른 조건 분기의 경우, 처음 두 개의 생산 모델은 예측을 수행하지 않도록 구현했지만, 이후 모델은 오늘날의 상태 코드에 해당하는 표시기 비트의 현재 값을 기반으로 예측을 구현하도록 변경되었다.[34] 스트레치 설계자들은 프로젝트 초기에 분기 명령어에 정적 힌트 비트를 고려했지만, 이를 채택하지 않기로 결정했다.[34] 잘못된 예측 복구는 스트레치의 룩어헤드 유닛에 의해 제공되었으며, 스트레치의 그다지 훌륭하지 않은 성능에 대한 명성은 잘못된 예측 복구에 소요되는 시간에 기인했다.[34] 이후 IBM의 대형 컴퓨터 설계에서는 1985년 IBM 3090까지 추측 실행을 사용한 분기 예측을 사용하지 않았다.[34]

2비트 예측기는 1977년 Tom McWilliams와 Curt Widdoes에 의해 로렌스 리버모어 국립 연구소 S-1 슈퍼컴퓨터용으로 도입되었으며, 1979년 Jim Smith에 의해 CDC에서 독립적으로 도입되었다.[35][52]

1960년대부터 1980년대까지, 그리고 그 이후까지 널리 사용되었던 마이크로 프로그램 방식 프로세서는 명령어당 여러 사이클을 소요했으며, 일반적으로 분기 예측을 필요로 하지 않았다. 그러나 IBM 3090 외에도 분기 예측을 통합한 몇 가지 다른 마이크로프로그래밍 설계의 예가 있다.[34]

1982년경에 출시된 마이크로프로그래밍된 COBOL 머신인 Burroughs B4900은 파이프라인 방식을 사용했으며 분기 예측을 사용했다. B4900의 분기 예측 기록 상태는 프로그램 실행 중에 메모리 내 명령어에 다시 저장된다. B4900은 각 분기 연산자 유형을 나타내기 위해 4개의 의미적으로 동일한 분기 연산 코드를 사용하여 4상태 분기 예측을 구현한다. 사용된 연산 코드는 해당 특정 분기 명령어의 기록을 나타낸다. 하드웨어가 특정 분기의 분기 예측 상태를 업데이트해야 한다고 판단하면, 올바른 기록을 힌트하는 의미적으로 동일한 연산 코드로 연산 코드를 다시 쓴다. 이 방식은 93%의 적중률을 얻는다.

1989년에 발표된 DEC VAX 9000은 마이크로프로그래밍 방식과 파이프라인 방식을 모두 사용하며 분기 예측을 수행한다.[36][53]

최초의 상업용 RISC 프로세서인 MIPS R2000 및 R3000과 초기 SPARC 프로세서는 사소한 "예측 안 함" 분기 예측만 수행한다. 분기 지연 슬롯을 사용하고, 사이클당 하나의 명령어만 가져오며, 순서대로 실행하기 때문에 성능 저하가 없다. 이후의 R4000은 동일한 사소한 "예측 안 함" 분기 예측을 사용하며, 분기 해결 재발이 4 사이클이기 때문에 각 분기마다 두 사이클을 잃는다.

분기 예측은 인텔 펜티엄, DEC 알파 21064, MIPS R8000, IBM POWER 시리즈와 같은 파이프라인 슈퍼스칼라 프로세서의 도입과 함께 더욱 중요해졌다. 이러한 프로세서는 모두 1비트 또는 단순 바이모달 예측기에 의존한다.

DEC 알파 21264 (EV6)는 결합된 로컬 예측기 및 글로벌 예측기에 의해 무시되는 다음 라인 예측기를 사용하며, 결합 선택은 바이모달 예측기에 의해 이루어진다.[37][54]

AMD K8은 결합된 바이모달 및 글로벌 예측기를 가지고 있으며, 결합 선택은 또 다른 바이모달 예측기이다. 이 프로세서는 ECC에 사용되는 L2 캐시 비트에 기본 및 선택 바이모달 예측기 카운터를 캐싱한다. 결과적으로, 기본 및 선택 예측기 테이블이 매우 크며, L2 캐시의 명령어에 ECC가 아닌 패리티가 있다. 패리티 설계는 충분하다. 패리티 오류가 발생하는 모든 명령어를 무효화하고 메모리에서 다시 가져올 수 있기 때문이다.

알파 21464 (EV8, 설계 후반에 취소됨)는 최소 14 사이클의 분기 예측 오류 페널티를 가졌다. 결합된 바이모달 및 다수결 투표 예측기에 의해 무시되는 복잡하지만 빠른 다음 라인 예측기를 사용할 예정이었습니다. 다수결 투표는 바이모달 및 두 개의 gskew 예측기 사이에서 이루어졌습니다.

2018년에는 스펙터라고 불리는 치명적인 보안 취약점이 Google의 Project Zero 및 기타 연구원에 의해 공개되었다.[38] 사실상 모든 최신 CPU에 영향을 미치는 이 취약점은 분기 예측기를 준비하여 다른 프로세스(또는 커널)가 분기를 잘못 예측하고 비밀 데이터를 배열 인덱스로 사용하여 공격자의 캐시 라인 중 하나를 제거하는 것을 포함한다. 공격자는 자신의 배열에 대한 액세스 시간을 측정하여 어느 배열인지 알아낼 수 있으며, 이를 통해 공격자가 직접 읽을 수 없었던 값에 대한 정보를 갖는 값을 저장할 수 있는 이 CPU 내부(마이크로아키텍처) 상태를 값으로 변환한다.[38]

2. 3. RISC 프로세서와 분기 예측

IBM 7030 스트레치는 1950년대 후반 설계되었으며, 무조건 분기 및 인덱스 레지스터에 의존하는 모든 조건 분기를 미리 실행했다.[34] 다른 조건 분기의 경우, 처음 두 생산 모델은 예측을 수행하지 않았으나, 이후 모델은 표시기 비트의 현재 값을 기반으로 예측을 구현하도록 변경되었다.[34] 스트레치 설계자들은 분기 명령어에 정적 힌트 비트를 고려했지만 채택하지 않았다. 잘못된 예측 복구는 스트레치의 룩어헤드 유닛에 의해 제공되었으며, 스트레치의 성능에 대한 명성은 잘못된 예측 복구 시간에 기인했다. 이후 IBM의 대형 컴퓨터 설계에서는 1985년 IBM 3090까지 추측 실행을 사용한 분기 예측을 사용하지 않았다.[34]

2비트 예측기는 1977년 Tom McWilliams와 Curt Widdoes에 의해 로렌스 리버모어 국립 연구소 S-1 슈퍼컴퓨터용으로 도입되었으며, 1979년 Jim Smith에 의해 CDC에서 독립적으로 도입되었다.[35]

1960년대부터 1980년대, 그리고 그 이후까지 널리 사용되었던 마이크로 프로그램 방식 프로세서는 명령어당 여러 사이클을 소요했으며, 일반적으로 분기 예측을 필요로 하지 않았다. 그러나 IBM 3090 외에도 분기 예측을 통합한 몇 가지 다른 마이크로프로그래밍 설계의 예가 있다.

1982년경에 출시된 마이크로프로그래밍된 COBOL 머신인 Burroughs B4900은 파이프라인 방식을 사용했으며 분기 예측을 사용했다. B4900의 분기 예측 기록 상태는 프로그램 실행 중에 메모리 내 명령어에 다시 저장된다. B4900은 각 분기 연산자 유형을 나타내기 위해 4개의 의미적으로 동일한 분기 연산 코드를 사용하여 4상태 분기 예측을 구현한다. 사용된 연산 코드는 해당 특정 분기 명령어의 기록을 나타낸다. 하드웨어가 특정 분기의 분기 예측 상태를 업데이트해야 한다고 판단하면, 올바른 기록을 힌트하는 의미적으로 동일한 연산 코드로 연산 코드를 다시 쓴다. 이 방식은 93%의 적중률을 얻었다.

1989년에 발표된 DEC VAX 9000은 마이크로프로그래밍 방식과 파이프라인 방식을 모두 사용하며 분기 예측을 수행한다.[36]

최초의 상업용 RISC 프로세서인 MIPS R2000 및 R3000과 초기 SPARC 프로세서는 "예측 안 함" 분기 예측만 수행했다. 분기 지연 슬롯을 사용하고, 사이클당 하나의 명령어만 가져오며, 순서대로 실행하기 때문에 성능 저하가 없었다. 이후의 R4000은 "예측 안 함" 분기 예측을 사용하며, 분기 해결 재발이 4 사이클이기 때문에 각 분기마다 두 사이클을 잃었다.

분기 예측은 인텔 펜티엄, DEC 알파 21064, MIPS R8000, IBM POWER 시리즈와 같은 파이프라인 슈퍼스칼라 프로세서의 도입과 함께 중요해졌다. 이러한 프로세서는 모두 1비트 또는 단순 바이모달 예측기에 의존한다.

DEC 알파 21264 (EV6)는 결합된 로컬 예측기 및 글로벌 예측기에 의해 무시되는 다음 라인 예측기를 사용하며, 결합 선택은 바이모달 예측기에 의해 이루어진다.[37]

AMD K8은 결합된 바이모달 및 글로벌 예측기를 가지고 있으며, 결합 선택은 또 다른 바이모달 예측기이다. 이 프로세서는 ECC에 사용되는 L2 캐시 비트에 기본 및 선택 바이모달 예측기 카운터를 캐싱한다. 결과적으로, 기본 및 선택 예측기 테이블이 매우 크며, L2 캐시의 명령어에 ECC가 아닌 패리티가 있다. 패리티 설계는 충분하다. 패리티 오류가 발생하는 모든 명령어를 무효화하고 메모리에서 다시 가져올 수 있기 때문이다.

알파 21464 (EV8, 설계 후반에 취소됨)는 최소 14 사이클의 분기 예측 오류 페널티를 가졌다. 결합된 바이모달 및 다수결 투표 예측기에 의해 무시되는 복잡하지만 빠른 다음 라인 예측기를 사용할 예정이었다. 다수결 투표는 바이모달 및 두 개의 gskew 예측기 사이에서 이루어졌다.[37]

2018년에는 스펙터라고 불리는 치명적인 보안 취약점이 Google의 Project Zero 및 기타 연구원에 의해 공개되었다. 사실상 모든 최신 CPU에 영향을 미치는 이 취약점은 분기 예측기를 준비하여 다른 프로세스(또는 커널)가 분기를 잘못 예측하고 비밀 데이터를 배열 인덱스로 사용하여 공격자의 캐시 라인 중 하나를 제거하는 것을 포함한다. 공격자는 자신의 배열에 대한 액세스 시간을 측정하여 어느 배열인지 알아낼 수 있으며, 이를 통해 공격자가 직접 읽을 수 없었던 값에 대한 정보를 갖는 값을 저장할 수 있는 이 CPU 내부(마이크로아키텍처) 상태를 값으로 변환한다.[38]

역사적으로 파이프라인과 분기 예측은 마이크로 프로그램 방식의 CISC 프로세서에서 태어나 발전한 기술이며, RISC를 포함한 마이크로프로세서에서의 분기 예측은 처음에는 간단한 것이었다. "마이크로 프로그램 방식의 프로세서는 분기 예측을 필요로 하지 않았다"는 설이 있지만, 이는 잘못된 것이다.

2. 4. 현대 분기 예측의 발전

IBM 7030 스트레치(IBM 7030 Stretch)는 1950년대 후반에 설계되었으며, 무조건 분기 및 인덱스 레지스터에 의존하는 모든 조건 분기를 미리 실행했다.[34] 다른 조건 분기의 경우, 처음 두 개의 생산 모델은 예측을 수행하지 않도록 구현했지만, 이후 모델은 표시기 비트의 현재 값을 기반으로 예측을 구현하도록 변경되었다.[34] 스트레치 설계자들은 분기 명령어에 정적 힌트 비트를 고려했지만 채택하지 않았다. 잘못된 예측 복구는 스트레치의 룩어헤드 유닛에 의해 제공되었으며, 잘못된 예측 복구에 소요되는 시간에 기인하여 스트레치의 성능은 좋지않았다. 이후 IBM의 대형 컴퓨터 설계에서는 1985년 IBM 3090까지 추측 실행을 사용한 분기 예측을 사용하지 않았다.[34]

2비트 예측기는 1977년 Tom McWilliams와 Curt Widdoes에 의해 로렌스 리버모어 국립 연구소 S-1 슈퍼컴퓨터용으로 도입되었으며, 1979년 Jim Smith에 의해 CDC에서 독립적으로 도입되었다.[35]

1960년대부터 1980년대까지, 그리고 그 이후까지 널리 사용되었던 마이크로프로그래밍 프로세서는 명령어당 여러 사이클을 소요했으며, 일반적으로 분기 예측을 필요로 하지 않았다. 그러나 IBM 3090 외에도 분기 예측을 통합한 몇 가지 다른 마이크로프로그래밍 설계의 예가 있다.[34]

1982년경에 출시된 마이크로프로그래밍된 COBOL 머신인 Burroughs B4900은 파이프라인 방식을 사용했으며 분기 예측을 사용했다. B4900의 분기 예측 기록 상태는 프로그램 실행 중에 메모리 내 명령어에 다시 저장된다. B4900은 각 분기 연산자 유형을 나타내기 위해 4개의 의미적으로 동일한 분기 연산 코드를 사용하여 4상태 분기 예측을 구현한다. 사용된 연산 코드는 해당 특정 분기 명령어의 기록을 나타낸다. 하드웨어가 특정 분기의 분기 예측 상태를 업데이트해야 한다고 판단하면, 올바른 기록을 힌트하는 의미적으로 동일한 연산 코드로 연산 코드를 다시 쓴다. 이 방식은 93%의 적중률을 얻었다.

1989년에 발표된 DEC VAX 9000은 마이크로프로그래밍 방식과 파이프라인 방식을 모두 사용하며 분기 예측을 수행한다.[36]

최초의 상업용 RISC 프로세서인 MIPS R2000 및 R3000과 초기 SPARC 프로세서는 "예측 안 함" 분기 예측만 수행한다. 분기 지연 슬롯을 사용하고, 사이클당 하나의 명령어만 가져오며, 순서대로 실행하기 때문에 성능 저하가 없다. 이후의 R4000은 동일한 "예측 안 함" 분기 예측을 사용하며, 분기 해결 재발이 4 사이클이기 때문에 각 분기마다 두 사이클을 잃는다.

분기 예측은 인텔 펜티엄, DEC 알파 21064, MIPS R8000, IBM POWER 시리즈와 같은 파이프라인 슈퍼스칼라 프로세서의 도입과 함께 더욱 중요해졌다. 이러한 프로세서는 모두 1비트 또는 단순 바이모달 예측기에 의존한다.

DEC 알파 21264 (EV6)는 결합된 로컬 예측기 및 글로벌 예측기에 의해 무시되는 다음 라인 예측기를 사용하며, 결합 선택은 바이모달 예측기에 의해 이루어진다.[37]

AMD K8은 결합된 바이모달 및 글로벌 예측기를 가지고 있으며, 결합 선택은 또 다른 바이모달 예측기이다. 이 프로세서는 ECC에 사용되는 L2 캐시 비트에 기본 및 선택 바이모달 예측기 카운터를 캐싱한다. 결과적으로, 기본 및 선택 예측기 테이블이 매우 크며, L2 캐시의 명령어에 ECC가 아닌 패리티가 있다.

알파 21464 (EV8, 설계 후반에 취소됨)는 최소 14 사이클의 분기 예측 오류 페널티를 가졌다. 결합된 바이모달 및 다수결 투표 예측기에 의해 무시되는 복잡하지만 빠른 다음 라인 예측기를 사용할 예정이었다. 다수결 투표는 바이모달 및 두 개의 gskew 예측기 사이에서 이루어졌다.[37]

2018년에는 스펙터라고 불리는 치명적인 보안 취약점이 Google의 Project Zero 및 기타 연구원에 의해 공개되었다. 사실상 모든 최신 CPU에 영향을 미치는 이 취약점은 분기 예측기를 준비하여 다른 프로세스(또는 커널)가 분기를 잘못 예측하고 비밀 데이터를 배열 인덱스로 사용하여 공격자의 캐시 라인 중 하나를 제거하는 것을 포함한다.[38]

3. 구현

3. 1. 정적 예측

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

초기 SPARC 및 MIPS(최초의 상업용 RISC 아키텍처 중 2개) 구현에서는 단일 방향 정적 분기 예측을 사용했다. 조건부 점프가 실행되지 않을 것으로 항상 예측하여 항상 다음 순차 명령을 가져온다. 분기 또는 점프가 실행되어 실행된 경우에만 명령 포인터가 비순차적 주소로 설정된다.

두 CPU 모두 디코딩 단계에서 분기를 평가하고 단일 사이클 명령 가져오기를 수행한다. 결과적으로 분기 대상 재발생은 2 사이클이며, 시스템은 실행된 모든 분기 바로 뒤의 명령을 항상 가져온다. 두 아키텍처 모두 이러한 가져온 명령을 활용하기 위해 분기 지연 슬롯을 정의했다.

더 발전된 형태의 정적 예측은 뒤로 가는 분기는 실행되고 앞으로 가는 분기는 실행되지 않는다고 가정한다. 뒤로 가는 분기는 대상 주소가 자체 주소보다 낮은 분기이다. 이 기술은 일반적으로 뒤로 가는 분기이며 실행될 확률이 높은 루프의 예측 정확도를 높이는 데 도움이 될 수 있다.

일부 프로세서는 정적 예측을 실행할지 여부를 알려주기 위해 코드에 분기 예측 힌트를 삽입할 수 있다. 인텔 펜티엄 4는 분기 예측 힌트를 허용했지만 이 기능은 이후 인텔 프로세서에서는 폐기되었다.[8][40]

정적 예측은 동적 예측기가 사용할 충분한 정보를 가지고 있지 않을 때, 일부 동적 분기 예측 프로세서에서 대체 기술로 사용된다. 모토로라 MPC7450 (G4e)와 인텔 펜티엄 4 모두 이 기술을 대체 기술로 사용한다.[9][41]

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

3. 1. 1. 단일 방향 정적 예측

wikitext

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

초기 SPARC 및 MIPS(최초의 상업용 RISC 아키텍처 중 2개) 구현에서는 단일 방향 정적 분기 예측을 사용했다. 조건부 점프가 실행되지 않을 것으로 항상 예측하여 항상 다음 순차 명령을 가져온다. 분기 또는 점프가 실행되어 실행된 경우에만 명령 포인터가 비순차적 주소로 설정된다.

두 CPU 모두 디코딩 단계에서 분기를 평가하고 단일 사이클 명령 가져오기를 수행한다. 결과적으로 분기 대상 재발생은 2 사이클이며, 시스템은 실행된 모든 분기 바로 뒤의 명령을 항상 가져온다. 두 아키텍처 모두 이러한 가져온 명령을 활용하기 위해 분기 지연 슬롯을 정의한다.

더 발전된 형태의 정적 예측은 뒤로 가는 분기는 실행되고 앞으로 가는 분기는 실행되지 않는다고 가정한다. 뒤로 가는 분기는 대상 주소가 자체 주소보다 낮은 분기이다. 이 기술은 일반적으로 뒤로 가는 분기이며 실행될 확률이 높은 루프의 예측 정확도를 높이는 데 도움이 될 수 있다.

일부 프로세서는 정적 예측을 실행할지 여부를 알려주기 위해 코드에 분기 예측 힌트를 삽입할 수 있다. 인텔 펜티엄 4는 분기 예측 힌트를 허용했지만 이 기능은 이후 인텔 프로세서에서는 폐기되었다.[8]

정적 예측은 동적 예측기가 사용할 충분한 정보를 가지고 있지 않을 때, 일부 동적 분기 예측 프로세서에서 대체 기술로 사용된다. 모토로라 MPC7450 (G4e)와 인텔 펜티엄 4 모두 이 기술을 대체 기술로 사용한다.[9]

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

3. 1. 2. 컴파일러 기반 정적 예측

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

초기 SPARC 및 MIPS(최초의 상업용 RISC 아키텍처 중 2개) 구현에서는 단일 방향 정적 분기 예측을 사용했다. 조건부 점프가 실행되지 않을 것으로 항상 예측하여 항상 다음 순차 명령을 가져온다. 분기 또는 점프가 실행되어 실행된 경우에만 명령 포인터가 비순차적 주소로 설정된다.

두 CPU 모두 디코딩 단계에서 분기를 평가하고 단일 사이클 명령 가져오기를 수행한다. 결과적으로 분기 대상 재발생은 2 사이클이며, 시스템은 실행된 모든 분기 바로 뒤의 명령을 항상 가져온다. 두 아키텍처 모두 이러한 가져온 명령을 활용하기 위해 분기 지연 슬롯을 정의한다.

보다 발전된 형태의 정적 예측은 뒤로 가는 분기는 실행되고 앞으로 가는 분기는 실행되지 않는다고 가정한다. 뒤로 가는 분기는 대상 주소가 자체 주소보다 낮은 분기이다. 이 기술은 일반적으로 뒤로 가는 분기이며 실행될 확률이 높은 루프의 예측 정확도를 높이는 데 도움이 될 수 있다.

일부 프로세서는 정적 예측을 실행할지 여부를 알려주기 위해 코드에 분기 예측 힌트를 삽입할 수 있다. 인텔 펜티엄 4는 분기 예측 힌트를 허용했지만 이 기능은 이후 인텔 프로세서에서는 폐기되었다.[8]

정적 예측은 동적 예측기가 사용할 충분한 정보를 가지고 있지 않을 때, 일부 동적 분기 예측 프로세서에서 대체 기술로 사용된다. 모토로라 MPC7450 (G4e)와 인텔 펜티엄 4 모두 이 기술을 대체 기술로 사용한다.[9]

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

3. 2. 동적 예측

동적 분기 예측은 실행 시간에 수집된 분기의 실행 여부에 대한 정보를 사용하여 분기의 결과를 예측한다.[1]

==== 1단계 예측 ====

==== 포화 카운터 (2비트 예측기) ====

1비트 포화 카운터 (플립플롭)는 분기의 마지막 결과를 기록한다. 이는 가장 간단한 동적 분기 예측 방식이지만, 정확도는 떨어진다.

2비트 포화 산술[1]는 다음 네 가지 상태를 가진 상태 머신이다.

2비트 포화 카운터의 상태 다이어그램

  • 강하게 실행 안 함
  • 약하게 실행 안 함
  • 약하게 실행
  • 강하게 실행


분기가 평가되면 해당 상태 머신이 업데이트된다. '실행 안 함'으로 평가된 분기는 '강하게 실행 안 함' 방향으로, '실행'으로 평가된 분기는 '강하게 실행' 방향으로 상태를 변경한다. 2비트 카운터 방식은 조건부 점프가 예측을 변경하기 전에 과거에 가장 많이 했던 것에서 두 번 벗어나야 한다는 장점이 있다. 예를 들어, 루프 종료 조건부 점프는 두 번이 아닌 한 번 잘못 예측된다.

초기의 비MMX 인텔 펜티엄 프로세서는 불완전한 구현이기는 하지만 포화 카운터를 사용한다.[8]

SPEC'89 벤치마크에서, 모든 분기가 고유한 카운터에 매핑되면 매우 큰 양방향 예측기는 93.5%의 정확도로 포화된다.[11]

예측 테이블은 명령 메모리 주소 비트로 인덱싱되므로, 프로세서는 명령이 디코딩되기 전에 각 명령에 대한 예측을 가져올 수 있다.

==== 2단계 적응형 예측기 ====

투-레벨 분기 예측기(Two-Level Branch Predictor)는 상관 기반 분기 예측기라고도 하며, "패턴 히스토리 테이블"이라고도 불리는 2차원 카운터 테이블을 사용한다. 테이블 항목은 2비트 카운터이다.[12]

`if` 문이 세 번 실행되는 경우, 세 번째 실행에서 결정은 이전 두 번의 실행이 수행되었는지 여부에 따라 달라질 수 있다. 이러한 시나리오에서 2단계 적응형 예측기는 포화 카운터보다 더 효율적으로 작동한다. 매 두 번째마다 수행되거나 다른 규칙적으로 반복되는 패턴을 가진 조건부 점프는 포화 카운터에 의해 제대로 예측되지 않는다. 2단계 적응형 예측기는 분기의 마지막 n번의 발생 기록을 기억하고 가능한 2n개의 히스토리 패턴 각각에 대해 하나의 포화 카운터를 사용한다.

n = 2인 경우를 생각해 보자. 이는 분기의 마지막 두 번의 발생이 2비트 시프트 레지스터에 저장된다는 의미이다. 이 분기 히스토리 레지스터는 00, 01, 10, 11의 네 가지 다른 이진 값을 가질 수 있으며, 여기서 0은 "수행되지 않음"을 의미하고 1은 "수행됨"을 의미한다. 패턴 히스토리 테이블은 분기당 4개의 항목을 포함하며, 22 = 4개의 가능한 분기 히스토리 각각에 대해 하나씩 포함하며, 테이블의 각 항목에는 각 분기에 대해 2비트 포화 카운터가 포함되어 있다. 분기 히스토리 레지스터는 4개의 포화 카운터 중 어느 것을 사용할지 선택하는 데 사용된다. 기록이 00인 경우 첫 번째 카운터가 사용되고, 기록이 11인 경우 4개의 카운터 중 마지막 카운터가 사용된다.

예를 들어 조건부 점프가 세 번째마다 수행된다고 가정한다. 분기 시퀀스는 001001001...이다. 이 경우 패턴 히스토리 테이블의 항목 번호 00은 "강력하게 수행됨" 상태로 이동하여 두 개의 0 다음에 1이 온다는 것을 나타낸다. 항목 번호 01은 "강력하게 수행되지 않음" 상태로 이동하여 01 다음에 0이 온다는 것을 나타낸다. 항목 번호 10도 마찬가지이며, 11은 두 개의 연속된 1이 없기 때문에 사용되지 않는다.

n비트 기록을 가진 2단계 적응형 예측기의 일반적인 규칙은 모든 n비트 부분 시퀀스가 다르면 모든 주기적 시퀀스를 예측할 수 있다는 것이다.[8]

2단계 적응형 예측기의 장점은 임의의 반복 패턴을 예측하는 것을 빠르게 배울 수 있다는 것이다. 이 방법은 미시간 대학교의 T.-Y. Yeh와 예일 패트에 의해 발명되었다.[13] 1991년 최초 발표 이후 이 방법은 매우 인기를 얻었다. 이 예측 방법의 변형은 대부분의 최신 마이크로프로세서에서 사용된다.

두 번째 실행 시 항상 분기하는 조건 분기(예를 들어, 포인터가 NULL인지 여부에 따라 분기하고, NULL인 경우 리소스를 확보하고, 그렇지 않으면 단순히 포인터가 가리키는 리소스에 액세스하는 경우)나 다른 규칙적으로 반복되는 패턴을 가진 조건 분기는 포화 카운터만으로는 제대로 예측할 수 없다. 2단계 적응형 분기 예측은 각 조건 분기 명령의 과거 n회의 히스토리를 기억하고, 2n개의 히스토리 패턴 각각에 포화 카운터를 대응시킨다.

n = 2인 경우를 예로 생각해 보자. 과거 2번의 분기 명령 실행 시 분기했는지 여부를 2비트의 시프트 레지스터에 저장한다. 이 분기 히스토리 레지스터는 이진법으로 4종류의 다른 값, 00, 01, 10, 11 중 하나가 된다. 여기서 0은 "분기하지 않음", 1은 "분기함"을 의미한다. 패턴 히스토리 테이블은 4개의 항목으로, 각 항목의 인덱스는 2n = 4종류의 패턴 중 하나에 해당한다. 패턴 히스토리 테이블의 각 항목 내용은 2비트 포화 카운터와 같다. 어떤 분기 명령의 히스토리가 00이면 패턴 히스토리 테이블의 첫 번째 카운터를 사용한다. 히스토리가 11이면 마지막 항목의 카운터를 사용한다.

어떤 조건 분기가 3번 중 1번의 패턴으로 분기한다고 가정하자. 그러면 분기 시퀀스는 001001001…가 된다. 이 경우 00 다음에 반드시 1이 오므로, 패턴 히스토리 테이블의 항목 00의 포화 카운터 상태는 "strongly taken"이 된다. 마찬가지로 01 다음에는 반드시 0이 오므로, 항목 01은 "strongly not taken"이 된다. 항목 10도 마찬가지이며, 항목 11은 이 분기 명령에서는 절대 패턴으로 나타나지 않으므로 사용되지 않는다.

일반적으로 n비트의 히스토리를 가진 2단계 적응형 분기 예측은 모든 n비트의 부분 시퀀스가 다르다면, 어떤 간격으로 반복되는 시퀀스라도 예측 가능하다[40]。

2단계 적응형 분기 예측의 장점은 임의의 반복 패턴에 대해 빠르게 예측을 학습할 수 있다는 점이다. 이 방식은 미시간 대학교의 T.-Y. Yeh와 예일 패트가 발명했다[44]。 1991년에 발표되었으며, 널리 채택되었다. 현대 마이크로프로세서의 많은 수가 이 방식에서 파생된 방식을 채용하고 있다.

==== 신경망 예측기 ====

기계 학습을 이용한 분기 예측은 루시안 빈탄(시비우 루시안 블라가 대학교)이 "신경망 분기 예측"으로 제안했다.[24] 1년 후, 그는 퍼셉트론 분기 예측기를 개발했다.[25] 신경망 분기 예측 연구는 다니엘 히메네스에 의해 훨씬 더 발전되었다.[26] 2001년,[26] 하드웨어 구현이 가능한 최초의 퍼셉트론 예측기가 발표되었다. 퍼셉트론 분기 예측기의 최초 상용 구현은 AMD의 파일드라이버 마이크로아키텍처에 있었다.[27]

신경망 예측기의 주요 장점은 선형적인 자원 증가만 필요하면서도 긴 히스토리를 활용할 수 있다는 점이다. 기존 예측기는 기하급수적인 자원 증가를 필요로 한다. 히메네스는 맥퍼링 스타일의 하이브리드 예측기보다 전체적으로 5.7% 향상되었다고 보고했다.[28] 그는 또한 gshare/퍼셉트론 오버라이딩 하이브리드 예측기를 사용했다.[28]

퍼셉트론 예측기의 주요 단점은 높은 대기 시간이다. 고속 산술 트릭을 활용하더라도, 계산 대기 시간은 많은 최신 마이크로아키텍처의 클럭 주기에 비해 상대적으로 높다. 예측 대기 시간을 줄이기 위해 히메네스는 2003년에 현재 분기의 PC가 아닌 현재 분기의 경로에 따라 가중치를 선택하는 ''고속 경로 신경망 예측기''를 제안했다. 많은 다른 연구자들이 이 개념을 개발했다.

최첨단 분기 예측기의 대부분은 퍼셉트론 예측기를 사용하고 있다 (인텔의 "챔피언십 분기 예측 경쟁" 참조).[29] 인텔은 이미 IA-64의 시뮬레이터 중 하나 (2003년)에 이 아이디어를 구현했다.[30]

AMD 라이젠[31][32][33] 멀티 코어 프로세서의 인피니티 패브릭과 삼성 엑시노스 프로세서에는 퍼셉트론 기반 신경망 분기 예측기가 포함되어 있다.

3. 2. 1. 1단계 예측

(빈칸)

3. 2. 2. 포화 카운터 (2비트 예측기)

1비트 포화 카운터 (플립플롭)는 분기의 마지막 결과를 기록한다. 이는 가장 간단한 동적 분기 예측 방식이지만, 정확도는 떨어진다.

2비트 포화 산술[1]는 다음 네 가지 상태를 가진 상태 머신이다.

  • 강하게 실행 안 함
  • 약하게 실행 안 함
  • 약하게 실행
  • 강하게 실행


분기가 평가되면 해당 상태 머신이 업데이트된다. '실행 안 함'으로 평가된 분기는 '강하게 실행 안 함' 방향으로, '실행'으로 평가된 분기는 '강하게 실행' 방향으로 상태를 변경한다. 2비트 카운터 방식은 조건부 점프가 예측을 변경하기 전에 과거에 가장 많이 했던 것에서 두 번 벗어나야 한다는 장점이 있다. 예를 들어, 루프 종료 조건부 점프는 두 번이 아닌 한 번 잘못 예측된다.

초기의 비MMX 인텔 펜티엄 프로세서는 불완전한 구현이기는 하지만 포화 카운터를 사용한다.[8]

SPEC'89 벤치마크에서, 모든 분기가 고유한 카운터에 매핑되면 매우 큰 양방향 예측기는 93.5%의 정확도로 포화된다.[11]

예측 테이블은 명령 메모리 주소 비트로 인덱싱되므로, 프로세서는 명령이 디코딩되기 전에 각 명령에 대한 예측을 가져올 수 있다.

3. 2. 3. 2단계 적응형 예측기

투-레벨 분기 예측기(Two-Level Branch Predictor)는 상관 기반 분기 예측기라고도 하며, "패턴 히스토리 테이블"이라고도 불리는 2차원 카운터 테이블을 사용한다. 테이블 항목은 2비트 카운터이다.[12]

그림 3: 2단계 적응형 분기 예측기. 패턴 히스토리 테이블의 각 항목은 2비트 포화 카운터를 나타낸다.


`if` 문이 세 번 실행되는 경우, 세 번째 실행에서 결정은 이전 두 번의 실행이 수행되었는지 여부에 따라 달라질 수 있다. 이러한 시나리오에서 2단계 적응형 예측기는 포화 카운터보다 더 효율적으로 작동한다. 매 두 번째마다 수행되거나 다른 규칙적으로 반복되는 패턴을 가진 조건부 점프는 포화 카운터에 의해 제대로 예측되지 않는다. 2단계 적응형 예측기는 분기의 마지막 n번의 발생 기록을 기억하고 가능한 2n개의 히스토리 패턴 각각에 대해 하나의 포화 카운터를 사용한다.

n = 2인 경우를 생각해 보자. 이는 분기의 마지막 두 번의 발생이 2비트 시프트 레지스터에 저장된다는 의미이다. 이 분기 히스토리 레지스터는 00, 01, 10, 11의 네 가지 다른 이진 값을 가질 수 있으며, 여기서 0은 "수행되지 않음"을 의미하고 1은 "수행됨"을 의미한다. 패턴 히스토리 테이블은 분기당 4개의 항목을 포함하며, 22 = 4개의 가능한 분기 히스토리 각각에 대해 하나씩 포함하며, 테이블의 각 항목에는 각 분기에 대해 2비트 포화 카운터가 포함되어 있다. 분기 히스토리 레지스터는 4개의 포화 카운터 중 어느 것을 사용할지 선택하는 데 사용된다. 기록이 00인 경우 첫 번째 카운터가 사용되고, 기록이 11인 경우 4개의 카운터 중 마지막 카운터가 사용된다.

예를 들어 조건부 점프가 세 번째마다 수행된다고 가정한다. 분기 시퀀스는 001001001...이다. 이 경우 패턴 히스토리 테이블의 항목 번호 00은 "강력하게 수행됨" 상태로 이동하여 두 개의 0 다음에 1이 온다는 것을 나타낸다. 항목 번호 01은 "강력하게 수행되지 않음" 상태로 이동하여 01 다음에 0이 온다는 것을 나타낸다. 항목 번호 10도 마찬가지이며, 11은 두 개의 연속된 1이 없기 때문에 사용되지 않는다.

n비트 기록을 가진 2단계 적응형 예측기의 일반적인 규칙은 모든 n비트 부분 시퀀스가 다르면 모든 주기적 시퀀스를 예측할 수 있다는 것이다.[8]

2단계 적응형 예측기의 장점은 임의의 반복 패턴을 예측하는 것을 빠르게 배울 수 있다는 것이다. 이 방법은 미시간 대학교의 T.-Y. Yeh와 예일 패트에 의해 발명되었다.[13] 1991년 최초 발표 이후 이 방법은 매우 인기를 얻었다. 이 예측 방법의 변형은 대부분의 최신 마이크로프로세서에서 사용된다.

두 번째 실행 시 항상 분기하는 조건 분기(예를 들어, 포인터가 NULL인지 여부에 따라 분기하고, NULL인 경우 리소스를 확보하고, 그렇지 않으면 단순히 포인터가 가리키는 리소스에 액세스하는 경우)나 다른 규칙적으로 반복되는 패턴을 가진 조건 분기는 포화 카운터만으로는 제대로 예측할 수 없다. 2단계 적응형 분기 예측은 각 조건 분기 명령의 과거 n회의 히스토리를 기억하고, 2n개의 히스토리 패턴 각각에 포화 카운터를 대응시킨다.

n = 2인 경우를 예로 생각해 보자. 과거 2번의 분기 명령 실행 시 분기했는지 여부를 2비트의 시프트 레지스터에 저장한다. 이 분기 히스토리 레지스터는 이진법으로 4종류의 다른 값, 00, 01, 10, 11 중 하나가 된다. 여기서 0은 "분기하지 않음", 1은 "분기함"을 의미한다. 패턴 히스토리 테이블은 4개의 항목으로, 각 항목의 인덱스는 2n = 4종류의 패턴 중 하나에 해당한다. 패턴 히스토리 테이블의 각 항목 내용은 2비트 포화 카운터와 같다. 어떤 분기 명령의 히스토리가 00이면 패턴 히스토리 테이블의 첫 번째 카운터를 사용한다. 히스토리가 11이면 마지막 항목의 카운터를 사용한다.

어떤 조건 분기가 3번 중 1번의 패턴으로 분기한다고 가정하자. 그러면 분기 시퀀스는 001001001…가 된다. 이 경우 00 다음에 반드시 1이 오므로, 패턴 히스토리 테이블의 항목 00의 포화 카운터 상태는 "strongly taken"이 된다. 마찬가지로 01 다음에는 반드시 0이 오므로, 항목 01은 "strongly not taken"이 된다. 항목 10도 마찬가지이며, 항목 11은 이 분기 명령에서는 절대 패턴으로 나타나지 않으므로 사용되지 않는다.

일반적으로 n비트의 히스토리를 가진 2단계 적응형 분기 예측은 모든 n비트의 부분 시퀀스가 다르다면, 어떤 간격으로 반복되는 시퀀스라도 예측 가능하다[40]。

2단계 적응형 분기 예측의 장점은 임의의 반복 패턴에 대해 빠르게 예측을 학습할 수 있다는 점이다. 이 방식은 미시간 대학교의 T.-Y. Yeh와 예일 패트가 발명했다[44]。 1991년에 발표되었으며, 널리 채택되었다. 현대 마이크로프로세서의 많은 수가 이 방식에서 파생된 방식을 채용하고 있다.

3. 2. 4. 신경망 예측기

기계 학습을 이용한 분기 예측은 루시안 빈탄(시비우 루시안 블라가 대학교)이 "신경망 분기 예측"으로 제안했다.[24] 1년 후, 그는 퍼셉트론 분기 예측기를 개발했다.[25] 신경망 분기 예측 연구는 다니엘 히메네스에 의해 훨씬 더 발전되었다.[26] 2001년,[26] 하드웨어 구현이 가능한 최초의 퍼셉트론 예측기가 발표되었다. 퍼셉트론 분기 예측기의 최초 상용 구현은 AMD의 파일드라이버 마이크로아키텍처에 있었다.[27]

신경망 예측기의 주요 장점은 선형적인 자원 증가만 필요하면서도 긴 히스토리를 활용할 수 있다는 점이다. 기존 예측기는 기하급수적인 자원 증가를 필요로 한다. 히메네스는 맥퍼링 스타일의 하이브리드 예측기보다 전체적으로 5.7% 향상되었다고 보고했다.[28] 그는 또한 gshare/퍼셉트론 오버라이딩 하이브리드 예측기를 사용했다.[28]

퍼셉트론 예측기의 주요 단점은 높은 대기 시간이다. 고속 산술 트릭을 활용하더라도, 계산 대기 시간은 많은 최신 마이크로아키텍처의 클럭 주기에 비해 상대적으로 높다. 예측 대기 시간을 줄이기 위해 히메네스는 2003년에 현재 분기의 PC가 아닌 현재 분기의 경로에 따라 가중치를 선택하는 ''고속 경로 신경망 예측기''를 제안했다. 많은 다른 연구자들이 이 개념을 개발했다.

최첨단 분기 예측기의 대부분은 퍼셉트론 예측기를 사용하고 있다 (인텔의 "챔피언십 분기 예측 경쟁" 참조).[29] 인텔은 이미 IA-64의 시뮬레이터 중 하나 (2003년)에 이 아이디어를 구현했다.[30]

AMD 라이젠[31][32][33] 멀티 코어 프로세서의 인피니티 패브릭과 삼성 엑시노스 프로세서에는 퍼셉트론 기반 신경망 분기 예측기가 포함되어 있다.

3. 3. 지역 분기 예측

지역 분기 예측기는 각 조건 분기 명령에 대해 별도의 히스토리 버퍼를 갖는다. 2단계 적응형 예측기를 사용할 수 있다.[11] 이 경우, 히스토리 버퍼는 각 조건 분기 명령에 대해 별도로 유지되며, 패턴 히스토리 테이블 역시 별도로 유지되거나 모든 조건 분기에 대해 공유될 수 있다.[45]

인텔 펜티엄 MMX, 펜티엄 II, 펜티엄 III는 각 조건 분기에 대해 4비트 지역 히스토리와 16개의 항목을 가진 지역 패턴 히스토리 테이블을 갖춘 지역 분기 예측기를 가지고 있다.[11][45]

표준 성능 평가 공사(SPEC)'89 벤치마크에서, 매우 큰 지역 예측기는 97.1%의 정확도로 포화된다.[11][45]

3. 4. 전역 분기 예측

전역 분기 예측기는 모든 조건 분기에 대한 공유 기록을 유지하여, 다른 조건 분기 간의 상관 관계를 예측에 반영한다. 그러나 서로 상관 관계가 없는 조건 분기의 경우 기록이 관련 없는 정보로 희석되거나, 동일 분기의 비트가 기록 버퍼에 포함되지 않을 수 있다. 이러한 경우 2단계 적응 예측기를 사용할 수 있다.

이 방식은 큰 테이블 크기에서 포화 카운터 방식보다 우수하지만, 지역 예측만큼 좋은 경우는 드물고, 좋은 예측을 위해 더 긴 기록 버퍼가 필요하다. 패턴 기록 테이블의 크기는 기록 버퍼 크기에 따라 지수 함수적으로 증가하므로, 큰 패턴 기록 테이블은 모든 조건 분기에서 공유된다.

전역으로 공유된 기록 버퍼와 패턴 기록 테이블을 가진 2단계 적응 예측기는, 전역 기록과 분기 PC를 XOR 게이트로 배타적 논리합(XOR)하면 "gshare" 예측기, 결합하면 "gselect" 예측기라고 한다. 전역 분기 예측은 AMD 프로세서와 인텔 펜티엄 M, 코어, 코어 2 및 실버몬트 기반 아톰 프로세서에서 사용된다.

3. 5. 결합 분기 예측 (하이브리드 예측기)

합금 분기 예측기는 지역 및 전역 분기 기록을 결합하거나, 프로그램 카운터의 일부 비트를 함께 사용하여 예측의 정확도를 높인다. VIA Nano 프로세서가 이 기술을 사용한 것으로 알려져 있다.[15][8]

하이브리드 예측기(hybrid predictor)는 결합 예측기(combined predictor)라고도 불리며, 두 개 이상의 예측 메커니즘을 함께 사용한다. 최종 예측은 과거에 어떤 예측기가 가장 좋은 예측을 제공했는지 기억하는 메타 예측기를 사용하거나, 홀수 개의 서로 다른 예측기를 기반으로 다수결 투표 함수를 사용하여 결정한다.

스콧 맥팔링은 1993년 논문에서 결합 분기 예측을 제안했다.[11]

SPEC'89 벤치마크에서 이러한 예측기는 로컬 예측기만큼 성능이 좋다.

gshare와 같은 예측기는 여러 개의 테이블 항목을 사용하여 특정 분기의 동작을 추적한다. 하지만, 이러한 항목의 증가는 두 분기가 동일한 테이블 항목에 매핑될 가능성(별칭)을 높여 예측 정확도를 떨어뜨릴 수 있다. 여러 예측기를 사용하는 경우, 각 예측기가 서로 다른 별칭 패턴을 갖도록 설계하여 적어도 하나의 예측기가 별칭이 없을 가능성을 높일 수 있다. 서로 다른 예측기에 대해 서로 다른 인덱싱 함수를 사용하는 결합 예측기를 ''gskew'' 예측기라고 하며, 이는 데이터 및 명령 캐싱에 사용되는 왜곡 연관 캐시와 유사하다.

합금 분기 예측(alloyed branch prediction)은 지역 분기 이력과 광역 분기 이력을 결합하고, 프로그램 카운터의 일부 비트 열을 포함하여 예측 정확도를 향상시킨다. VIA Nano 프로세서는 이 기술을 채택한 것으로 평가된다.[46][40]

통합 분기 예측(combined branch prediction)이라고도 불리는 하이브리드 분기 예측(hybrid branch prediction)은 여러 분기 예측 기구를 구현한다. 최종 예측은 과거에 어떤 예측기가 가장 좋은 성능을 보였는지 기억하는 메타 예측기가 결정하거나, 홀수 개의 예측기를 사용하여 다수결로 예측을 결정하는 방식 등을 사용한다.[48]

SPEC89 벤치마크에서 통합 분기 예측은 거의 지역 분기 예측과 같은 성능을 보인다.

gshare와 같은 분기 예측 방법에서는 하나의 분기 명령에 대응하는 테이블 엔트리가 여러 개 존재한다. 이는 같은 엔트리에서 여러 분기 명령이 경합하는 것을 의미하며, 결과적으로 분기 예측 정밀도를 악화시킨다. 따라서 여러 분기 예측 기법을 통합할 때에는 각 기법에서 엔트리 경합 패턴이 다르게 설계하는 것이 중요하다. 이렇게 하면 어느 하나는 경합하지 않는 엔트리로 예측할 수 있는 확률이 높아진다. 이러한 방식으로 통합된 분기 예측을 gskew 분기 예측이라고 부르며, 이는 skewed cache(연관도가 여러 캐시에 대해 웨이마다 다른 해시 함수를 사용하는 기법)에서 유추된 것이다.

3. 5. 1. 합의 예측기

합의 예측기는 전역 공유 히스토리 버퍼 및 패턴 히스토리 테이블과 추가적인 로컬 포화 카운터가 있는 2단계 적응형 예측기이다. 로컬 예측기와 전역 예측기의 출력은 서로 XOR 연산을 수행하여 최종 예측을 제공한다. 이 예측기의 목적은 반대 예측을 하는 두 개의 분기가 패턴 히스토리 테이블에서 동일한 항목을 공유하는 경우, 패턴 히스토리 테이블에서의 충돌을 줄이는 것이다.[16]

합의 예측은 광역적인 이력 버퍼와 패턴 이력 테이블을 사용한 2단계 적응형 분기 예측의 일종으로, 지역 포화 카운터를 추가하고 있다. 지역 분기 예측과 광역 분기 예측의 결과를 XOR하여 최종적인 예측 결과를 얻는다. 2개의 조건 분기 명령이 패턴 이력 테이블의 동일한 항목을 공유하고 있어 예측 결과가 다른 경우의 충돌을 최대한 줄이는 것을 목적으로 한다.[47]

초기의 펜티엄 4에서 채용되었지만, 그 이후 모델에서는 사용되지 않는다.

3. 5. 2. 루프 예측기

조건 분기가 루프를 제어하는 경우 특수한 루프 예측기로 예측하는 것이 가장 좋습니다. 루프 하단에 있는 N번 반복되는 조건 분기는 N-1번 실행된 후 한 번 실행되지 않습니다. 조건 분기가 루프 상단에 배치되면 N-1번 실행되지 않고 한 번 실행됩니다. 여러 번 한 방향으로 이동한 다음 한 번 다른 방향으로 가는 조건 분기는 루프 동작을 하는 것으로 감지됩니다. 이러한 조건 분기는 간단한 카운터로 쉽게 예측할 수 있습니다. 루프 예측기는 메타 예측기가 조건 분기가 루프 동작을 하는지 감지하는 하이브리드 예측기의 일부입니다.

루프를 구성하는 조건 분기를 가장 잘 예측하는 루프 전용 예측기가 있습니다. 루프 마지막 조건 분기는 N회 반복하는 경우 N-1회 분기하고, 1회만 분기하지 않습니다. 조건 분기가 루프 선두에 있는 경우 N-1회는 분기하지 않고, 1회만 분기합니다. 따라서, 여러 번 분기의 한쪽을 통과하고 드물게 다른 쪽을 통과하는 조건 분기는 루프를 형성하고 있다고 판단할 수 있습니다. 이러한 조건 분기는 단순한 카운터로 쉽게 예측할 수 있습니다. 루프 예측기는 하이브리드 분기 예측의 일부로 구현되며, 메타 예측기가 해당 조건 분기가 루프와 같은 동작을 하는지 감지하는 데 사용합니다.

최근 마이크로프로세서의 대부분이 루프 예측기를 구현하고 있습니다[40].

3. 6. 간접 분기 예측

간접 점프 명령어는 둘 이상의 분기 중에서 선택할 수 있다. 일부 프로세서는 특화된 간접 분기 예측기를 가지고 있다.[17][18] 인텔[19] 및 AMD[20]의 최신 프로세서는 2단계 적응형 예측기를 사용하여 간접 분기를 예측할 수 있다. 이러한 종류의 명령은 기록 버퍼에 둘 이상의 비트를 기여한다. zEC12 및 이후 z/Architecture 프로세서는 일반 목적 레지스터의 내용에 즉시 변위 값을 더하여 구성된 분기 대상 주소로 주어진 명령에 대한 분기 예측기 항목을 사전 로드할 수 있는 명령어를 지원한다.[21][22]

이러한 메커니즘이 없는 프로세서는 마지막으로 간접 점프가 했던 것과 동일한 대상으로 이동하도록 단순하게 예측한다.[8]

3. 7. 함수 반환 예측

일반적으로 함수는 호출된 위치로 반환된다. return 명령어은 호출 스택에서 대상 주소를 읽는 간접 점프이다. 많은 마이크로프로세서에는 return 명령어에 대한 별도의 예측 메커니즘이 있으며, 이 메커니즘은 호출 스택의 로컬 미러인 소위 "return stack buffer"를 기반으로 한다. return stack buffer의 크기는 일반적으로 4~16개 항목이다.

3. 8. 분기 예측 재정의

빠른 분기 예측과 정확한 분기 예측 사이의 상충 관계는 때때로 두 개의 분기 예측기를 갖는 것으로 해결된다. 첫 번째 분기 예측기는 빠르고 단순하다. 두 번째 분기 예측기는 더 느리고 복잡하며 더 큰 테이블을 사용하며, 첫 번째 예측기가 잘못 예측했을 가능성이 있는 경우 이를 무시한다.[23]

알파 21264 및 알파 EV8 마이크로프로세서는 분기 대상 재귀를 처리하고 간단하고 빠른 분기 예측을 제공하기 위해 빠른 단일 사이클 다음 라인 예측기를 사용했다. 다음 라인 예측기의 정확성이 매우 낮고 분기 해상도 재귀에 시간이 오래 걸리기 때문에, 두 코어 모두 단일 손실 페치 사이클의 대가로 다음 라인 예측기의 예측을 무시할 수 있는 2 사이클 보조 분기 예측기를 가지고 있다. 이를 통해 최악의 경우에도 1개 명령만 페치한 명령을 버리는 것으로 끝나, 성능이 향상된다. 4개 이상의 명령을 동시에 페치하면, 여러 개의 분기 명령이 포함될 가능성이 있다. 따라서 덮어쓰기 시에는 다음 명령이 분기하는지 하지 않는지를 예측할 필요가 있다. 일반적으로, 분기 명령을 평가하여 분기 주소를 구한다.[23]

인텔 코어 i7은 두 개의 분기 타겟 버퍼를 가지고 있으며, 두 개 이상의 분기 예측기를 갖추고 있다.[23]

4. 보안 취약점

참조

[1] 웹사이트 Dynamic Branch Prediction http://web.engr.oreg[...] 2017-03-22
[2] 웹사이트 The Schemes and Performances of Dynamic Branch predictors http://bwrcs.eecs.be[...]
[3] 웹사이트 Branch Prediction Techniques and Optimizations http://www.cse.iitd.[...] 2017-04-02
[4] 웹사이트 18-447 Computer Architecture Lecture 11: Branch Prediction https://www.ece.cmu.[...] 2013-02-11
[5] 간행물 Skewed branch predictors https://hal.science/[...] 1996-09
[6] conference Characterizing the branch misprediction penalty IEEE
[7] 서적 Modern processor design: fundamentals of superscalar processors https://archive.org/[...] McGraw-Hill Higher Education 2005
[8] 웹사이트 The microarchitecture of Intel, AMD, and VIA CPUs http://www.agner.org[...] 2017-03-22
[9] 웹사이트 The Pentium 4 and the G4e: an Architectural Comparison https://arstechnica.[...] 2001-05-12
[10] 웹사이트 CMSC 611: Advanced Computer Architecture, Chapter 4 (Part V) http://ece-research.[...]
[11] 웹사이트 Combining Branch Predictors https://hplabs.itcs.[...] 1993-06
[12] 학술지 New Algorithm Improves Branch Prediction: 3/27/95 https://www.cs.cmu.e[...] 2016-02-02
[13] conference Two-Level Adaptive Training Branch Prediction ACM 1991
[14] 학술지 Two-Level Branch Prediction using Neural Networks https://www.research[...] 2003-12
[15] conference A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions https://www.cs.virgi[...] 2000-10
[16] conference The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference http://meseec.ce.rit[...] 1997-06
[17] 웹사이트 Cortex-A15 MPCore Technical Reference Manual, section 6.5.3 "Indirect predictor" http://infocenter.ar[...]
[18] 웹사이트 Limits of Indirect Branch Prediction http://hoelzle.org/p[...] 1997-06-25
[19] 웹사이트 A Look at Centrino's Core: The Pentium M https://arstechnica.[...] 2004-02-25
[20] 웹사이트 Performance Analysis for Core 2 and K8: Part 1 https://www.realworl[...] 2008-10-28
[21] 서적 z/Architecture Principles of Operation https://publibfp.dhe[...] IBM 2022-05
[22] 웹사이트 IBM zEnterprise BC12 Technical Guide https://www.redbooks[...] IBM 2014-02
[23] 특허 A method and apparatus for branch prediction using a second level branch prediction table
[24] conference Towards a High Performance Neural Branch Predictor http://webspace.ulbs[...] 2010-12-02
[25] 학술지 Towards a Powerful Dynamic Branch Predictor http://webspace.ulbs[...] Romanian Academy 2000
[26] conference Dynamic Branch Prediction with Perceptrons https://www.cs.utexa[...] 2001
[27] 웹사이트 The AMD Trinity Review (A10-4600M): A New Hope http://www.anandtech[...] 2012-05-15
[28] conference Fast Path-Based Neural Branch Prediction http://www.microarch[...] 2018-04-08
[29] 웹사이트 Championship Branch Prediction https://www.jilp.org[...]
[30] conference Hierarchical scheduling windows 2002-12
[31] 웹사이트 AMD Ryzen reviews, news, performance, pricing, and availability https://www.pcgamesn[...] 2017-12-06
[32] 간행물 AMD Takes Computing to a New Horizon with Ryzen™ Processors https://www.amd.com/[...] AMD 2016-12-14
[33] 뉴스 AMD's Zen CPU is now called Ryzen, and it might actually challenge Intel http://arstechnica.c[...] 2016-12-14
[34] 웹사이트 IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism https://people.compu[...]
[35] 웹사이트 S-1 Supercomputer https://people.compu[...]
[36] 서적 Digest of Papers Compcon Spring '90. Thirty-Fifth IEEE Computer Society International Conference on Intellectual Leverage
[37] 간행물 Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor https://citeseerx.is[...]
[38] 웹사이트 Meltdown and Spectre: 'worst ever' CPU bugs affect virtually all computers https://www.theguard[...] 2018-01-04
[39] 서적 Modern processor design: fundamentals of superscalar processors McGraw-Hill Higher Education
[40] 웹사이트 The microarchitecture of Intel, AMD and VIA CPUs http://www.agner.org[...] 2009-10-01
[41] 문서 The Pentium 4 and the G4e: an Architectural Comparison http://arstechnica.c[...] Ars Technica
[42] 문서 一般に分岐予測は繰り返し実行されることを前提としており、あるプログラムを実行開始した直後の予測成功確率はもっと低い
[43] 문서 Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36
[44] 간행물 Two-Level Adaptive Training Branch Prediction ACM 1991
[45] 문서 Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36
[46] 간행물 A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions 2000-10
[47] 간행물 The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference 1997-06
[48] 문서 Combining Branch Predictors http://citeseer.nj.n[...]
[49] 특허 A method and apparatus for branch prediction using a second level branch prediction table
[50] 문서 Championship Branch Prediction http://www.jilp.org/[...]
[51] 문서 IBM Stretch (7030) -- Aggressive Uniprocessor Parallelism http://www.cs.clemso[...]
[52] 문서 S-1 Supercomputer http://www.cs.clemso[...]
[53] 문서 Micro-architecture of the VAX 9000 http://ieeexplore.ie[...]
[54] 문서 Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor http://citeseer.ist.[...]
[55] 웹인용 Dynamic Branch Prediction http://web.engr.oreg[...] 2019-09-09
[56] 웹인용 The Schemes and Performances of Dynamic Branch predictors http://bwrcs.eecs.be[...]
[57] 웹인용 Branch Prediction Techniques and Optimizations http://www.cse.iitd.[...] 2019-09-09
[58] 웹인용 18-447 Computer Architecture Lecture 11: Branch Prediction https://www.ece.cmu.[...] 2019-09-09
[59] 웹인용 Skewed branch predictors https://pdfs.semanti[...] 2019-09-09


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com