хочу распараллелить последовательную подпрограмму с помощью openmp. подпрограмма представляет собой обход дефрагментированого разреженного массива F(N1,N2), где N1~500, N2~100000. в служебном массиве V(N1)<N2 хранится значение последнего значимого элемента подмассива F(i,:).
значимые элементы содержат в себе фазовые вектора частиц p=(x,v,i) где x -- координата, v -- скорость, i -- номер узла, причём в F(i,:) хранятся лишь те вектора, чей (x) лежит в заданном интервале (т.е. все вектора локализованы)
в процессе счёта значения x меняются так, что частица может или перескочить в соседний узел или остаться в том же.
сейчас я просто обхожу последовательно все узлы i=0..N1, все вектора j=0..V(i), провожу вычисления, и в случае, если x не соотвествует узлу i, то переношу его значение в соседний узел i2, а на его место записываю нижнее значение из F(i,V(i)) (и делаю V(i)-1, V(i2)+1).
как организовать такой обход массива при параллельном расчёте? пока на ум приходит только завести массив такого же ранга F2, все сложные вычисления проводить параллельно в F, а затем обойти F последовательно, копируя значения в уже в нужные узлы F2, но это явно непотимально. какие есть ещё варианты? с учётом того, что порядок в котором вектора записаны внутри F(i,:) не имеет значения. ссылки на статьи приветствуются.
Классические приёмы распараллеливания молекулярной динамики - разбиение пространства с периодическими граничными условиями, например - не подходят?
Возможно, я не въехал в задачу, у меня от этих F, V и N голова кругом пошла. Словесно бы описал, что ли..
Я может и не в тему. Но по-моему в развитых странах ваши задачи давным давно уже решены. ну всмысле, компьютеры изначально предназначались для таких вот глобальных рассчётов и алгоритмы распараллеливания подобных задач были придуманы и отлажены еще в 70-е годы.
одномерное пространство равномерно разбито на N ячеек с шагом h. в пространстве находятся заряженные (и нейтральные) частицы, отсортированные по ячейкам так, что в ячейке №i находятся только те частицы, чьи floor(x/h+1)=i. так как массив статичный, то что бы отличать данные от мусора введён дополнительный массив V (он просто хранит номера последних значащих строк)
для каждого сорта частиц свой массив F
решается нестационарная задача. интервал времени dt столь мал, что электромагнитные поля можно считать стационарными? а самая быстрая частица не может сместиться больше чем на h.
для каждой частицы решаются уравнения движения, производится взвешивание на стеку и анализируются (монтекарло) столкновения, в результате ионизационных столкновений производится рождение новых частиц (сортировка по сетке нужна в основном для учёта столкновений, что бы сразу подобрать частице "партнёра" по столкновению)
при решении уравнений движения многие частицы должны быть перемещены в соседние узлы, так как их координаты сместились.
на выходе должен получится новый отсортированный по сетке массив частиц.
когда все частицы обработаны, на основе новых изменившихся значений плотности заряда и токов рассчитываются новые значения электромагнитных полей.
как распараллелить задачу с минимальным числом обхода массива частиц? в последовательном коде я обхожу массив только 1 раз за итерацию, производя взвешивание и дефрагментацию прямо на ходу, а вот как быть в параллельном случае ума не приложу. Первое что на ум приходит -- разбить итерацию на параллельную обработку (числопроцессоров)/N ячеек, так что бы между ними оставался зазор в 2 ячейки -- таким образом частицы, обрабатываемые разными процессорами никак не попадут не в свою область, а после такой обработки достаточно будет пройтись по оставшимся промежуткам. но наверняка есть алгоритмы и пооптимальней.
//параллелить буду с помощью OpenMP (общая память)
thambs писал: разбить итерацию на (числопроцессоров)/N областей, так что бы между ними оставался зазор в 2 ячейки -- таким образом частицы, обрабатываемые разными процессорами никак не попадут не в свою область, а после такой обработки достаточно будет пройтись по оставшимся промежуткам
А если сделать перекрывающиеся области? Чуть больше расчётов, но не будет "оставшихся промежутков".
thambs писал: а не получится ли ситуации, что соседний процессор попытается обработать уже обработанную частицу?
ну значит надо там завести некую переменную индикатор о том, что частица уже обработана. Я правда смутно себе представляю как расшарить эту информацию между потоками.
ну и задачка, разве нельзя разбить массив на несколько блоков, например на 4 и сделать обсчет в 4 потока, заранее захватив на 2 больше элемента с начало и с конца для каждого блока т.к они влияют на расчет крайних элементов судя по схеме. потом дождаться окончания работы всех потоков и собрать результат воедино, автор так и написал вприцнипе, считаю это оптимальным решением.
если без синхронизации и ожидания потоков, то можно попробовать просто булевую переменую завести чтобы помечать обработаные ячейки, только значения булевой через атомарную операцию менять.
Нет, я только с Cuda, и то лишь в теории - ни разу не пришлось применить знания на практике.
Цитата:
marikcool писал: то можно попробовать просто булевую переменую завести чтобы помечать обработаные ячейки, только значения булевой через атомарную операцию менять.
Только не булевую, а timestamp counter. И сравнивать его с глобальным, который увеличивается каждый акт расчётов. Булевую сбрасывать придётся, зачем лишние операции. А atomic - да, наверное, хорошее решение.
13-02-2012 13:25
Словесно бы описал, что ли..
