Использование SIMD на amd64, когда лучше использовать больше инструкций или загружать из памяти?

Ответ 1

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

Причина, по которой ваш микро-тест указывает на то, что подход на основе LUT быстрее, потому что весь LUT загружается в кеш и никогда не выдается. Это делает его использование эффективно бесплатным, так что вы сравниваете выполнение 8 и 30 инструкций. Ну, вы можете догадаться, какой из них будет быстрее.:-) На самом деле вы догадались об этом и доказали это с явным недействительным кэшем.

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

Другая скрытая стоимость (больших) LUT заключается в том, что они рискуют выдать код из кеша, поскольку большинство современных процессоров имеют единые кэши данных и команд. Таким образом, даже если реализация на основе LUT немного быстрее, у нее очень сильный риск замедления всего остального. Микрообъект не покажет это. (Но на самом деле бенчмаркинг вашего реального кода будет, так что всегда хорошо делать, когда это возможно. Если нет, читайте дальше.)

Мое эмпирическое правило состоит в том, что если подход на основе LUT не является явным выигрышем в производительности над другим подходом в реальных тестах, я его не использую. Похоже, это так. Если результаты тестов слишком близки к вызову, это не имеет значения, поэтому выберите реализацию, которая не раздувает ваш код на 4k.

Ответ 2

Cody Gray уже покрыл большинство оснований выше, поэтому я просто добавлю несколько своих собственных мыслей. Обратите внимание, что я не так отрицателен на LUT как Cody: вместо того, чтобы давать им общий "большой палец", я думаю, вам нужно тщательно проанализировать недостатки. В частности, чем меньше LUT, тем более вероятно, что его можно сравнить с яблоками для яблок с подходом к вычислению.

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

SIMD

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

Для кода SIMD LUT имеют некоторые преимущества, а также дополнительные недостатки. Главный недостаток заключается в том, что за пределами обтекания PSHUFB -типа, обсуждаемого ниже, нет хорошего эквивалента SIMD для скалярного кода LUT. То есть, в то время как вы можете делать N (где N - ширина SIMD), параллельные независимые вычисления для каждой команды с использованием SIMD, вы обычно не можете выполнять N поисков. Как правило, вы ограничены одним и тем же количеством запросов на цикл в SIMD-коде, так как вы находитесь в коде LUT, причем 2/цикл является общим числом современного оборудования.

Это ограничение - это не просто некоторый надзор в SIMD ISAs - это довольно фундаментальный результат того, как создаются кэши L1: у них только очень небольшое количество портов чтения (как указано выше, 2 является общим), и каждый добавленный порт значительно увеличивает размер L1, энергопотребление, задержку и т.д. Таким образом, вы просто не увидите, что процессоры общего назначения предлагают 16-портовые нагрузки из памяти в ближайшее время. Вы часто видите инструкцию gather, но она не обойти это фундаментальное ограничение: вы все равно будете ограничены лимитом 2-х нагрузок за цикл. Самое лучшее, на что вы можете надеяться в gather, состоит в том, что он может заметить, когда две нагрузки имеют один и тот же адрес (или, по крайней мере, "достаточно близко" ), так что они могут быть удовлетворены одной и той же нагрузкой ⁶.

Что SIMD позволяет вам делать, это более широкие нагрузки. Таким образом, вы можете загрузить сразу 32 последовательных байта. Обычно это не полезно для прямого векторизации скалярного поиска, но он может включать некоторые другие трюки (например, вектор может сам по себе посредством таблицы, и вы выполняете второй поиск, используя материал "LUT in register", как описано ниже).

С другой стороны, LUT часто обнаруживают новую нишу в SIMD-коде, потому что:

• Тот факт, что вы векторизовали код, означает, что вы, вероятно, ожидаете умеренный или большой размер проблемы, что помогает амортизировать затраты на кеширование LUT.

• Больше, чем скалярный код, SIMD любит загружать множество масок и других констант: однако часто бывает сложно вычислить такие вещи, как маски с тасованием, с помощью "вычисления", поэтому LUTs часто пригодится здесь.

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

