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

Где-то внутри процессора. Что именно делается, зависит от процессора.

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

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

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

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

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

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

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

Метаданные предикторов ветвлений хранятся на кристалле в таблицах предикторов ветвлений. В некоторых исследованиях предлагается хранить их в иерархии кеша (что называется виртуализация предиктора). ), но я не думаю, что это было реализовано в каком-либо реальном процессоре.

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