Прогнозирование ветвей

Возможный дубликат:
Можно ли сказать предсказателю ветвления, насколько вероятно, что он последует за ветвью?

Итак, если предсказание ветвлений играет такую ​​большую роль («Предикторы ветвлений играют решающую роль в достижении высокой эффективной производительности во многих современных конвейерных архитектурах микропроцессоров, таких как x86». wiki), имеет смысл, что должен быть способ оптимизировать и помочь этому, не так ли?

Я задам свой вопрос прямо:
Можете ли вы сказать предсказателю ветвления, какой маршрут вы, скорее всего, выберете?

Приведу пример:

Моя программа каждый раз при загрузке проверяет, запускает ли ее пользователь впервые. Скорее всего, кэшировать следует ветку с пометкой «это не в первый раз».

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

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


assembly micro-optimization
person MasterMastic    schedule 23.12.2012    source источник
comment
@CarlNorum Это для C. Я прошу ASM.   -  person MasterMastic    schedule 23.12.2012
comment
Однако в соответствии с этим вопросом есть инструкция подсказки ветки, но это NOP на архитектурах после Netburst.   -  person Colin Valliant    schedule 23.12.2012
comment
Со временем и C, и сборка превращаются в машинные инструкции.   -  person Carl Norum    schedule 23.12.2012
comment
@CarlNorum Да, с компиляцией. Я не знаю, как сам скомпилировать там код.   -  person MasterMastic    schedule 23.12.2012

Ответы (4)


arrow_upward
2
arrow_downward

Это для C. Я прошу ASM

Это означает, что вам придется реализовать семантику __builtin_expect самостоятельно. Это не сложно, просто неудобно. Если предиктор ветвления не имеет истории для ветки, тогда он будет предполагать, что ветвь выполняется, когда ветвь идет назад, и не выполняется, когда она идет вперед.

Таким образом, вам, возможно, придется реструктурировать свой код, используя противоположное условие в инструкции ветвления и переместить код, чтобы приспособиться к этому. Безусловный переход вперед с условной обратной ветвью является обычным явлением, например, как компилятор C реализует цикл for ().

person Hans Passant    schedule 23.12.2012

arrow_upward
2
arrow_downward

«В случае необходимости подсказки ветвления, следующие префиксы инструкций могут быть добавлены перед инструкцией ветвления, чтобы изменить способ поведения статического предсказателя: 0x3E - статически предсказывать ветвление как взятое 0x2E - статически предсказывать ветвление как незанятое»

http://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts

person Bartosz Wójcik    schedule 23.12.2012

arrow_upward
1
arrow_downward

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

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

person Mike Duigou    schedule 23.12.2012

arrow_upward
1
arrow_downward

Некоторая важная оптимизация предсказания ветвления сборки, Источник: wiki

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

Безусловные переходы могут быть неверно предсказаны, а инструкции загрузки, следующие за переходами, могут быть декодированы и вызывать доступ к кэш-памяти. Избегайте размещения инструкций по загрузке после ветвей, если вы не намерены ЦП предварительно выбирать адреса, на которые они ссылаются.

Хотя инструкции декодируются попарно, предсказатель ветвления может прогнозировать только одну цель ветвления за цикл. Если у вас есть условная ветвь, за которой сразу следует другая ветвь, и первая ветвь, вероятно, будет выполнена, поместите инструкцию без операции между ветвями, чтобы предотвратить декодирование и предсказание второй ветки. Вставка NOP вредна, если первая ветвь используется нечасто.

person Sunil Bojanapally    schedule 23.12.2012