Почему бы просто не предсказать обе ветви?

Question

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

Почему бы просто не взять обе ветви? То есть, предположим, что обе ветви будут поражены, кешировать обе стороны, а при необходимости взять правильную. Кэш не должен быть признан недействительным. Хотя для этого требуется, чтобы компилятор загружал обе ветви заранее (больше памяти, правильная компоновка и т. Д.), Я полагаю, что надлежащая оптимизация могла бы упростить обе, чтобы можно было получить почти оптимальные результаты от одного предиктора. То есть, для загрузки обеих веток потребуется больше памяти (что является экспоненциальным для N ветвей), большую часть времени нужно уметь достаточно быстро "переписать" неудачную ветку с новым кодом, прежде чем он завершит выполнение взятой ветви.,

если (х) Bl остальное Br;

Вместо того, чтобы предполагать, что берется Bl, предположим, что взяты и Bl, и Br (некоторый тип параллельной обработки или специального перемежения), и после того, как ветвь фактически определена, одна ветвь становится недействительной, и кеш может быть освобожден для использования (может быть, некоторые Тип специальной техники будет необходимо заполнить и использовать его должным образом).

Фактически, схема предсказания не требуется, и весь проект, используемый для этого, мог бы вместо этого использоваться для обработки обеих ветвей.

Есть идеи, если это возможно?

Answer 1

Историческая перспектива получения инструкций с обоих путей

Первое подобное предложение (насколько мне известно) обсуждалось в этом патенте 1968 года. Я понимаю, что вы спрашиваете только о получении инструкций из обеих веток, но терпите меня немного. В этом патенте были изложены три широкие стратегии, одна из которых идет по обоим путям (сквозной путь и путь ответвления). То есть не только выборка инструкций из обоих путей, но и выполнение обоих путей. Когда инструкция условного перехода разрешается, один из путей отбрасывается. Это было упомянуто только как идея во введении патента, но сам патент был о другом изобретении.

Позже в 1977 году коммерческий процессор был выпущен от IBM, названный процессором IBM 3033. Это первый процессор (насколько мне известно), который реализует именно то, что вы предлагаете. Я удивлен, увидев, что на странице Википедии не упоминается, что процессор извлек инструкции из обоих путей. Документ, описывающий IBM 3033, называется "IBM 3033: взгляд изнутри". К сожалению, я не могу найти газету. Но в статье о IBM 3090 этот факт упоминается. То, что вы предлагаете, имело смысл и было реализовано в реальных процессорах около полувека назад.

Патент был подан в 1981 году и выдан в 1984 году на процессор с двумя запоминающими устройствами, и инструкции могут быть получены из обеих запоминающих устройств одновременно. Я цитирую из аннотации патента:

Микропоследователь с двойной выборкой, имеющий два однопортовых запоминающих устройства микропрограмм, в которых микропроцессоры последовательного адреса и адреса перехода двоичной условной ветви могут быть одновременно предварительно извлечены, по одной из каждой памяти. Микропрограмма собрана таким образом, что адреса последовательных и переходов каждой ветви имеют противоположные нечетные / четные полярности. Соответственно, со всеми нечетными адресами в одной памяти и даже в другой, первая инструкция обоих возможных путей всегда может быть предварительно выбрана одновременно. Когда микрокоманда условного перехода загружается в регистр выполнения, ее адрес перехода или соответствующее ему значение передается в регистр адреса для соответствующей памяти микропрограммы. Адрес микроинструкции в регистре выполнения увеличивается и передается в регистр адреса другой памяти микропрограммы. Задержки предварительной выборки тем самым уменьшаются. Кроме того, когда действительный адрес условного перехода не предоставлен, эта память микропрограммы может быть прозрачно наложена в течение этого микроцикла.

Историческая перспектива получения и выполнения инструкций с обоих путей

В 80-х и 90-х годах было опубликовано много исследований, посвященных предложению и оценке методов, с помощью которых инструкции из обоих путей не только извлекаются, но и выполняются даже для нескольких условных ветвей. Это может привести к дополнительным накладным расходам при извлечении данных, требуемых обоими путями. Идея достоверности предсказания ветвления была предложена в этой статье в 1996 году и использовалась для улучшения таких методов, поскольку они были более избирательными в отношении того, какие пути выбирать и выполнять. В другом документе (Threaded Multiple Path Execution), опубликованном в 1998 году, предлагается архитектура, использующая одновременную многопоточность (SMT) для запуска нескольких путей по условным ветвям. В другом документе (Dual Path Instruction Processing), опубликованном в 2002 году, предлагается извлекать, декодировать и переименовывать, но не выполнять инструкции из обоих путей.

обсуждение

Извлечение инструкций из обоих путей в один или несколько кэшей снижает эффективную емкость кэшей в целом, поскольку, как правило, один из путей будет выполняться гораздо чаще, чем другой (в некоторых, потенциально крайне нерегулярных, шаблонах). Представьте себе загрузку в кэш L3, который практически всегда распределяется между всеми ядрами и содержит как инструкции, так и данные. Это может оказать негативное влияние на способность кэша L3 хранить полезные данные. Загрузка в кэш L2 гораздо меньшего размера может даже привести к существенно худшей производительности, особенно когда L3 включительно. Извлечение инструкций из обоих путей по нескольким условным ветвям для всех ядер может привести к частому извлечению и возврату горячих данных, хранящихся в кешах. Следовательно, экстремальные варианты предлагаемой вами техники могут снизить общую производительность современных архитектур. Однако менее агрессивные варианты могут быть полезны.

Мне не известны какие-либо настоящие современные процессоры, которые извлекают инструкции по обоим путям, когда они видят условную ветвь (возможно, некоторые делают, но это не публично раскрывается). Но предварительная выборка инструкций была тщательно исследована и до сих пор существует. Важный вопрос, который необходимо решить: какова вероятность того, что достаточное количество инструкций из другого пути уже присутствует в кэше, когда предсказанный путь оказывается неверным? Если вероятность высока, тогда будет мало мотивации для получения инструкций с обоих путей. В противном случае, действительно есть возможность. Согласно старой статье Intel (Wrong-Path Instruction Prefetching), в протестированных тестах более 50% инструкций, к которым обращались по непредсказуемым путям, впоследствии были доступны при правильном выполнении пути. Ответ на этот вопрос, безусловно, зависит от целевой области проектируемого процессора.