Где/как хранятся данные прогноза ветвления?

Question

Я всегда задавался вопросом, где/как хранятся данные прогнозирования? Есть ли предел? Это только последние отрасли? Меня больше всего интересует архитектура Intel, но все, что я могу узнать о любой архитектуре, оценивается.

Answer 1

Где-то внутри процессора. То, что точно сделано, зависит от процессора.

В очень простом случае вы можете взять 4096 бит данных предсказания ветвления. Затем для каждой ветви вы берете последние 12 бит адреса ветки, которая дает 4096 разных значений и принимает это как индекс в данные прогноза ветвления. И поскольку у вас есть только один бит данных, вы просто сохраняете, была ли занята последняя ветка.

Преимущество в том, что это очень дешево. Недостатком является то, что две ветви, точно равные 4096 байт, используют одну и ту же запись в таблице. Поэтому, если ваш код выполняет эти две ветви все время, и один всегда берется, а один никогда не берется, предсказание ветви довольно плохое.

Некоторые процессоры используют два бита для каждой ветви, что означает «сильные взятые», «взятые», «не приняты», «сильные не приняты». Каждый раз, когда ветвь берется, предсказание движется к «сильному взятому», если ветвь не взят, она движется к «сильному не взятому». Это работает лучше, если ветви обычно берутся за редким исключением.

Некоторые процессоры не просто используют последние 12 или более бит адреса филиала, но они смешиваются в том, говорят ли последние четыре ветки. Скажем, у вас есть код

if (x >= 0) { ... } 
if (x <= 0) { ... } 

и x редко 0, но довольно случайным образом положительным или отрицательным. Тогда первая ветвь трудно предсказать, но вторая никогда не берется после первого взятия и всегда берется, если первая не берется. Смешивая эту информацию, вы используете две записи в таблице прогноза ветвления для второй ветви, но предсказание для второй ветви будет очень точной, даже если ветвь случайным образом взята или не принята.

У вас всегда возникает проблема, что одна и та же запись в таблице прогноза ветвления будет использоваться для нескольких ветвей; вы просто живете с этим. (Делать что-нибудь умное, чтобы справиться с этим, потребовалось бы слишком много хранения. Мы используем 1 или 2 бит на предсказание ветвлений, поэтому у нас могут быть массивные таблицы с очень небольшим объемом памяти).