ITTAGE 간접 분기 예측기
원문은 Nelson Elhage님이 에 게재했습니다. 이 블로그 구독하기
성능을 조사하던 새로운 Python 3.14 tail-calling 인터프리터 과정에서 나는 (Sam Gross가 남긴 매우 유익한 코멘트를 통해) 내게는 새로웠던 성능 관련 사실 하나를 알게 되었다: 최신 CPU는 더 이상 “전통적인” 바이트코드 인터프리터 루프 안의 바이트코드 디스패치 간접 점프를 예측하는 데 크게 어려움을 겪지 않는다는 것이다. 바이트코드 자체가 어느 정도 안정적이라고 가정하면 정상 상태에서는 최신 CPU가 심지어 “그냥” while / switch 방식의 인터프리터 루프에서도 디스패치를 매우 높은 정확도로 예측한다1!
궁금해진 나는 분기 예측기가 도대체 어떻게 이런 일을 해내는지 찾아보는 데 시간을 좀 썼다. 답이 꽤 흥미로워서, 내가 이해한 핵심적인 상위 수준의 특징들과, 이를 통해 떠오른 흥미로운 연결점과 아이디어들을 공유해 보려 한다.
미리 밝혀두자면, 나는 하드웨어 엔지니어나 CPU 설계자가 아니며, 주로 내가 흥미롭게 느낀 상위 수준의 아이디어에 초점을 맞출 것이다. 아마 틀린 부분도 있을 것이다. 제대로 아는 사람이 쓴 CPU 분기 예측 입문을 원한다면 Dan Luu의 글을 참고하길 바란다.
TAGE와 ITTAGE 분기 예측기
일반적으로 최신 최고 사양 CPU들은 분기 예측기에 대해 그리 자세히 문서화하지 않는 듯하므로, 실제 최첨단 CPU에서 분기 예측이 어떻게 이루어지는지 우리는 알지 못한다 — 적어도 나는 쉽게 찾지 못했다. 하지만 바이트코드 인터프리터 루프를 예측할 수 있을 만큼 실용적인 공개 알고리즘은 (적어도) 하나 존재하는데, 바로 ITTAGE 간접 분기 예측기이며, 이 글에서 다룰 주제가 그것이다. 이 예측기의 저자는 논문을 써서 바이트코드 인터프리터에서의 예측을 탐구하고, 자신의 ITTAGE가 Intel Haswell CPU와 유사한 성능을 보인다는 것을 발견해 그들이 이의 변형을 사용한다고 제안했지만, 확실히 아는 것은 아닌 것 같다.
ITTAGE는 TAGE 예측기의 변형이다. TAGE는 조건부 분기의 taken/not-taken 동작을 예측하고, ITTAGE는 간접 점프의 목적지를 예측한다. 두 예측기는 구조가 매우 유사하므로, 이 글의 대부분에서는 함께 묶어 설명하겠다.
간단 미리보기
본격적으로 들어가기 전에 앞으로 다룰 내용을 간단히 요약하겠다. TAGE와 ITTAGE는 모두:
- (PC, PC 히스토리) -> 과거 동작 매핑을 통해 분기 동작을 예측하고, 미래가 과거와 비슷하리라 가정한다.
- 기하급수적으로 증가하는 히스토리 길이 시리즈를 사용해 이러한 테이블을 다수 저장한다
- 각 분기에 대해 올바른 테이블(히스토리 길이)을 동적으로 선택하려 시도한다.
- 오류가 발생하면 더 긴 히스토리로 적응적으로 이동하고, 유용한 항목을 우선적으로 유지하는 세심한 교체 정책을 사용해 이를 수행한다.
이제 더 긴 버전으로 들어가 보자! 혹은 이 정도로 충분하다면, 앞으로 건너뛰어 이 주제가 나에게 특히 흥미로운 이유에 대한 몇 가지 성찰과 연결점들을 봐도 된다.
동적 분기 예측 기초
많은 동적 분기 예측 알고리즘은 단순한 전제에서 출발한다: 어떤 형태로든 과거 데이터 테이블을 유지하다가, 분기를 예측하라는 요청을 받으면 “지난번에” 무슨 일이 있었는지 조회하고 역사가 반복될 것이라 가정하는 것이다. C++ 풍의 의사코드로 생각하면, 나는 이 접근법을 대체로 다음과 같이 머릿속에서 모델링한다:
struct BranchDetails {
// The information we use to identify a branch
};
struct BranchHistory {
// The information we store about eaach branch
// Predict the outcome of a branch based on past state
bool predict() const { /* ... */ };
// Update our state based on a resolved branch
void update(bool taken) { /* ... */ };
};
// We store a mapping from one to the other. This is a fixed-size chunk of
// hardware, so it stores a fixed number of entries. We'll talk a bit about
// replacement strategy and some details later on.
using PredictorState = FixedSizeMap<BranchDetails, BranchHistory>;
void on_resolve_branch(PredictorState &pred, BranchDetails &branch, bool taken) {
pred[branch].update(taken);
}
bool predict_branch(PredictorState &pred, BranchDetails &branch) {
return pred[branch].predict();
}그렇다면 BranchDetails와 BranchHistory에는 무엇을 쓸까? 아마 가장 단순한 선택은 — 초기 CPU 일부에서 실제로 사용되기도 했다! — 분기를 식별하기 위해 분기 주소만을 사용하고 — 사실상 프로그램 텍스트의 각 분기 명령어마다 상태를 추적하는 셈이다 — 히스토리로는 1비트 정보만을 사용하는 것이다:
struct BranchDetails { uintptr_t addr; };
struct BranchHistory {
bool taken_;
bool predict() { return taken_; }
void update(bool taken) { taken_ = taken; }
};그다음으로 단순한 전략은 분기당 bool 상태를 작은 카운터(최소 2비트!)로 교체해 히스테리시스를 부여하는 것이다. 분기가 해소될 때 카운터를 증가시키거나 감소시키고, 부호를 이용해 예측한다. 알고 보면 대부분의 분기는 한쪽으로 강하게 “치우쳐” 있다 — 예컨대 분기 taken 비율이 10%나 90%인 경우가 50%인 경우보다 훨씬 흔하다 — 그리고 약간의 히스테리시스만 있어도 가끔 튀는 동작을 흡수하면서 우리가 알고 있는 모든 것을 잊지 않을 수 있다:
struct BranchHistory {
int2_t counter_;
bool predict() { return counter_ >= 0; }
void update(bool taken) {
saturating_increment(&counter_, taken ? 1 : -1);
}
};단순한 PC를 넘어서
PC로 분기를 인덱싱하는 것은 단순하고 효율적이지만 한계가 있다. 많은 분기가 동적인 데이터 의존적 행태를 보이며, 더 높은 정확도를 원한다면 어쨌든 더 세밀하게 구분할 필요가 있다.
분기 예측기는 CPU 프론트엔드에 존재하며, 명령어가 실제로 실행되기 훨씬 전 — 어쩌면 완전히 디코딩되기도 전 — 에 예측을 해야 하므로 예측에 활용할 다른 CPU 상태에 대한 접근이 많지 않다. 하지만 사실상 “공짜로” 접근할 수 있는 한 가지 컨텍스트가 있다: 프로그램 카운터와 최근 분기들의 히스토리다. 애초에 예측기가 그것을 생성하는 데 관여했기 때문이다!
따라서 분기 예측기는 고정된 크기의 원형 버퍼를 유지하면서 어떤 형태로든 롤링 “분기 히스토리” 혹은 “PC 히스토리”를 저장하고, 그 상태를 이용해 서로 다른 분기를 구분할 수 있다. 가장 단순한 경우 이전 분기마다 1비트를 저장해, 분기가 taken이면 “1”, not-taken이면 “0”을 기록할 수 있다. 더 정교한 예측기에서는 무조건 분기를 포함하거나, PC 값의 몇 비트를 히스토리에 기록하기도 한다:
constexpr int history_length = ...;
struct BranchDetails {
uintptr_t pc;
bitarray<history_length> history;
}분기 히스토리의 크기 정하기
얼마나 큰 히스토리를 써야 할까? 클수록 항상 좋을까?
더 긴 히스토리를 사용하면 더 많은 패턴, 더 복잡한 패턴을 학습할 수 있다. 동작이 안정적인 프로그램의 경우 정상 상태에서는 더 큰 히스토리가 프로그램 동작을 더 많이 학습하고 서로 다른 상황을 더 세밀하게 구분할 수 있게 해줄 잠재력이 있다.
하지만 더 긴 히스토리는 단순한 패턴을 학습하는 데도 테이블에서 더 많은 공간이 필요하고, 잠재적으로 더 많은 시간이 걸린다는 뜻이기도 하다. 가능한 상태가 더 많아 각각을 개별적으로 마주해야 학습할 수 있기 때문이다. 다음과 같은 단순한 함수를 상상해 보자:
bool logging_active;
void log(const char *msg) {
if (logging_active) {
printf("%s\n", msg);
}
}이 함수가 인라인되지 않고 실행 파일 내 여러 곳에서 호출된다고 가정해 보자.
logging_active가 런타임에 정적이거나 대체로 정적이라고 가정하면 이 분기는 예측 가능성이 매우 높다. 단순한 PC 전용 예측기라면 거의 완벽한 정확도를 달성해야 한다. 하지만 분기 히스토리까지 고려하면 예측기는 더 이상 이 분기를 단일 개체로 “보지” 않는다. 대신 이 분기 명령어에 도달하는 모든 경로를 각각 따로 추적해야 한다. 최악의 경우 k비트의 히스토리를 저장하면 이 하나의 분기에 대해 2^k개의 서로 다른 테이블 항목이 필요할 수도 있다! 더 나쁜 점은 각 상태를 개별적으로 마주해야 하며, 서로 다른 경로로부터는 아무것도 “배우지 못한다”는 것이다.
TAGE 알고리즘: 핵심 아이디어
이제 TAGE 예측기에 대한 설명을 개략적으로 그려볼 만한 배경지식이 갖춰졌다.
TAGE는 내가 설명한 대로 분기 히스토리를 추적하지만, 더 단순한 예측기와 달리 수백, 심지어 수천 비트의 히스토리를 추적해 잠재적으로 매우 긴 거리에 걸친 패턴을 학습할 수 있다.
원치 않는 상태 폭발 없이 이 모든 히스토리를 활용하기 위해 TAGE는 기하급수적 히스토리 길이 시리즈로 인덱싱된 여러 개의 히스토리 테이블(아마 10~20개 정도)을 저장한다(즉, 테이블 N은 어떤 비율 r에 대해 히스토리 길이 \( L_n ≈ L_0\cdot{}r^n \)을 사용한다). 그리고 TAGE는 각 분기에 대해 좋은 예측을 하기에 충분한 가장 짧은 히스토리 길이(와 해당 테이블)를 적응적으로 선택하려 시도한다.
어떻게 그렇게 할까? 핵심 아이디어는 다음과 같다(내가 이해한 바로는). 더 자세히 알고 싶다면 뒤에서 논문과 코드를 링크하겠다!
각 테이블의 태그 비트
지금까지 나는 이러한 조회 테이블이 실제로 어떻게 구현되는지, 특히 “주어진 키로 항목을 조회”하는 것을 구체적으로 어떻게 구현하는지에 대한 질문을 완전히 건너뛰었다.
많은 단순한 분기 예측기에서 히스토리 테이블은 어떤 키를 저장하고 있는지에 대해 “아무것도 모르고”, 그저 키의 일부 비트를 기반으로 직접 인덱싱할 뿐이다.
예컨대 PC로 인덱싱되는 예측기의 경우 \(2^k\)개의 카운터 배열을 두고 PC의 하위 \(k\)비트를 이용해 항목을 선택할 수 있다. 두 분기가 \(2^k\)에 대한 나머지로 같은 주소를 가지면 충돌해 같은 테이블 항목을 사용하게 되며, 우리는 충돌을 감지하거나 다르게 동작하려는 노력을 하지 않는다. 이러한 선택은 테이블을 극도로 저렴하고 효율적으로 만들고, 많은 경우 좋은 트레이드오프가 된다. 직관적으로 우리는 이미 분기 예측기가 틀리는 상황을 처리해야 하며, 이러한 충돌은 틀릴 수 있는 또 다른 이유일 뿐이다. 충돌을 감지하고 대응하려면 더 많은 하드웨어와 저장 공간이 들고, 그 자원을 다른 방식으로 오류율을 낮추는 데 쓰는 편이 더 낫다는 것이 밝혀졌다.
하지만 TAGE는 여러 테이블을 저장하고 서로 다른 분기에 대해 서로 다른 테이블을 사용해야 하며, 이는 결국 주어진 키에 대한 정보를 실제로 저장하고 있는 테이블이 어떤 것인지, 충돌하는 키와 구분해 알아야 함을 의미한다. 따라서 다른 페이로드에 더해 각 테이블 항목은 해당 항목에 어떤 키가 저장되어 있는지를 설명하는 추가 메타데이터 비트를 담는 태그를 저장한다.
(PC, 분기 히스토리) 튜플 T가 주어지면, TAGE는 각 테이블마다 두 개의 서로 다른 해시 함수 H_index와 H_tag를 사용한다. 분기 상태 T는 H_index(T) 인덱스의 테이블에 H_tag(T)의 태그 값과 함께 저장된다. 조회 시에는 H_index(T)의 값을 확인하고 태그를 H_tag(T)와 비교한다.
- 태그가 일치하지 않으면, 이 항목은 현재 다른 분기에 대한 정보를 저장하고 있는 것이므로 사용하지 않는다(단 덮어쓸 수는 있다)
- 태그가 일치하면 이 상태가 우리 분기와 일치한다고 가정하고 이를 사용하거나 업데이트한다. 여전히 해시만 확인하므로 두 해시 모두에서 다른 분기와 충돌했을 가능성도 있지만, 실제로는 이 조건이 충분히 드물도록 설계하고 크기를 선택할 것이다.
이러한 tag 비트가 TAGE라는 이름의 “TA”를 만들고, “GE”는 히스토리 길이의 geometric series에서 온 것이다.
기본 예측 알고리즘
이러한 설정이 주어지면 TAGE의 기본 예측 알고리즘은 꽤 단순하다. 각 테이블 항목은 위에서 설명한 대로 카운터(논문에서는 ctr이라 부른다)를 저장한다 — “branch taken”이면 증가하고 “not taken”이면 감소한다.
예측을 위해 TAGE는 적절한 히스토리 길이를 사용해 모든 테이블을 확인한다. 태그가 일치하는 모든 테이블 항목을 고려한 뒤, 가장 긴 히스토리 길이에 해당하는 일치 항목의 예측을 사용한다.
베이스 예측기 — 가장 단순한 경우 PC로만 인덱싱된 테이블 — 는 태그 비트를 사용하지 않으므로 항상 일치하며, 더 긴 히스토리가 일치하지 않을 때 폴백으로 사용된다.
예측 오류 시 더 긴 히스토리로 이동
분기가 해소되어 정답을 알게 되면 예측기를 업데이트해야 한다.
TAGE는 예측에 사용된 항목의 ctr 필드를 항상 업데이트한다. 하지만 예측이 틀렸을 경우, 더 긴 히스토리 길이를 사용하는 테이블 중 하나에 새로운 항목을 할당하려고도 시도한다. 따라서 목표는 동작하는 길이를 찾을 때까지 동적으로 점점 더 긴 히스토리를 시도하는 것이다.
테이블 항목의 유용성 추적
테이블 항목에 태그가 있으므로 언제 테이블 항목을 교체해 새로운 분기에 재사용할지 결정할 방법이 필요하다. 예측기가 잘 동작하려면 앞으로 유용한 예측을 할 가능성이 높은 항목은 유지하고, 그렇지 않은 항목은 버리는 것을 목표로 한다.
그 목표에 근접하기 위해 TAGE는 어떤 항목이 최근에 유용했는지를 추적한다. 태그와 카운터에 더해 각 테이블 항목은 테이블이 최근에 유용한 예측을 생성했는지를 추적하는 u(“useful”) 카운터(일반적으로 단 1~2비트)도 가진다.
위에서 설명한 대로 새로운 테이블 항목을 할당할 때는 u=0인 슬롯만 덮어쓰고, 새로운 슬롯은 u=0으로 초기화한다. 따라서 새로운 항목은 자신의 가치를 증명해야 하며, 그렇지 않으면 교체될 위험이 있다.
u 카운터는 주어진 테이블 항목이 다음 조건을 만족할 때마다 증가한다:
- 예측에 사용되고,
- 그 예측이 정답으로 밝혀지며,
- 해당 항목의 예측이 그다음으로 긴 히스토리를 가진 일치 항목이 내놓은 예측과 다를 때.
따라서 항목이 정확한 예측을 내놓는 것만으로는 충분하지 않다. 반사실적으로 틀렸을 예측과 다른 올바른 예측을 내놓아야 한다.
또한 항목이 영원히 남아 있는 것을 방지하기 위해 u 카운터는 어떤 형태로든 주기적으로 감소되거나(혹은 그냥 0으로 설정된다). 여기서의 정확한 알고리즘은 공개된 버전마다 많이 다르다.
TAGE에서 ITTAGE로
지금까지 조건부 분기에 대해 1비트 정보(taken/not-taken)를 예측하는 TAGE의 동작을 설명해 왔다. 간접 분기의 타깃을 예측하는 ITTAGE(이 시스템을 다루는 이유 자체다!)는 사실상 동일하며, 주요 변경점은 단지 다음과 같다:
- 각 테이블 항목이 예측된 타깃 주소도 함께 저장한다
- ctr 카운터는 유지되지만 “신뢰도” 카운터가 된다. “정확한 예측”이면 증가하고 “틀린 예측”이면 감소한다. 틀린 예측 시에는 ctr이 최솟값일 때에만 예측된 타깃을 새 값으로 업데이트한다. 따라서 ctr은 이 특정 타깃 주소에 대한 우리의 신뢰도를 추적하고, u는 전체 예측기의 맥락에서 이 항목 전체의 유용성을 추적한다.
실제로 동일한 테이블들을 결합해 논문에서 “COTTAGE”라 불리는 결합 예측기로 만들 수도 있다.
참고 문헌
TAGE와 ITTAGE에 대해 쓰인 글을 엄청나게 많이 찾지는 못했지만, 더 자세히 파고들고 싶은 분들을 위해 내가 찾은 최고의 링크들을 여기에 포함한다! 이 논문들을 읽으면서, 올바른 상위 수준의 아이디어를 가지는 것만으로는 전혀 충분하지 않다는 점이 정말 눈에 띄었다. 고성능 TAGE나 ITTAGE(혹은 어떤 분기 예측기든) 구현은 훌륭한 설계와 엄청난 양의 세심한 튜닝 및 트레이드오프 조율의 결과물이다. 링크는 다음과 같다:
- A case for (partially) tagged geometric history length branch prediction
- 내가 알기로는 이 논문이 TAGE와 ITTAGE를 제안한 논문이다
- The L-TAGE Branch Predictor
- 2007년 분기 예측 대회(“CBP-2”)를 위한 TAGE 구현이다.
- A 64 Kbytes ISL-TAGE branch predictor
- 후속 대회인 2011년 대회(“CBP-3”)를 위한 업데이트 버전의 설명이다.
- A 64-Kbytes ITTAGE indirect branch predictor
- 같은 대회의 간접 분기 트랙을 위한 ITTAGE 예측기에 대한 설명이다.
- The program for JWAC2, which hosted the CBP-3 competition
- 특히 해당 대회에 제출된 TAGE 및 ITTAGE 구현(마이크로아키텍처 시뮬레이터 내)의 소스 코드 링크를 포함하고 있다.
- BOOM (Berkeley Out Of Order Machine)’s documentation on their TAGE implementation
- BOOM은 마이크로아키텍처 연구를 위해 만들어진 오픈소스 RISC-V 코어다.
내가 ITTAGE를 흥미롭게 여기는 이유
한편으로 내가 ITTAGE를 흥미롭게 여기는 이유는 가끔 인터프리터 루프나 비슷한 소프트웨어의 성능에 대해 생각할 일이 있는데, 그것이 그러한 상황을 어떻게 추론해야 하는지에 대한 중요한 업데이트를 의미하기 때문이다. 매우 구체적으로는 지난 글의 CPython 벤치마킹에 영향을 주었다.
하지만 나는 더 넓은 이유와 다른 관심 분야와의 연결성 때문에도 이 주제가 매혹적이라고 생각한다.
나는 과거에 프로그램 카운터의 시간에 따른 행태를 살펴봄으로써 프로그램의 동작을 상당 부분 이해하려는 소프트웨어 도구들(커버리지 가이드 퍼저와 트레이싱 JIT 모두 포함)에 대해 쓴 적이 있으며, 프로그램 상태가 “데이터 속에 숨겨져” 있고 제어 흐름만으로는 “흥미로운” 상태를 제대로 대변하지 못하는 인터프리터 및 유사 소프트웨어에서 그러한 도구들이 — 서로 관련된 방식으로 — 어려움을 겪는 방식에 대해서도 썼다.
그 글에서는 이 연결점에 대해 쓰지 않았지만, 나는 항상 분기 예측기도 이러한 종류의 도구에 속한다고 여겨왔다. 위에서 언급했듯이, 분기 예측기 역시 프로그램 실행을 대부분 “일련의 프로그램 카운터 값”이라는 렌즈를 통해 이해하며, 그들 역시 — 적어도 역사적으로는 — 인터프리터 루프에서 제대로 동작하는 데 어려움을 겪어왔다.
따라서 ITTAGE와 그것이 인터프리터 동작을 예측하는 데 성공했다는 사실을 알게 되면서 자연스럽게 다음과 같은 질문이 떠올랐다: ITTAGE 알고리즘으로부터 다른 도구들을 위해 배울 점은 없을까?
특히 궁금한 것은…
커버리지 가이드 퍼징과 프로그램 상태 탐색을 위한 ITTAGE?
그 이전 글에서 개략적으로 설명했듯이, 커버리지 가이드 퍼징은 후보 입력을 생성한 뒤 어떤 입력이 프로그램에서 “새로운” 동작을 만들어내는지를 관찰함으로써 대상 프로그램의 동작을 자동으로 탐색하려는 기법이다.
이 루프가 동작하려면 프로그램 동작을 특징짓거나 버킷으로 나누는 어떤 방법이 필요하며, 그래야 이미 관찰한 동작과 대비해 무엇이 “새로운” 혹은 “흥미로운” 동작으로 간주되는지를 결정할 수 있다. 이 분야의 최신 최전선에 대해 내가 최신 정보를 갖추고 있지는 않다는 점을 인정하지만, 역사적으로는 PC 값이나 분기(본질적으로 (PC, PC’) 쌍을 의미한다)의 발생 횟수를 세는 “커버리지”와 유사한 메트릭을 이용해 이를 수행해 왔다. 이러한 카운트는 버킷화될 수 있으며, 우리는 실행 중에 생성된 [(PC, bucketed_count)] 값 목록으로 실행을 “지문화”한다.
이 접근법은 실제로는 엄청나게 효과적이다. 하지만 “흥미로운” 상태가 프로그램 카운터나 분기의 집합에 잘 매핑되지 않는 특정 형태의 프로그램 — 종종 인터프리터를 포함한다 — 에서는 어려움을 겪을 수 있다. 이 문제를 보여주는 내가 가장 좋아하는 예시 중 하나는 IJON 논문으로, 몇 가지 구체적인 문제를 보여주고 인간이 추가한 어노테이션을 이용해 이를 해결한다.
그렇다면 나의 질문은 다음과 같다: TAGE/ITTAGE와 같은 접근법이 커버리지 가이드 퍼저가 인터프리터 및 인터프리터와 유사한 프로그램의 상태 공간을 더 잘 탐색하도록 도울 수 있을까? 예를 들어 기존 코퍼스 항목들에 대해 TAGE와 유사한 예측기를 학습시킨 뒤, 예측 오류율에 따라 후보 뮤턴트의 우선순위를 정할 수 있을까? 이를 통해 퍼저가 (예컨대) 인터프리터에만 어노테이션을 추가함으로써 인터프리터 언어로 작성된 코드의 상태 공간을 효과적으로 탐색할 수 있게 될까?
실제적인 과제는 매우 많지만, 원리적으로는 이를 통해 상태 공간을 더 뉘앙스 있게 탐색하고, 긴 범위의 상관관계와 패턴을 통해서만 식별할 수 있는 “새로운 동작”을 발견할 수 있을 것 같다.
TAGE/ITTAGE는 특히 하드웨어 성능 특성과 트레이드오프에 맞춰 설계되고 튜닝되었다는 점을 밝혀둔다. 소프트웨어에서의 성능 지형은 매우 다르므로, 만약 이러한 아이디어가 실제로 동작한다면 세부 사항은 꽤 다르게 보이고 효율적인 소프트웨어 구현에 최적화될 것이라고 생각한다. “분기마다 히스토리 길이를 동적으로 선택한다”는 핵심 아이디어를 차용할 여지는 충분히 있어 보인다.
한층 더 엉뚱한 아이디어는 실제 하드웨어 분기 예측기를 사용하는 것일 수도 있다. 최신 CPU에서는 하드웨어 성능 카운터를 통해 분기 예측 정확도를 관찰할 수 있으며, 기존 예제들의 코퍼스를 실행해 분기 예측기를 학습시킨 뒤 실제 하드웨어의 예측 실패 횟수를 새로움(novelty) 신호로 관찰하는 모습을 상상해 볼 수 있다. 이 접근법 역시 하드웨어 분기 예측기의 불투명성과 이를 명시적으로 제어할 수 없다는 점 등으로 인해 수많은 과제를 안고 있다. 하지만 소프트웨어 예측기보다 훨씬, 훨씬 저렴할 수 있다는 장점이 있다. “예측기 상태 저장 또는 복원” 연산과 같은 형태로 분기 예측기 상태를 명시적으로 노출하는 CPU가 있는지 궁금해지는데, 그런 기능이 있다면 이러한 접근법을 훨씬 더 실현 가능하게 만들 것 같다.
혹시 이와 비슷한 것을 시도한 프로젝트를 아는 분이 있거나 — 혹은 실험해 보고 싶다는 영감을 받은 분이 있다면 — 꼭 알려주시기 바란다.
호기심과 강화 학습
위 섹션에서 설명했듯이, TAGE/ITTAGE와 유사한 알고리즘을 퍼징에 적용하는 방법에 대한 나의 최선의 추측은 “예측 오류”를 보상 신호로 취급하고 예측 오류가 높은 입력에 시간을 할애하는 것이다.
그 아이디어를 곰곰이 생각해 보니, 어느 정도 추상화 수준에서는 강화 학습 분야에서 나온 고전적인 아이디어라서 익숙하게 들린다는 것을 깨달았다!
아마도 가장 주목할 만한 예로, 2018년에 OpenAI는 환경으로부터의 보상 신호가 없는 경우에도 탐색을 장려하는 보상 항을 추가해 강화 학습을 강화하는 기법을 탐구하는 “호기심 기반 학습(curiosity-driven learning)”에 관한 두 편의 논문을 발표했다. 두 논문은 접근법의 세부 사항에서는 다르지만 기본 아이디어는 동일하다: 취할 행동을 결정하는 정책 네트워크와 함께, 환경의 어떤 특징이나 행동의 결과를 예측하려는 예측 네트워크를 학습시킨다. 그리고 높은 예측 오류를 가진 행동이나 상태를 발견한 정책 모델에 보상을 주어 — 모든 것이 잘 풀린다면 — 환경의 새로운 부분을 탐색하도록 장려하는 것이다.
내가 아는 한 이 기법은 꽤 잘 동작했다. 두 번째 논문은 강화 학습 알고리즘에게는 악명 높게 어려웠던 아타리 게임인 Montezuma’s Revenge에서 최첨단 성능을 달성했는데, 이 게임은 점수를 받기 전에 열쇠와 장비를 광범위하게 탐색하고 조작해야 하기 때문이다. 하지만 그 작업과 접근법의 이후 궤적이 어떻게 되었는지는 지금 당장 기억나지 않는다.
나는 그 논문들을 알고 있었고 당시 그 연구를 따라가기도 했지만, 머릿속에서 “ITTAGE”와 “커버리지 가이드 퍼징” 조각들을 맞춰보려 할 때는 의식적으로 떠올리지 못하고 있었다. 이러한 합류는 내게 뭔가 있을지도 모른다는 생각을 하게 한다. 물론 동시에 2025년에는 맞춤형으로 설계·튜닝된 예측 알고리즘 대신 그냥 신경망을 문제에 던지는 편이 더 쉬울지도 모른다!
각 opcode에 디스패치 로직을 복제하는 “threaded” 방식의 인터프리터는 여전히 성능상 이득이 되지만 과거 CPU에서만큼은 아니다. 요즘의 이득은 대부분 총 명령어 수, 특히 분기 수를 더 적게 실행하기 때문이다. 내 이전 글에 추가 논의가 있다. ↩︎
댓글
로그인하고 댓글 남기기