HLFX.Ru Forum
профиль •  правила •  регистрация •  календарь •  народ •  FAQ •  поиск •  новое •  сутки •  главная •  выход  
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Технические вопросы > вопрос по программированию#3 [OpenMP]
продублирую здесь
  Предыдущая тема   Следующая тема
Автор
Тема Новая тема    Ответить
thambs
мразь конченная

Дата регистрации: Mar 2006
Проживает: -
Сообщений: 6417

Рейтинг



вопрос по программированию#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

Сообщить модератору | IP: Записан
Сообщение: 92419

Старое сообщение 13-02-2012 13:25
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35046
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]


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

__________________

Сообщить модератору | IP: Записан
Сообщение: 92428

Старое сообщение 13-02-2012 14:51
-
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33057
Нанёс повреждений: 392 ед.

Рейтинг



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

__________________
My Projects: download page

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

Цитата:

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

Сообщить модератору | IP: Записан
Сообщение: 92431

Старое сообщение 13-02-2012 15:05
-
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35046
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]


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

__________________

Сообщить модератору | IP: Записан
Сообщение: 92440

Старое сообщение 13-02-2012 16:01
-
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33057
Нанёс повреждений: 392 ед.

Рейтинг



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

__________________
My Projects: download page

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

Цитата:

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

Сообщить модератору | IP: Записан
Сообщение: 92449

Старое сообщение 13-02-2012 17:37
-
thambs
мразь конченная

Дата регистрации: Mar 2006
Проживает: -
Сообщений: 6417

Рейтинг



XaeroX

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


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

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

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

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


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

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

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

Отредактировано thambs 13-02-2012 в 19:09

Сообщить модератору | IP: Записан
Сообщение: 92451

Старое сообщение 13-02-2012 18:59
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35046
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]


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

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

__________________

Сообщить модератору | IP: Записан
Сообщение: 92453

Старое сообщение 13-02-2012 19:12
-
thambs
мразь конченная

Дата регистрации: Mar 2006
Проживает: -
Сообщений: 6417

Рейтинг



XaeroX

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

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

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

Сообщить модератору | IP: Записан
Сообщение: 92455

Старое сообщение 13-02-2012 19:18
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33057
Нанёс повреждений: 392 ед.

Рейтинг



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

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

__________________
My Projects: download page

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

Цитата:

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

Сообщить модератору | IP: Записан
Сообщение: 92457

Старое сообщение 13-02-2012 20:05
-
marikcool
Житель форума

Дата регистрации: Jul 2011
Проживает: kz
Сообщений: 1522
Возраст: 39

Рейтинг



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

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

Сообщить модератору | IP: Записан
Сообщение: 92466

Старое сообщение 13-02-2012 23:46
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35046
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]


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

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

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

__________________

Сообщить модератору | IP: Записан
Сообщение: 92475

Старое сообщение 14-02-2012 06:39
-
Тема: (Опционально)
Ваш ответ:



Переводчик транслита


[проверить длину сообщения]
Опции: Автоматическое формирование ссылок: автоматически добавлять [url] и [/url] вокруг интернет адресов.
Уведомление по E-Mail: отправить вам уведомление, если кто-то ответил в тему (только для зарегистрированных пользователей).
Отключить смайлики в сообщении: не преобразовывать текстовые смайлики в картинки.
Показать подпись: добавить вашу подпись в конец сообщения (только зарегистрированные пользователи могут иметь подписи).

Временная зона GMT. Текущее время 19:58. Новая тема    Ответить
  Предыдущая тема   Следующая тема
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Технические вопросы > вопрос по программированию#3 [OpenMP]
продублирую здесь
Версия для печати | Отправить тему по E-Mail | Подписаться на эту тему

Быстрый переход:
Оцените эту тему:

Правила Форума:
Вы not можете создавать новые темы
Вы not можете отвечать в темы
Вы not можете прикреплять вложения
Вы not можете редактировать ваши сообщения
HTML Код ВЫКЛ
vB Код ВКЛ
Смайлики ВКЛ
[IMG] Код ВКЛ
 

< Обратная связь - HLFX.ru >

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