Примеры алгоритмов общего назначения, которые выиграли от работы на GPU? [закрыто]

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

Несколько вещей сразу приходят на ум:

Был написан специализированный биткойн-клиент для использования графического процессора для выполнения криптографических хэшей. Клиент GPU обычно работает более чем в 10 раз лучше, чем клиент CPU SMP в типичной 4-ядерной системе. Биткойн зависит от вычисления большого количества несвязанных криптографических хэшей, которые могут быть вычислены параллельно.

Проект Folding @ Home предлагает клиент GPU для моделирования молекулярной динамики. Эти вычисления выполняются для отдельных связей между атомами в различных средах и условиях. Математика относительно проста, но для каждой связи должна вычисляться миллиарды раз, чтобы имитировать простые наносекунды активности.

Популярный «игрушечный» пример, используемый сторонниками вычислений на GPU, - это проблема n-body .

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

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

Видео и аудио транскодирование является отличным примером. Это преобразование из одного формата файла в другой. Примером является MPEG-2 до H.264.

_{Обратите внимание, что транскодирование видео не связано с трехмерной графикой. Вы не можете кодировать видео, используя вершинный и пиксельный шейдеры.}

Майнинг биткойнов с использованием графического процессора стал очень популярным.

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

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

Другое приложение на финансовых рынках для торговли в реальном времени с использованием таких моделей, как Блэк-Шоулз .

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

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

Игра жизни Конвея - хороший академический пример.

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

1. Любая живая клетка с менее чем двумя живыми соседями умирает, как если бы она была вызвана недостаточным населением.
2. Любая живая клетка с двумя или тремя живыми соседями живет для следующего поколения.
3. Любая живая клетка с более чем тремя живыми соседями умирает, как если бы она была переполнена.
4. Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как будто путем размножения.

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

Задачи, которые требуют много математики, которые могут быть выполнены одновременно. Там, где я работал, мы хотели поиграть с графическими процессорами, чтобы сложить / вычесть / умножить 2 матрицы для определения генетической корреляции. Первый раз, когда я услышал о графических процессорах, было то, что они использовались финансовым центром программного обеспечения для некоторых моделей (Монте-Карло и так далее). Было бы полезно при взломе кода.

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

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

Я уже видел этот тест FFT, и хотя ему уже несколько лет, я думаю, что он был хорошо сделан для того, что он есть: http://www.sharcnet.ca/~merz/CUDA_benchFFT