Оптимизация предварительной загрузки в X86: многопоточный код "computed goto"
У меня есть довольно нетривиальная проблема, где у моего вычислительного графа есть циклы и несколько "вычислительных путей". Вместо того, чтобы делать цикл диспетчера, где каждая вершина будет называться один за другим, у меня была идея поместить все заранее выделенные "объекты кадра" в кучу (код + данные).
Это несколько похоже на многопоточный код (или даже лучше: CPS), просто перепрыгивая через кучу, выполняя код. Каждый фрагмент кода связан со своим собственным "указателем кадра" в куче и использует данные, относящиеся к этому. Кадры остаются всегда выделенными. Код просто создает побочные эффекты в известных местах, вычисляет (при необходимости) следующее значение goto и переходит туда.
Я еще не пробовал (это будет серьезное обязательство, чтобы исправить это, и я полностью осознаю все трудности), поэтому я хотел спросить экспертов по оборудованию x86: может ли это быть быстрее, чем цикл диспетчера? Я знаю, что есть несколько оптимизаций для инструкций call/ret, происходящих в аппаратном обеспечении.
Есть ли разница между доступом к данным относительно указателя стека или любого другого указателя? Есть ли предварительная выборка для косвенного перехода (переход к значению, хранящемуся в регистре?).
Эта идея даже жизнеспособна?
PS Если вы читали это и все еще не могли понять, что я имею в виду под этой идеей (извините за неудачные попытки объяснить вещи), представьте себе это целое как набор из множества предварительно распределенных сопрограмм в куче, которые уступают друг другу. Стандартный стек x86 не используется в процессе, так как все в куче.
1 ответ
Переход непосредственно от блока к блоку часто является выигрышным для предсказания ветвления, а не возврата к одному родительскому косвенному ветвлению, особенно на процессорах старше Intel Haswell.
С переходами из хвоста каждого блока каждая ветвь имеет свою историю предикторов ветвления. Вероятно, для данного блока обычно свойственно переходить к тому же следующему блоку или иметь простой шаблон пары целевых адресов. Это часто можно хорошо предсказать, поскольку каждая ветвь в отдельности имеет более простой шаблон, а история ветвей распределяется по нескольким веткам.
Если вся диспетчеризация происходит из одной непрямой ветви, для нее может быть только одна запись BTB (целевой буфер ветвления), и шаблон будет слишком сложным, чтобы он мог хорошо прогнозировать.
Современные предикторы ветвей TAGE в Intel Haswell и более поздних индексах BTB, использующие недавнюю историю ветвлений, в том числе адресаты косвенных ветвлений, фактически решают эту проблему. См. Комментарии об издержках индексированной ветви в 64-битном режиме X86 и выполните поиск Haswell в https://danluu.com/branch-prediction/
В частности, предсказание ветвлений и эффективность интерпретаторов - не доверяйте фольклору (2015) Роу, Свами и Сезнека сравнивает Nehalem, SandyBridge и Haswell с эталонными показателями интерпретатора и измеряет фактическую частоту ошибочных прогнозов для циклов диспетчеризации с помощью одного switch заявление. Они считают, что Haswell работает намного лучше, вероятно, используя предиктор ITTAGE.
Они не тестируют процессоры AMD. Со времени Piledriver AMD опубликовала некоторую информацию о своих процессорах, используя нейронные сети Perceptron для прогнозирования ветвлений. Я не знаю, насколько хорошо они обрабатывают диспетчерские циклы с одной косвенной ветвью.
Darek Mihocka обсуждает этот паттерн в контексте интерпретатора эмулятора ЦП, который переходит от блока к блоку обработчиков для различных инструкций (или упрощенных мопов). Он подробно рассказывает о производительности различных стратегий на Core2, Pentium4 и AMD Phenom. (Было написано в 2008 году). Современные предсказатели ветвления на современных процессорах больше похожи на Core2.
В конце концов он представляет то, что он называет шаблоном Nostradamus Distributor для проверки раннего выхода (функции возвращают указатель функции или "пожарный выход", страж), дружественным к предсказанию ветвления. Если вам это не нужно, просто посмотрите в начале статьи, где он говорит о прямом сцеплении переходов между блоками и центральным распределителем.
Он даже оплакивает отсутствие инструкции предварительной выборки кода в x86. Вероятно, это была большая проблема с Pentium4, где первоначальное декодирование для заполнения кэша трассировки было очень медленным по сравнению с запуском из кэша трассировки. В семействе Sandybridge есть кэш декодированного типа, но это не кэш-память трассировки, и декодеры все еще достаточно сильны, чтобы не сосать, когда кэш-память UO пропускает. Ризен похож.
Есть ли разница между доступом к данным относительно указателя стека или любого другого указателя?
Нет, вы могли бы даже установить rsp после прыжка каждый блок может иметь свой собственный стек. Если у вас установлены обработчики сигналов, rsp необходимо указать на действительную память. Кроме того, если вы хотите иметь возможность call любые нормальные функции библиотеки, вам нужно rsp работать как указатель стека, потому что они захотят ret,
Есть ли предварительная выборка для косвенного перехода (переход к значению, хранящемуся в регистре?).
Предварительная выборка в L2 может быть полезна, если вы знаете целевой адрес ветви задолго до того, как будете готовы выполнить косвенный переход. Все текущие процессоры x86 используют разделенные кэши L1I / L1D, поэтому prefetcht0 будет загрязнять L1D без выгоды, но prefetcht1может быть полезным (получить в L2 и L3). Или это может быть бесполезно, если код уже горячий в L2.
Также полезно: вычислять целевой адрес перехода как можно раньше, чтобы выполнение по порядку могло разрешить переход, в то время как большая часть работы была поставлена в очередь в ядре не по порядку. Это минимизирует потенциальный пузырь в трубопроводе. Держите расчет независимо от других вещей, если это возможно.
Наилучшим случаем является адрес в реестре за много инструкций доjmpтак что как толькоjmpполучает цикл на порте выполнения, он может предоставить правильное назначение внешнему интерфейсу (и переадресовать, если предсказание ветвления ошибочно). В худшем случае цель ветвления является результатом длинной цепочки зависимостей инструкций непосредственно перед ветвью. Пара независимых инструкций и / или скачок памяти - это нормально; Внеочередное выполнение должно найти циклы для выполнения этих инструкций, когда они находятся в планировщике OOO.
Существуют также разделенные L1iTLB и L1dTLB, но L2TLB обычно унифицирован на большинстве микроархитектур. Но IIRC, L2TLB работает как кэш-память жертвы для TLB L1. Предварительная выборка может инициировать просмотр страницы для заполнения записи в TLB данных L1, но на некоторых микроархитектурах, которые не помогут избежать пропуска iTLB. (По крайней мере, данные самой таблицы страниц будут передаваться в L1D или, возможно, во внутренние кэши каталогов страниц в оборудовании для обхода страниц, поэтому еще один просмотр страницы для той же записи будет быстрым. Но поскольку процессоры отличаются от Intel Skylake (и более поздних версий) иметь только 1 аппаратный блок просмотра страниц, если пропадание iTLB происходит во время первого обхода страницы, возможно, оно не сможет запуститься сразу, поэтому может причинить вред, если ваш код настолько разбросан, что вы пропускаете iTLB.)
Используйте 2MB огромных страниц для фрагмента памяти, в который вы будете использовать JIT, чтобы уменьшить потери TLB. Вероятно, лучше всего выложить код в довольно узкой области, с отдельными данными. Эффекты локальности DRAM реальны. (Я думаю, что страница DRAM обычно больше, чем 4 КБ, но это аппаратная вещь, и вы не можете выбирать. Это меньшая задержка для доступа на уже открытой странице.)
См . Pdf, посвященный Agner Fog, а также руководство по оптимизации Intel., (И руководство AMD тоже, если вы беспокоитесь о процессорах AMD). Больше ссылок смотрите в теге x86 wiki.
Эта идея даже жизнеспособна?
Да, возможно.
Если возможно, когда один блок всегда переходит на другой блок, исключите прыжок, сделав блоки смежными.
Относительная адресация для данных проста: x86-64 имеет RIP-относительную адресацию.
Вы можете lea rdi, [rel some_label] а затем индексировать оттуда, или просто использовать RIP-относительную адресацию напрямую для некоторых ваших статических данных.
Вы собираетесь JITting свой код или что-то в этом роде, поэтому просто рассчитайте смещения со знаком от конца текущей инструкции до данных, к которым необходимо получить доступ, и это ваше относительное смещение RIP. Независимый от позиции код + статические данные легко в x86-64.