Я пишу приложение с хрустальными номерами С++, где узкое место - это функция, которая должна вычисляться для double:
template<class T> inline T sqr(const T& x){return x*x;}
и другой, который вычисляет
Base dist2(const Point& p) const
{ return sqr(x-p.x) + sqr(y-p.y) + sqr(z-p.z); }
Эти операции занимают 80% времени вычислений. Интересно, можете ли вы предложить подходы, чтобы сделать это быстрее, даже если есть какая-то потеря точности
Спасибо
Есть много ответов, в которых упоминается SSE уже... но так как никто не упомянул, как его использовать, я заброшу еще один...
В вашем коде есть все, что нужно для векторизатора, кроме двух ограничений: сглаживание и выравнивание.
Сглаживание - это проблема двух имен, ссылающихся на два одинаковых объекта. Например, my_point.dist2( my_point ) будет работать на двух экземплярах my_point. Это связано с векторизатором.
C99 определяет ключевое слово restrict для указателей, чтобы указать, что ссылочный объект однозначно ссылается: не будет другого указателя restrict для этого объекта в текущей области. Большинство достойных компиляторов С++ реализуют C99, а также импортируют эту функцию.
__restrict__. Он может применяться к ссылкам или this.__restrict. Я был бы удивлен, если бы поддержка не отличалась от GCC.(но не в С++ 0x.)
#ifdef __GCC__
#define restrict __restrict__
#elif defined _MSC_VER
#define restrict __restrict
#endif
Base dist2(const Point& restrict p) const restrict
Большинство блоков SIMD требуют выравнивания по размеру вектора. С++ и C99 оставляют реализацию выравнивания реализацией, но С++ 0x выигрывает эту гонку, вводя [[align(16)]]. Поскольку это все еще немного в будущем, вы, вероятно, хотите, чтобы ваша полуавтоматическая поддержка вашего компилятора, la restrict:
#ifdef __GCC__
#define align16 __attribute__((aligned (16)))
#elif defined _MSC_VER
#define align16 __declspec(align (16))
#endif
struct Point {
double align16 xyz[ 3 ]; // separate x,y,z might work; dunno
…
};
Это не гарантирует получение результатов; как GCC, так и MSVC обеспечивают полезную обратную связь, чтобы рассказать вам, что не было векторизованным и почему. Google, чтобы узнать больше.
Во-первых, убедитесь, что dist2 может быть встроенным (из вашего сообщения не ясно, имеет ли это значение), если он определен в файле заголовка, если это необходимо (как правило, вам нужно это сделать), но если ваш компилятор генерирует код во время соединения, то это необязательно в случае).
Предполагая архитектуру x86, обязательно разрешите компилятору генерировать код с помощью инструкций SSE2 (пример набора команд SIMD), если они доступны в целевой архитектуре. Чтобы дать компилятору наилучшую возможность их оптимизировать, вы можете попытаться объединить свои операции sqr вместе (инструкции SSE2 должны иметь возможность выполнять до 4 операций с плавающей запятой или двумя двойными операциями за раз в зависимости от инструкции.. но, конечно, это может делайте это только в том случае, если у вас есть входы для нескольких операций на готовом устройстве). Я бы не слишком оптимистично относился к способности компилятора понять, что он может их запускать, но вы можете хотя бы настроить свой код, чтобы это было возможно в теории.
Если вы все еще не удовлетворены скоростью, и вы не верите, что ваш компилятор делает все возможное, вам следует изучить возможность использования встроенных компиляторов, которые позволят вам явно писать потенциальные параллельные инструкции.. или, альтернативно, вы может идти прямо вперед и писать архитектурный код сборки, чтобы использовать SSE2 или любые команды, наиболее подходящие для вашей архитектуры. (Предупреждение: если вы вручную скомпоновите сборку, либо проявите особую осторожность, чтобы она по-прежнему встраивалась, либо превращала ее в большую пакетную операцию)
Чтобы сделать это еще больше (и, как уже упоминалось выше), вы можете выполнять эти операции на графическом процессоре. Для вашего конкретного случая имейте в виду, что GPU часто не поддерживает двойную точность с плавающей запятой. Хотя, если он подходит для того, что вы делаете, вы получите на порядок более высокую производительность таким образом. Google для GPGPU или чего-то еще и посмотреть, что лучше для вас.
Что такое Base?
Является ли это классом с неявным конструктором? Возможно, вы создаете достаточное количество временных объектов Base. Это может быть большой бонус процессора.
template<class T> inline T sqr(const T& x){return x*x;}
Base dist2(const Point& p) const {
return sqr(x-p.x) + sqr(y-p.y) + sqr(z-p.z);
}
Если переменные-члены p имеют тип Base, вы можете вызвать sqr в базовых объектах, которые будут создавать временные значения для вычитаемых координат, в sqr, а затем для каждого добавленного компонента.
(Мы не можем сказать без определений классов)
Вероятно, вы могли бы ускорить его, заставив вызовы sqr быть в примитивах, а не используя Base, пока не дойдете до типа возврата dist2.
Другие возможности улучшения производительности заключаются в следующем:
dist2 так много, возможно, кэшировать или использовать свойство transitive.Я думаю, что оптимизация этих функций может быть сложной, вам может быть лучше оптимизировать код, который вызывает эти функции, чтобы называть их меньше или делать что-то по-другому.
Вы не говорите, можно ли рассылать вызовы dist2 или нет. Если они могут, тогда вы можете создать пул потоков и разделить эту работу на меньшие куски на поток.
Что говорит ваш профайлер, происходит внутри dist2. Вы на самом деле используете 100% процессор все время или у вас отсутствует кеш и ожидаете загрузки данных?
Честно говоря, нам действительно нужно больше деталей, чтобы дать вам окончательный ответ.
Если sqr() используется только для примитивных типов, вы можете попробовать использовать аргумент по значению вместо ссылки. Это спасет вас от косвенности.
Если вы можете упорядочить свои данные подходящим образом, вы можете использовать здесь оптимизацию SIMD. Для эффективной реализации вы, вероятно, захотите разместить свою структуру Point так, чтобы она имела 4 элемента (т.е. Добавила четвертый фиктивный элемент для заполнения).
Если у вас есть несколько таких функций, и вы выполняете графические или графические задачи (термическое моделирование, практически любое 3D-моделирование), вы можете использовать OpenGL и разгружать задачи на графический процессор. Это позволило бы параллельным вычислениям с высокой оптимизацией операционных возможностей. В конце концов, вы бы ожидали чего-то вроде расстояния или расстояний q, чтобы иметь собственный код операции на графическом процессоре.
Исследователь из локального университета разгружает почти все свои 3D-вычисления для работы ИИ на GPU и добивается гораздо более быстрых результатов.
Если вам действительно нужны все значения dist2, вы должны их вычислить. Это уже низкий уровень и не может себе представить ускорения, кроме распределения на нескольких ядрах.
С другой стороны, если вы ищете близость, вы можете предоставить функции dist2() текущее значение miminum. Таким образом, если sqr(x-p.x) уже больше вашего текущего минимума, вы можете избежать вычисления оставшихся 2 квадратов.
Кроме того, вы можете избежать первого квадрата, углубляясь в двойное представление. Сравнение непосредственно с показателем экспоненты с вашим текущим мимином может сэкономить еще больше циклов.
Используете ли вы Visual Studio? Если это так, вы можете посмотреть, как указать элемент управления с плавающей запятой, используя /fp fast в качестве компиляционного переключателя. Посмотрите Режим fp: быстрый для семантики плавающей точки. GCC имеет множество оптимизаций с плавающей запятой -fOPTION, которые вы, возможно, захотите рассмотреть (если, как вы говорите, точность не вызывает большого беспокойства).
Я предлагаю два метода:
Эти методы могут не иметь значения, но их стоит попробовать. Прежде чем вносить какие-либо изменения, сначала распечатайте язык ассемблера.. Это даст вам базовый уровень для сравнения.
Здесь код:
Base dist2(const Point& p) const
{
// Load the cache with data values.
register x1 = p.x;
register y1 = p.y;
register z1 = p.z;
// Perform subtraction together
x1 = x - x1;
y1 = y - y1;
z1 = z - z2;
// Perform multiplication together
x1 *= x1;
y1 *= y1;
z1 *= z1;
// Perform final sum
x1 += y1;
x1 += z1;
// Return the final value
return x1;
}
Другой альтернативой является группировка по размеру. Например, сначала выполните все операции "X", затем Y и затем Z. Это может показать компилятору, что части являются независимыми и могут делегировать другому ядру или процессору.
Если вы не можете получить больше производительности из этой функции, вы должны посмотреть в другом месте, как предложили другие люди. Также прочитайте Data Driven Design. Есть примеры, когда реорганизация загрузки данных может ускорить работу более чем на 25%.
Кроме того, вам может понадобиться изучить использование других процессоров в системе. Например, BOINC Project может делегировать вычисления графическому процессору.
Надеюсь, что это поможет.
Операции с плавающей запятой довольно часто медленнее, возможно, вы можете подумать об изменении кода, чтобы использовать только целочисленную арифметику и посмотреть, помогает ли это?
ИЗМЕНИТЬ: После того, как Павел сделал это, я изложил свой совет, чтобы не требовать, чтобы операции с плавающей запятой всегда были медленнее. Благодарю.
Из числа операций, я не вижу, как это можно ускорить, не вникая в оптимизацию оборудования (например, SSE), как указывали другие. Альтернативой является использование другой нормы, как 1-норма - это просто сумма абсолютных значений термов. Тогда никаких умножений не требуется. Однако это изменяет основную геометрию вашего пространства, изменяя кажущееся расстояние между объектами, но это может не иметь значения для вашего приложения.
Ваша лучшая надежда состоит в том, чтобы дважды проверить, что каждый вызов dist2 действительно необходим: возможно, алгоритм, который его вызывает, может быть реорганизован, чтобы быть более эффективным? Если несколько расстояний вычисляются несколько раз, возможно, они могут быть кэшированы?
Если вы уверены, что все вызовы необходимы, вы можете выжать последнюю каплю производительности с помощью компилятора, ориентированного на архитектуру. Я получил хорошие результаты, используя компилятор Intel на x86s, например.
Просто несколько мыслей, однако маловероятно, что я добавлю что-нибудь ценное после 18 ответов:)
Если вы тратите 80% времени на эти две функции, я могу представить два типичных сценария:
Ваш алгоритм по крайней мере полиномичен
Поскольку ваши данные кажутся пространственными, возможно, вы можете привести O (n) вниз, введя пространственные индексы?
Вы перебираете определенный набор
Если этот набор поступает либо из данных на диске (сортировка?), Либо из цикла, возможно, существует возможность кэширования или использовать предыдущие вычисления для более быстрого вычисления sqrt.
Кроме того, что касается кэша, вы должны определить требуемую точность (и диапазон ввода) - может быть, может быть использован какой-то вид/кеш?
(царапины, что!!! sqr!= sqrt)
Посмотрите, применимо ли в вашем случае "Fast sqrt":
Посмотрите на контекст. Там вы ничего не можете сделать, чтобы оптимизировать операцию так же просто, как x*x.
Вместо этого вы должны посмотреть на более высокий уровень: откуда вызвана функция? Как часто? Зачем? Можете ли вы уменьшить количество звонков? Можете ли вы использовать инструкции SIMD для выполнения умножения на несколько элементов за раз?
Можете ли вы разгрузить целые части алгоритма на GPU?
Определяется ли функция так, что она может быть встроена? (в основном, его определение видимо на сайтах вызовов)
Требуется ли результат сразу после вычисления? Если это так, латентность операций FP может повредить вам. Постарайтесь упорядочить свой код, так что цепи зависимостей разбиваются или чередуются с несвязанными инструкциями.
И, конечно же, рассмотрите сгенерированную сборку и посмотрите, что вы ожидаете.
Есть ли причина, по которой вы выполняете свой собственный оператор sqr?
Пробовал ли вы в libm, он должен быть сильно оптимизирован.
Первое, что происходит со мной, это memoization ( "на лету" кеширование вызовов функций), но как sqr, так и dist2 казалось бы, что они слишком низки для служебных данных, связанных с memoization, экономия из-за воспоминаний. Однако на более высоком уровне вы можете обнаружить, что это может сработать для вас.
Я думаю, требуется более подробный анализ ваших данных. Говоря, что большую часть времени в программе тратится, выполнение команд MOV и JUMp может быть точным, но это не поможет очень оптимизировать yhou. Информация слишком низкая. Например, если вы знаете, что целые аргументы достаточно хороши для dist2, а значения находятся между 0 и 9, тогда предварительно кэшированный текст будет 1000 элементов - не большой. Вы всегда можете использовать код для его создания.
Вы развернули петли? Сломанный матричный отступ? Посмотрел на места, где вы можете получить таблицы, вместо фактического расчета.
Наиболее решительным было бы принять методы, описанные в: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.8660&rep=rep1&type=pdf хотя это, по общему признанию, трудно читать, и вам следует получить помощь от того, кто знает Common Lisp, если вы этого не сделаете.
Мне любопытно, почему вы сделали этот шаблон, когда сказали, что вычисление выполняется с помощью парных? Почему бы не написать стандартный метод, функцию или просто "x * x"?
Если ваши входы могут быть предсказуемо ограниченными и вам действительно нужна скорость, создайте массив, содержащий все выходы, которые может произвести ваша функция. Используйте вход как индекс в массив (разреженный хеш). Затем оценка функции становится сравнением (для проверки границ массива), добавлением и ссылкой на память. Это не будет намного быстрее, чем это.
См. инструкции SUBPD, MULPD и DPPD. (DPPD требуется SSE4)
Зависит от вашего кода, но в некоторых случаях макет схемы с массивами может быть более дружественным к векторизации, чем макет структуры структуры.