Тестирование производительности для расчета-тяжелых программ

Question

Каковы некоторые полезные советы и/или методы оптимизации и повышения эффективности расчета тяжелых программ. Я говорю о таких вещах, как вычисления графики усложнения или математические и симуляционные типы программирования, где каждая секундная справка полезна, в отличие от тяжелых программ IO, где полезно только определенное ускорение.

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

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

Редактировать: указать немного больше. Я использую C#, и мои алгоритмы вращаются вокруг вычисления и решения проблем типа ограничения для выражений (используя деревья выражений). Под выражениями я подразумеваю такие вещи, как x^2 + 4 или что-то еще подобное, которое было бы проанализировано в дереве выражений. Мои алгоритмы создают и обрабатывают эти деревья, чтобы попытаться найти более удобные аппроксимации. Но я хотел задать вопрос в общем виде, если это поможет кому-то еще.

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

Answer 1

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

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

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

Старайтесь избегать ненужного выделения и выделения памяти. Здесь есть смысл отступить от чисто подхода OO.

Answer 2

Это почти такой же процесс, как и любая другая оптимизация: профиль, эксперимент, эталон, повторение.

Сначала вы должны выяснить, какие разделы вашего кода занимают время. Затем попробуйте разные методы, чтобы ускорить их (методы, основанные на заслугах, будут лучше, чем попытка наугад). Тест, чтобы узнать, действительно ли вы ускорили их. Если вы это сделали, замените старый метод на новый. Профиль снова.

Answer 3

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

Стандартные узкие места в числовых алгоритмах - это память Использование (вы получаете доступ к матрицам в том порядке, в котором элементы хранятся в памяти); коммуникационные накладные расходы и т. д. Они могут немного отличаться от других нецифровых программ.

Кроме того, многие другие факторы, такие как предварительное кондиционирование и т. Д. могут привести к резкому изменению поведения производительности ИСПОЛЬЗУЕМОГО алгоритма по той же проблеме. Убедитесь, что вы определяете оптимальные параметры для своих реализаций.

Что касается сравнения различных алгоритмов, я рекомендую читать газету

«Тестирование программного обеспечения оптимизации с профилями производительности,» Хорхе и Элизабет ещё Д. Долан, Математическое программирование 91 (2002), 201-213.

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

Удачи вам!

Answer 4

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

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

• GProf
• PerfMon2
• OProfile
• HPCToolkit

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

Помимо этого, нужно подумать о том, как лучше всего перестроить ваш код, и это зависит от проблемы. Возможно, вы только что получили цикл, который компилятор не оптимизирует, и вы можете встраивать или перемещать вещи в/из цикла, чтобы помочь компилятору выйти. Или, если вы работаете так быстро, как можете, используя базовые арифметические операции, вы можете попытаться использовать векторные инструкции (SSE и т. Д.). Если ваш код параллелен, могут возникнуть проблемы с балансировкой нагрузки, и вам может потребоваться реструктурируйте свой код, чтобы данные лучше распределялись по ядрам.

Это всего лишь несколько примеров. Оптимизация производительности сложна, и это может не помочь вам почти достаточно, если вы начинаете с грубой силы.

Для получения дополнительной информации о том, как люди оптимизировали вещи, в недавнем прошлом были довольно хорошие примеры Why do you program in assembly? вопрос.

Answer 5

Это больше чаевых, чтобы найти дыры в самом алгоритме ...

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

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

initialize: 
float y = 0; // y coordinate 
float yi = 0; // incremental variable 

loop: 
y += yi; 
yi += 0.001; 

if (y > 10) 
    yi = -yi; 

Но теперь предположим, что вы испытываете, чтобы сделать это с вложенными петлями в моделировании N-тела, где каждая частица притягивается к каждой другой частице. Это может быть чрезвычайно сложной задачей, когда вы имеете дело с тысячами частиц.

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

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

y += yi * 0.01; 

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