LINUX.ORG.RU

Процессору можно подсказать наивероятный переход?

 , ,


0

1

Наткнулся в расте на likely/unlikely. Получается в рантайме можно вручную направить CPU в нужный бранч, чтобы он не подключал свои вероятностные нейронки и прочий кремниевый хлам?

А вот интересно, в тех же JIT-ах делается подобная оптимизация, в том же HotSpot джавы?

★★★

свои вероятностные нейронки и прочий кремниевый хлам?

в книжки про процессоры писалось про два бита на адрес, выбранное два раза подряд направление и становится likely

а ещё процессор может оба направления в бранче начать исполнять, а потом неудачный отбросить.

dimon555 ★★★★★ ()

Процессору можно подсказать наивероятный переход?

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

Наткнулся в расте на likely/unlikely.

Они и в C/C++ есть (в ядре Linux появились, еще когда раста даже в задумке не было). Эти подсказки компилятору говорят, какая ветка должна быть в бинарнике скомпилирована сразу за командой перехода, а какая по адресу, куда произойдет переход (но какая ветка кода пойдет в конвейер процессора, решает динамический предсказатель). Таким образом likely ветка будет сразу за командой jCC и с большей вероятностью окажется в кеше, но предсказатель может выбрать unlikely ветку и тогда процессор начнет предвыборку другой ветки.

// какую ветку после jCC prefetch будет считывать - решает динамический предсказатель
    jCC l1
    // likely branch code (more likely to be in code cache)
    jmp end
l1: 
    // unlikely branch code
end:
    // other code 

anonymous ()
Ответ на: комментарий от dimon555

в книжки про процессоры писалось про два бита на адрес, выбранное два раза подряд направление и становится likely

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

anonymous ()
Ответ на: комментарий от anonymous

Современные x86 вообще не пользуются статическим предсказателем, только динамическим.

Странный выбор, по мне так было бы более логично использовать даже не статический предсказатель, а просто включать в команду ожидаемое значение.

В чём причина причина выбора динамических предсказателей?
Мне вот кажется что это просто распил денег потребителей.

torvn77 ★★★★ ()
Ответ на: комментарий от torvn77

Да нет там ничего магического, или подвоха. Ну смотри. Аноним всё правильно пишет. И в большинстве случаев выборка произойдет сразу после команды jCC, но некоторых случаях, обнаруженных интелом с помощью хаков, это не так. И что бы не формализовать эту эвристику поведения, которая ничего тебе не даст, по сути, а является микрооптимизацией на низком уровне, интел оставляет себе пространство для маневра, называя это в документации «динамическим предсказанием».

PtiCa ★★★★★ ()
Ответ на: комментарий от torvn77

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

Скорее ожидаемую ветку. Я тоже мечтаю о такой команде (в дополнение к существующим) или префиксе для существующих условных переходов. Иногда бывают ситуации, когда независимо от частоты выпадения условия нужно предпочтительной сделать всегда определенную ветку. Например при обработке ошибок, когда возвращается optional или пара <result,error> или код типа:

if( have_next() )
    process( get_data() );
else
    wait_for_data();
Тут нужно, чтобы process( get_data() ); загружался в конвейер процессора приоритетно, потому что мне безразлично, сколько потеряется тактов, если на самом деле выпадет ветка wait_for_data();.

anonymous ()
Ответ на: комментарий от PtiCa

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

Тут я хочу уточнить, что динамический предсказатель - это совсем отдельная часть процессора (отдельная от конвейера prefetch->decode->execute->write/commit). В том смысле, что уже на следующем такте после предзагрузки (prefetch) команды условного перехода будет загрузка (prefetch) предсказанной ветки. Т.е. предсказание происходит ДО стадии декодировки команды перехода. Частично поэтому и не используется статический предсказатель.

anonymous ()
Ответ на: комментарий от foror

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

Partisan ()
Ответ на: комментарий от Partisan

более важные и сложные вопросы, чем маргинальная оптимизация скорости

То-то, я запустил один in-memory Хешмап от одного не дурачка хипстера. Всё модно, молодёжно на Котлине даже написано. Вот только работает как черепаха и память у меня всю выжрала моментально, не хватило.

А потом, взял нормальную, оптимизированную Хешмапу, где оптимизации на уровне битов. И всё летает и в память всё влезло, даже осталось еще много свободной.

foror ★★★ ()
Последнее исправление: foror (всего исправлений: 1)
Ответ на: комментарий от foror

Всё модно, молодёжно на Котлине даже написано. Вот только работает как черепаха и память у меня всю выжрала моментально, не хватило.

А потом, взял нормальную, оптимизированную Хешмапу, где оптимизации на уровне битов. И всё летает и в память всё влезло, даже осталось еще много свободной.

Вторая реализация в java некорректна.

slovazap ★★★★★ ()
Ответ на: комментарий от torvn77

Странный выбор, по мне так было бы более логично использовать даже не статический предсказатель, а просто включать в команду ожидаемое значение.

Не «логично», а «так кажется». Не видно в заключениях логики.

А на деле префиксы для статического предсказания переходов уже были реализованы в Pentium 4. В других процессорах эффекта уже не наблюдалось. Не взлетело, видать.

i-rinat ★★★★★ ()

Этот префикс (вероятного бранча) игнорируется в amd, а в intel влияет просто на начальное состояние предсказателя. Так что оптимизация сия сомнительна.

Алсо, в большенстве процов там простая state machine, без всяких нейросетей

deadplace ()
Ответ на: комментарий от dimon555

(кроме общих фраз про нейронные сети).

нет там никаких неройнных сетей, два бита и так больше 90% дают

А чё ты мне это говоришь. Запости баг на документацию в AMD или куда еще...

anonymous ()
Ответ на: комментарий от anonymous

Современные x86 вообще не пользуются статическим предсказателем, только динамическим. Т.е. процессор после выборки команды перехода сразу начнет выбирать одну ветку (какую решит сам на основании своей статистики и повлиять на это нельзя)

А если статистики еще нет (или она уже выкинулась из кэша), то будет использована одна из веток, например первая. Атрибуты likely/unlikely позволяют сгенерировать ассемблер с ветками, идущими в порядке, предпочитаемом данным процом.

annulen ★★★★★ ()
Ответ на: комментарий от deadplace

В Zen появились нейронные сети.

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

khrundel ()
Ответ на: комментарий от dimon555

Простой saturation counter 90% не дает, увы. Но на его основе делают другие предикторы, правда всего битов там куда больше. Вообще сейчас самый вменяемый предиктор, которые многие используют - TAGE.
Вот неплохая презенташка по предикторам: https://www.cs.cmu.edu/afs/cs/academic/class/15740-s17/www/lectures/L19-Branc...

Deleted ()
Последнее исправление: SMD (всего исправлений: 1)