Каков самый быстрый способ распараллеливать код?

Question

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

Мой вопрос в том, что лучший способ приблизиться к этим изменениям, чтобы я получил быстрый ускорительный удар по доллару?

В идеале, библиотека/подход Я ищу должен отвечать следующим критериям:

1. Еще быть около 5 лет. Что-то вроде варианта CUDA или ATI может быть заменено менее аппаратно-конкретным решением в недалеком будущем, поэтому мне хотелось бы что-то более надежное. Если мое впечатление от CUDA ошибочно, я приветствую исправление.
2. Быть быстрым для реализации. Я уже написал этот код, и он работает в серийном режиме, хотя и очень медленно. В идеале я бы просто взял свой код и перекомпилировал его параллельно, но я думаю, что это может быть фантазия. Если я просто переписал его с использованием другой парадигмы (т. Е. Как шейдеры или что-то еще), то это тоже будет хорошо.
3. Не требуется слишком много знаний об оборудовании. Я хотел бы иметь возможность не указывать количество потоков или операционных единиц, а скорее иметь что-то автоматически, чтобы все это было для меня на основе используемой машины.
4. Быть работоспособным на дешевом оборудовании. Это может означать графическую карту стоимостью 150 долларов или что-то еще.
5. Быть в Windows. Что-то вроде GCD может быть правильным, но клиентская база, на которую я нацеливаюсь, не скоро переключится на Mac или Linux. Обратите внимание, что это делает ответ на вопрос немного иным, чем this other question.

Какие библиотеки/подходы/языки следует искать? Я смотрел такие вещи, как OpenMP, CUDA, GCD и т. Д., Но мне интересно, есть ли другие вещи, которые мне не хватает.

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

Answer 1

Вы видели Intel (с открытым исходным кодом) Threading Building Blocks?

Answer 2

Самый простой способ состоит в том, чтобы разделить ваше изображение на количество частей, которые вы можете обрабатывать параллельно (4, 8, 16, в зависимости от ядер). Затем просто запустите другой процесс для каждой части.

С точки зрения этого, взгляните на OpenCL. Он, надеюсь, будет работать дольше, поскольку он не является специфичным для вендора, и NVIDIA и ATI хотят его поддержать.

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

Answer 3

Я не использовал его, но взгляните на Cilk. Один из больших париков в их команде - Чарльз Э. Лейзерсон; он является «L» в CLRS, самой распространенной/уважаемой книге «Алгоритмы» на планете. Я думаю, что он удовлетворяет вашим требованиям.

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

Answer 4

Если у вас уже есть рабочий серийный код в одном из C, C++ или Fortran, вы должны серьезно рассмотреть OpenMP. Одно из его больших преимуществ перед множеством других библиотек/языков/систем распараллеливания - это то, что вы можете параллелизовать цикл за раз, что означает, что вы можете получить полезную скорость без необходимости переписывать или, что еще хуже, повторять -design, ваша программа.

С точкой зрения ваших требований:

1. OpenMP часто используется в высокопроизводительных вычислениях, есть много «вес» за ним и активное развитие сообщества - www.openmp.org.

2. Быстрое выполнение, если вам посчастливилось выбрать C, C++ или Fortran.

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

4. Работает на оборудовании, которое у вас уже есть, нет необходимости в дорогостоящих или дешевых дополнительных видеокартах.

5. Да, существуют реализации для систем Windows.

Конечно, если бы вы были неосторожность не выбрали C, C++ или Fortran в начале много этот совет будет применяться только после того, как вы переписали его на один из этих языков!

С уважением

Марк

Answer 5

Я также рекомендовал бы Threading Building Blocks. Мы используем это с Intel® Integrated Performance Primitives для анализа изображений в компании, в которой я работаю.

Резьбовые строительные блоки (TBB) аналогичны OpenMP и Cilk. И он использует OpenMP для многопоточности, он просто завернут в более простой интерфейс. С этим вам не нужно беспокоиться о том, сколько потоков нужно сделать, вы просто определяете задачи. Он будет разбивать задачи, если это возможно, на то, чтобы все было занято, и он выполняет балансировку нагрузки для вас.

Intel Integrated Performance Primitives (Ipp) имеет оптимизированные библиотеки для зрения. Большинство из них многопоточные. Для требуемых функций, которые не входят в IPP, мы используем их с использованием TBB.

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