Можно ли распространять или параллельно обрабатывать последовательную программу?

Question

В C ++ я написал математическую программу (для агрегирования с диффузионным ограничением), в которой каждая вычисленная новая точка зависит от всех предыдущих точек. Возможно ли, чтобы такая программа работала параллельно или распределенно для увеличения скорости вычислений? Если да, то какие изменения в коде мне нужно изучить?

РЕДАКТИРОВАТЬ: мой исходный код доступен на ... http://www.bitbucket.org/damigu78/brownian-motion/downloads/ имя файла - DLA_full3D.cpp Я не против значительных переписываний, если это то, что нужно. В конце концов, я хочу научиться это делать.

Answer 1

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

Какой алгоритм вы используете?

РЕДАКТИРОВАТЬ: поиск в Google "алгоритм параллельной диффузии с ограниченной диффузией" приводит меня здесь со следующей цитатой:

DLA, с другой стороны, был показан [9,10] принадлежать к классу по своей сути последовательный или, более формально, P-полные задачи. Следовательно, вряд ли DLA кластеры могут быть отобраны параллельно в время полилога, когда ограничено количество процессоров полинома в Размер системы.

Итак, ответ на ваш вопрос «все знаки указывают на нет».

Answer 2

Не зная больше о вашей проблеме, я просто скажу, что это выглядит как хороший кандидат для реализации в качестве параллельного сканирования префиксов (http://en.wikipedia.org/wiki/Prefix_sum). * Простейшим примером этого является массив, который вы хотите сделать текущая сумма из:

1 5 3 2 5 6

становится

1 6 9 11 16 22 * ​​1009 *

Это выглядит по сути последовательно (поскольку все точки зависят от предыдущих), но это можно сделать параллельно.

Answer 3

Существует cilk , который является расширением языка C (к сожалению, не C ++ (пока)), который позволяет вам добавить некоторую дополнительную информацию в ваш код. С помощью всего лишь нескольких незначительных советов компилятор может автоматически распараллеливать части вашего кода, например, выполнять несколько итераций цикла for параллельно, а не последовательно.

Answer 4

Возможно. Существуют параллельные версии большинства последовательных алгоритмов, и для тех последовательных алгоритмов, которые не могут быть сразу распараллелены, обычно есть параллельные заменители. Похоже, это один из тех случаев, когда вам нужно рассмотреть возможность распараллеливания или распараллеливания, прежде чем выбрать алгоритм. Но если вы не расскажете нам немного (много?) О своем алгоритме, мы не сможем дать много конкретных указаний. Если вам забавно наблюдать, как SO спорят в отсутствие жестких данных, бездельничайте и смотрите, но если вы хотите получить ответы, отредактируйте свой вопрос.

Веб-сайт toxiclibs дает полезную информацию о том, как осуществляется одна реализация DLA

Answer 5

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

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