• Наборы инструкций SIMD часто имеют команды перетасовки/перестановки, которые могут быть переназначены в функциональность "поиск в регистре", как описано ниже.

Одна вещь, о которой следует помнить при выполнении LUT в SIMD-коде, - это небольшая таблица. Вы можете избежать записи таблицы шириной 16 или 32 байта, если сможете. В дополнение к методам сокращения таблицы ниже, вы можете часто размещать широковещательные или "распакованные" инструкции для хорошего использования здесь, если записи имеют некоторую регулярность. В некоторых случаях (последние x86) такие команды могут быть "свободными" при замене простой нагрузки.

Проблема с дополнительным решением

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

Если вы делаете серию решений по оптимизации, основанных на контрольных показателях, каждый раз применяя "лучший" подход, основанный на реальных тестах, более поздние решения могут аннулировать предыдущие. Например, скажем, вы рассматриваете возможность использования LUT или вычисления для функции A. Возможно, вы обнаружите, что в реальном мире LUT выполняется несколько быстрее, поэтому вы реализуете это. На следующий день вы тестируете новые реализации функции B, снова с помощью подхода LUT и вычислений - вы можете снова обнаружить, что LUT лучше, чем вычисление, поэтому вы реализуете это, но если вы вернетесь и протестируете A, результаты могут быть другой! Теперь A может быть лучше с помощью метода вычисления, поскольку добавление LUT для функции B вызвало увеличение конкуренции с кешем. Если бы вы оптимизировали функции в обратном порядке, проблема не возникла бы ².

Итак, в принципе, функции A и B должны быть оптимизированы вместе, и этот же принцип может часто применяться ко всей программе. Кроме того, ваши решения для A и B также влияют на некоторую гипотетическую будущую функцию C, даже не написанную, которая может также понравиться делать некоторые поисковые запросы и может еще лучше использовать ограниченное пространство кеша, чем A или B.

Все, что нужно сказать, что вам не нужно просто ориентироваться в реальном сценарии, вам нужно сохранить влияние на существующие функции и даже на будущие функции.

Баллы LUT Оценки

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

Например, возьмите некоторый номер шарика для промаха в кэше для DRAM, например, 200 циклов, а затем вы можете оценить наихудшую производительность LUT для различных размеров итераций вашего алгоритма. Например, если подход LUT занимает 10 циклов, когда он попадает в кеш, против 20 циклов для подхода к вычислению и имеет таблицу из 640 байт (10 строк кэша), тогда вы можете заплатить стоимость 10 * 200 = 2000 циклов для ввода всего LUT, поэтому вам нужно повторить по меньшей мере около 200 раз, чтобы заплатить эту стоимость. Вы также можете удвоить стоимость пропусков кеша, так как доведение LUT до кэша, по-видимому, часто также приводит к пропуску нисходящего потока для любой строки, которая была высечена.

Таким образом, вы можете иногда сказать: "Да, LUT имеет худшую стоимость X циклов из-за эффектов кеша, но мы почти всегда платим за это, потому что мы обычно называем метод Y раз с экономией Z циклов/колл".

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

I-Cache Misses

Одна вещь, которая не часто упоминается в дискуссии LUT и вычисления, - это эффект на я $. Некоторые программы, особенно большие объектно-ориентированные или веткистые ⁴ более чувствительны к давлению кэша команд, чем давление кэша данных. Если подход, основанный на вычислении, принимает значительно более статические инструкции (т.е. Кодовую сторону, не выполненный счетчик команд), он может несколько способствовать LUT. Тот же аргумент может быть сделан, например, при принятии решения о разворачивании или агрессивном векторизации циклов или нет.

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

Гибридные подходы

Часто то, что сравнивается, - это подход с чистым LUT и вычислением. Часто есть средняя площадка, где вы можете использовать гораздо меньший LUT в сочетании с некоторыми вычислениями.

