Предсказание ветвлений

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

Definition

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

Scope

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

Core questions

• Почему ветвления вызывают простой глубоких конвейеров и как предсказание помогает в этом?
• Как динамические предсказатели используют историю ветвлений для повышения точности?
• Что такое буфер целевых адресов ветвлений и что он обеспечивает?
• Каков штраф за ошибочное предсказание и как он компенсируется?

Key concepts

• статическое против динамического предсказания
• одно- и двухбитовые насыщающие счетчики
• история ветвлений и корреляция
• турнирные предсказатели
• буфер целевых адресов ветвлений
• штраф за ошибочное предсказание
• спекулятивная выборка

Key theories

Динамическое предсказание на основе истории

Исходы ветвлений сильно коррелируют с их собственным прошлым поведением и поведением других ветвлений; предсказатели, которые записывают историю в насыщающие счетчики и комбинируют локальную и глобальную историю (коррелирующие и турнирные предсказатели), достигают очень высокой точности.

Mechanisms

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

Clinical relevance

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

History

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

Key figures

• James E. Smith
• Yale Patt
• Tse-Yu Yeh
• John L. Hennessy

Seminal works

• hennessy2019
• patterson2020

Frequently asked questions

Что происходит, когда ветвление предсказано неверно?

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

Насколько точны современные предсказатели ветвлений?

Современные динамические предсказатели обычно превышают 95-процентную точность на типичных рабочих нагрузках, комбинируя локальную и глобальную историю ветвлений. Эта высокая точность делает глубокие, широкие конвейеры целесообразными, поскольку каждое ошибочное предсказание тратит впустую много циклов спекулятивной работы.