HLFX.Ru Forum - вопрос по программированию#3 [OpenMP]

Показать все 11 сообщений этой темы на одной странице

HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Технические вопросы (https://hlfx.ru/forum/forumdisplay.php?forumid=20)
-- вопрос по программированию#3 [OpenMP] (https://hlfx.ru/forum/showthread.php?threadid=3260)

Отправлено thambs 13-02-2012 в 13:25:

вопрос по программированию#3 [OpenMP]

хочу распараллелить последовательную подпрограмму с помощью 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,:) не имеет значения. ссылки на статьи приветствуются.

__________________
http://www.moddb.com/mods/monorail-quest

Отправлено XaeroX 13-02-2012 в 14:51:

Классические приёмы распараллеливания молекулярной динамики - разбиение пространства с периодическими граничными условиями, например - не подходят?
Возможно, я не въехал в задачу, у меня от этих F, V и N голова кругом пошла. Словесно бы описал, что ли..

__________________

Отправлено Дядя Миша 13-02-2012 в 15:05:

Я может и не в тему. Но по-моему в развитых странах ваши задачи давным давно уже решены. ну всмысле, компьютеры изначально предназначались для таких вот глобальных рассчётов и алгоритмы распараллеливания подобных задач были придуманы и отлажены еще в 70-е годы.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено XaeroX 13-02-2012 в 16:01:

Дядя Миша
Так он и просит дать ему алгоритм.

__________________

Отправлено Дядя Миша 13-02-2012 в 17:37:

XaeroX я думал мож какой сайт есть специализироватый

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено thambs 13-02-2012 в 18:59:

XaeroX

вот. я нарисовал схемку

Цитата:

одномерное пространство равномерно разбито на N ячеек с шагом h. в пространстве находятся заряженные (и нейтральные) частицы, отсортированные по ячейкам так, что в ячейке №i находятся только те частицы, чьи floor(x/h+1)=i. так как массив статичный, то что бы отличать данные от мусора введён дополнительный массив V (он просто хранит номера последних значащих строк)
для каждого сорта частиц свой массив F

решается нестационарная задача. интервал времени dt столь мал, что электромагнитные поля можно считать стационарными? а самая быстрая частица не может сместиться больше чем на h.

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

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

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

//параллелить буду с помощью OpenMP (общая память)

__________________
http://www.moddb.com/mods/monorail-quest

Отправлено XaeroX 13-02-2012 в 19:12:

Цитата:

thambs писал:
разбить итерацию на (числопроцессоров)/N областей, так что бы между ними оставался зазор в 2 ячейки -- таким образом частицы, обрабатываемые разными процессорами никак не попадут не в свою область, а после такой обработки достаточно будет пройтись по оставшимся промежуткам

А если сделать перекрывающиеся области? Чуть больше расчётов, но не будет "оставшихся промежутков".

__________________

Отправлено thambs 13-02-2012 в 19:18:

XaeroX

а не получится ли ситуации, что соседний процессор попытается обработать уже обработанную частицу?

кстати, ты с openCL знаком?

__________________
http://www.moddb.com/mods/monorail-quest

Отправлено Дядя Миша 13-02-2012 в 20:05:

Цитата:

thambs писал:
а не получится ли ситуации, что соседний процессор попытается обработать уже обработанную частицу?

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

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено marikcool 13-02-2012 в 23:46:

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

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

Отправлено XaeroX 14-02-2012 в 06:39:

Цитата:

thambs писал:
кстати, ты с openCL знаком?

Нет, я только с Cuda, и то лишь в теории - ни разу не пришлось применить знания на практике.

Цитата:

marikcool писал:
то можно попробовать просто булевую переменую завести чтобы помечать обработаные ячейки, только значения булевой через атомарную операцию менять.

Только не булевую, а timestamp counter. И сравнивать его с глобальным, который увеличивается каждый акт расчётов. Булевую сбрасывать придётся, зачем лишние операции. А atomic - да, наверное, хорошее решение.

__________________

Временная зона GMT. Текущее время 08:14.

Показать все 11 сообщений этой темы на одной странице

На основе vBulletin версии 2.3.0
Авторское право © Jelsoft Enterprises Limited 2000 - 2002.
Дизайн и программирование: Crystice Softworks © 2005 - 2024