Подсчет FLOP для библиотечных функций

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

Под специальными функциями мы подразумеваем такие вещи, как:

• ехр ()
• SQRT ()
• грех / соз / тангенс ()

которые обычно предоставляются системными библиотеками.

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

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

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

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

Аппаратно поддерживаемые операции с плавающей запятой

Этот чип поддерживает инструкции AVX , поэтому регистры имеют длину 32 байта (содержит 4 двойных). Суперскалярная архитектура позволяет инструкциям перекрываться, причем большинство арифметических инструкций выполняется за несколько циклов, даже если новая инструкция может быть запущена в следующем цикле. Эта семантика обычно сокращается путем записи задержки / обратной пропускной способности, значение 5/2 будет означать, что для выполнения инструкции требуется 5 циклов, но вы можете начинать новую инструкцию каждый второй цикл (при условии, что операнды доступны, поэтому нет данных зависимость и не дожидаясь памяти).

Существует три арифметических единицы с плавающей запятой на ядро, но третья не имеет отношения к нашему обсуждению, мы назовем соответствующие две единицы A и M, потому что их основными функциями являются сложение и умножение. Пример инструкции (см . Таблицы Агнера Фога )

• vaddpd: сложенное сложение, занимающее блок А в течение 1 цикла, задержка / обратная пропускная способность 3/1
• vmulpd: упакованное умножение, единица М, 5/1
• vmaxpd: упаковано выбрать попарно максимум, единица A, 3/1
• vdivpd: упакованное деление, единица М (и немного А), от 21/20 до 45/44 в зависимости от входа
• vsqrtpd: упакованный квадратный корень, некоторые A и M, 21/21 до 43/43 в зависимости от входа
• vrsqrtps: упакованный обратный квадратный корень низкой точности для ввода с одинарной точностью (8 floats)

Точная семантика того, что может перекрываться vdivpdи vsqrtpd, по-видимому, неуловима и AFAIK, нигде не документирована. В большинстве случаев я думаю, что вероятность перекрытия невелика, хотя формулировка в руководстве предполагает, что в этой инструкции несколько потоков могут предложить больше возможностей для перекрытия. Мы можем достичь пиковых флопов, если мы начнем a vaddpdи vmulpdна каждом цикле, всего 8 флопов за цикл. Плотная матрица-матрица multiply ( dgemm) может быть достаточно близко к этому пику.

При подсчете флопов для специальных инструкций я бы посмотрел, сколько заняты FPU. Предположим для аргумента, что в вашем диапазоне ввода vdivpdпотребовалось в среднем 24 цикла для завершения, полностью занимая модуль M, но сложение могло (если оно было доступно) выполняться одновременно для половины циклов. FPU способен выполнять 24 упакованных умножения и 24 упакованных сложения в течение этих циклов (с идеальным чередованием vaddpdи vmulpd), но при vdivpdэтом лучшее, что мы можем сделать, - это 12 дополнительных упакованных сложений. Если мы предположим, что лучший способ сделать деление - это использовать аппаратное обеспечение (разумное), мы можем посчитать vdivpd36 упакованных «флопов», указывая, что мы должны считать каждое скалярное деление как 36 «флопов».

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

y *= (3 - x*y*y)*0.5;

Если многие из этих операций необходимо выполнить, это может быть значительно быстрее, чем наивная оценка y = 1/sqrt(x). До появления аппаратного приблизительного квадратного корня, некоторый чувствительный к производительности код использовал печально известные целочисленные операции, чтобы найти начальное предположение для итерации Ньютона.

Предоставляемые библиотекой математические функции

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

Я предлагаю использовать хорошую библиотеку векторной математики в качестве основы (например, VML от Intel, часть MKL). Измерьте количество циклов для каждого вызова и умножьте на пиковые достижимые провалы за это количество циклов. Поэтому, если для оценки упакованной экспоненты требуется 50 циклов, посчитайте, что она равна 100 флопсам, умноженным на ширину регистра. К сожалению, библиотеки векторной математики иногда трудно вызвать и не имеют всех специальных функций, поэтому вы можете в конечном итоге делать скалярную математику, и в этом случае вы будете считать нашу гипотетическую скалярную экспоненту 100 флопсами (даже если это, вероятно, все еще занимает 50 циклов, так что вы получите только 25% «пика», если все время тратится на оценку этих показателей).

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

Вы можете рассчитывать их на реальных системах, используя PAPI , который предоставляет доступ к аппаратным счетчикам и простым тестовым программам. Мой любимый интерфейс / оболочка PAPI - IPM (Integrated Performance Monitor), но существуют и другие решения (например, TAU ). Это должно дать довольно стабильное сравнение между методами.

Я собираюсь ответить на этот вопрос, как если бы вы спросили:

«Как мне аналитически сравнить или предсказать производительность алгоритмов, которые в значительной степени полагаются на специальные функции, вместо традиционных подсчетов FLOP со множественным добавлением-переносом, которые приходят из числовой линейной алгебры»

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

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

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

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

3. Объем памяти - это тесно связано с предыдущими пунктами, но по мере того, как компьютеры становятся все больше и больше, объем памяти на ядро ​​фактически снижается. Есть два преимущества небольшого объема памяти. Во-первых, небольшое количество программных данных, вероятно, сможет полностью поместиться в кэш процессора. Второе - это то, что для очень больших проблем алгоритм с меньшим объемом памяти может быть способен вписаться в память процессора, что позволяет решать проблемы, которые в противном случае превысили бы возможности компьютера.

Зачем считать флопы? Просто посчитайте циклы для каждой операции, и вы получите нечто универсальное.