Вычислительно интенсивные алгоритмы

Question

Я планирую написать кучу программ по вычислительно-интенсивным алгоритмам. Программы будут служить индикатором разной производительности компилятора / аппаратного обеспечения.

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

Любой совет по выбору алгоритма был бы чрезвычайно полезен.

Answer 1

Тесты не заслуживают вашего внимания!

Самое лучшее руководство по производительности процессора: http://www.agner.org/optimize/

И тогда кто-то забросит его в коробку с 3 ГБ ОЗУ, победив двухканальные надежды, и ваш прекрасно настроенный тест снова даст совершенно другие результаты.

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

Показательный пример: люди, которые делают программное обеспечение для сжатия - например, zip и 7zip, а также такие высококлассные продукты, как PPM, микширование контекста и т. Д. - очень внимательно относятся к производительности и тестируют свои программы. Они тусуются на www.encode.ru

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

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

(Я видел, как одно и то же повторялось неоднократно в программировании соревнований, например, Конкурсы по программированию Аль Циммермана , который в равной степени учитывает производительность.)

(более новая серия GCC 4.x очень хороша во всех отношениях, но это только мое мнение, другие по-прежнему поддерживают ICC)

(Тесты платформы для задач, связанных с вводом-выводом - это совсем другое; люди не ценят, как по-разному работают Linux, Windows и FreeBSD (и остальные) в стрессовых ситуациях. И тесты там - на одной рабочей нагрузке, на одной машине, разные машины или разные подсчёты ядра - это было бы очень информативно. К сожалению, таких тестов не хватает.)

Answer 2

Несколько лет назад в Беркли была проделана определенная работа. Выявлено 13 общих приложений для параллельного программирования «13 гномов». Включают такие вещи, как линейная алгебра, модели n-тела, FFT и т. Д.

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html

См. Стр. 10.

Здесь есть несколько примеров реализации .NET:

http://paralleldwarfs.codeplex.com/

Answer 3

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

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

Answer 4

Типичным является быстрое преобразование Фурье, возможно, вы также можете сделать что-то вроде теста простоты Лукаса-Лемера.