Это вычисление может возникнуть перед поиском, когда вы сопоставляете входной домен с индексом с меньшим доменом, так что все входы, сопоставленные с одним и тем же индексом, имеют одинаковый ответ. Простым примером может быть вычисление четности: вы можете сделать это "быстро" (в микро-контрольном смысле!) С помощью таблицы поиска 65K, но вы также можете просто скомпоновать ввод как input ^ (input >> 8), а затем использовать нижний байт для индекс в таблицу с 256 входами. Таким образом, вы сокращаете размер таблицы в 256 раз за счет еще нескольких инструкций (но все же довольно быстро, чем полный подход к вычислению).

Иногда вычисление происходит после поиска. Это часто принимает форму хранения таблицы в немного более "сжатом" формате и декомпрессии вывода. Представьте себе, например, какую-то функцию, которая отображает байт в булев. Любая такая функция может быть реализована с помощью lut bool[256], стоимостью 256 байт. Однако для каждой записи действительно нужен только один бит (всего 32 байта), а не один байт - если вы захотите "распаковать" после поиска, например return bitwise_lut[value] & (1 << (value & 7)).

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

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

Уменьшение пропусков кэш-памяти

До сих пор довольно ясно, что основным фактором, затрудняющим измерение эффективности алгоритма LUT, является влияние кэша. Есть ли какие-либо трюки помимо вышеизложенного, которые мы можем использовать для их сокращения?

Расположение LUT рядом с кодом

В принципе, это похоже на очень маленькие LUT, вы можете просто поместить LUT в ту же строку кэша, что и код. Это лучше всего работает, если ваш LUT несколько меньше, чем строка кэша; в частности, он лучше всего работает, если добавление его к размеру функции не изменяет общее количество строк кэша для комбинированного кода LUT +, но может по-прежнему иметь небольшие преимущества, даже если это не так. ⁵.

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

LUT в регистрах GP и SIMD

Крайняя версия подхода "поместить LUT рядом с кодом" заключается в том, чтобы найти LUT в коде. В скалярном коде вы можете сделать это, загрузив константу в регистр и затем сделав что-то вроде переменной shift-and-mask, чтобы выделить элемент в регистре. Например, вы можете использовать регистр как 16-элементный логический LUT для вычислять паритет.

В общем случае N-разрядный универсальный регистр может использоваться для реализации LUT, который не превышает N бит. Таким образом, 64-разрядный регистр может реализовать 8-элементные LUT для байтовых значений или 64-элементный LUT для логических значений и т.д.

В мире x86-64 SIMD вы можете довести эту идею до предела с помощью инструкции PSHUFB (сначала доступной в SSSE3). В своем 128-битном воплощении SSE он позволяет эффективно выполнять 16 параллельных 4-битных и 8-битных поисков за один цикл. Версия AVX2 позволяет выполнять 32 таких поиска параллельно. Таким образом, вы можете выполнять поиск на стероидах без большинства недостатков реального LUT (т.е. Таблица хранится в регистре, хотя вам может понадобиться одна нагрузка, чтобы получить ее там в первую очередь).

Это работает только для небольших (16-элементных таблиц) - хотя вы можете расширить это до 32, 64 и т.д., таблицы элементов с операциями 2, 4,..., PSHUFB и аналогичное количество операций смешивания, но это все еще возможно только для довольно небольших таблиц.

¹ Возможно, вы также можете назвать это "проблема с зависящей от пути оптимизации" или "неаддитивная оптимизация".

²Разумеется, зная, что оптимизация B тогда A сработала бы в этом случае, имеет больший академический интерес, чем практическое значение, поскольку не существует хорошего способа заранее знать правильный порядок.

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

⁴ Приходят на ум компиляторы, браузеры и всевозможные коды JIT'а.

⁵ Например, используя строку кэша, которая вводится путем последовательной предварительной выборки, которая в противном случае могла бы быть потрачена впустую, или, по крайней мере, для определения кода и LUT на одной странице 4K, возможно, сохранение промах TLB.

⁶ Стоит отметить, что на Intel, несмотря на то, что он существует как минимум для 4 новых выпусков чипов, gather все еще не делает этого: он ограничен, в лучшем случае, 2 раза в день цикл, даже если в загруженных индексах происходит дублирование.