Трехдиагональная СЛАУ: параллельный алгоритм
типа знаю, что это классический пример хреново параллелизуемого алгоритма 
Больше мне вас порадовать нечем, решить не пытался
Больше мне вас порадовать нечем, решить не пытался решается 20000 раз - надеюсь, с разной правой частью и одинаковой левой?
тогда - LU-разложение. один раз разложить - потом 20000 раз считать.
тогда - LU-разложение. один раз разложить - потом 20000 раз считать.
Кстати да, эти 20000 раз быстро приходят? А то зачем вам параллельный алгоритм, если размерность небольшая? Просто раздавали бы задачи по узлам по мере появления (даже можно штук по 50, а не по одной). Не подойдет? Это же считается моментально на указанных размерностях.
To :
Нет, к сожалению левая часть меняется.
To , :
В кратце, ситуация такова. Допустим есть двумерный массив, значение которого зависит от времени. На каждом шаге по времени идет цикл по строчкам этого массива. В данной строчке составляется тридиагональная система размерности равной длине столбцов данного массива.
Пусть A(i B(i C(i) - поддиагональ, диагональ и наддиагональ соответствующей системы. Тогда А, B, C есть функции:
Проблема в том что в действительности узел хранит не всю матрицу ARRAY а только допустим A(I, JJ1:JJ2, T).
Поэтому сейчас перед такого рода циклами стоит синхронизация массива по столбцам.
Любые рационализаторские предложения -welcome
Нет, к сожалению левая часть меняется.
To , :
В кратце, ситуация такова. Допустим есть двумерный массив, значение которого зависит от времени. На каждом шаге по времени идет цикл по строчкам этого массива. В данной строчке составляется тридиагональная система размерности равной длине столбцов данного массива.
Пусть A(i B(i C(i) - поддиагональ, диагональ и наддиагональ соответствующей системы. Тогда А, B, C есть функции:
/* Идем по строчкам */
FOR I = 1, N
/* Идем по столбцам */
FOR J = 1, N
A(j) = FUNCTION(ARRAY(I,J,T
B(j) = FUNCTION(ARRAY(I,J,T
C(j) = FUNCTION(ARRAY(I,J,T
ENDFOR
/* Система составлена, решаем ее */
SOLVE(A, B, C, N)
ENDFOR
Проблема в том что в действительности узел хранит не всю матрицу ARRAY а только допустим A(I, JJ1:JJ2, T).
Поэтому сейчас перед такого рода циклами стоит синхронизация массива по столбцам.
Любые рационализаторские предложения -welcome
У меня есть подозрение, что компьютеры соединены в сеть по средством, в лучщем случае, 1gb Ethernet, с латентностью по порядку в милисекунды или в лучшем случае в 100 микросекунд или 10^5 - 10^6 тактов процессора тактов процессора. т.е. любой распределенный алгоритм будет работать покрайней мере дольше этого времени. Сколько времени занимает алгоритм для указанных размерностей? понятно, что по порядку примерно столько же или меньше. Т.е. в лучшей случае, удасться ускорить эту систему не более чем в 2 раза на распередленной системе, в не зависимости от количества процессоров.
Стоит смотреть, как ускорить это дело на одном узле, может использовать GPGPU (массивно-параллельные процессоры В любом случае производительностей близкой к пиковой не стоит ожидать, скорее всего лимитирующим фактором будет пропускная способность памяти.
Какие критерии эффективности к алгоритму: маленькая задержка между входящими и выходящими данными? Может общая пропускная способность //решение тысяч систем в секунду?.. или еще что (может минимилизация затрат на оборудование и электроэнергию?) ... Или просто хочется параллельно...
Стоит смотреть, как ускорить это дело на одном узле, может использовать GPGPU (массивно-параллельные процессоры В любом случае производительностей близкой к пиковой не стоит ожидать, скорее всего лимитирующим фактором будет пропускная способность памяти.
Какие критерии эффективности к алгоритму: маленькая задержка между входящими и выходящими данными? Может общая пропускная способность //решение тысяч систем в секунду?.. или еще что (может минимилизация затрат на оборудование и электроэнергию?) ... Или просто хочется параллельно...
У меня были аналогичные вопросы выше и далее последовал ответ, который я бы на вашем месте прочитал внимательнее.
да, и был на вашем месте, и прочитал внимательнее, первый раз со мной такое!
Спасибо за подкинутые мысли:
* Это Blue Gene/P, что на ВМК.
* Вот тут или в официальной документации
(там, вроде, только hardware latency указана)
можно взять цифры про латентность - 0.1 микросекунды для point-to-point
и 3 микросекунды для коллективных операций
* Текущий алгоритм работает примерно 10 микросекунд (это зависит
от конфигурации, но порядок таков)
* Мы проглядели несколько подходов по решению трехдиагональной
системы уравнений параллельным методом. В частности, часть
из них требуют пересылки данных (O(1) элементов) от всех всем.
Таким образом, как минимум 3 микросекунды потратится на такую
пересылку (не считая расходов, связанных с пропускной способностью).
Но даже если учитывать заявленную способность 425мб/сек => получится
порядка еще < 1 микросекунды. Итого, около 4 микросекунд как минимум
на 1 пересылку, которая требуется в алгоритме. Поэтому увеличения
более, чем в (10/4=2.5) раза ждать не приходится, как и сказал ,
в независимости от количества процессов.
У нас есть еще некоторые идеи, которые надо обсудить. Но если у кого-нибудь
возникнут мысли, то я готов обсудить их прямо здесь
* Это Blue Gene/P, что на ВМК.
* Вот тут или в официальной документации
(там, вроде, только hardware latency указана)
можно взять цифры про латентность - 0.1 микросекунды для point-to-point
и 3 микросекунды для коллективных операций
* Текущий алгоритм работает примерно 10 микросекунд (это зависит
от конфигурации, но порядок таков)
* Мы проглядели несколько подходов по решению трехдиагональной
системы уравнений параллельным методом. В частности, часть
из них требуют пересылки данных (O(1) элементов) от всех всем.
Таким образом, как минимум 3 микросекунды потратится на такую
пересылку (не считая расходов, связанных с пропускной способностью).
Но даже если учитывать заявленную способность 425мб/сек => получится
порядка еще < 1 микросекунды. Итого, около 4 микросекунд как минимум
на 1 пересылку, которая требуется в алгоритме. Поэтому увеличения
более, чем в (10/4=2.5) раза ждать не приходится, как и сказал ,
в независимости от количества процессов.
У нас есть еще некоторые идеи, которые надо обсудить. Но если у кого-нибудь
возникнут мысли, то я готов обсудить их прямо здесь
Это даже на 20000 запусках займёт не больше секунды в одном потоке. Считаю, что оно не стоит распараллеливания.
Есть проблема, что перед самим решением стоит синхронизация матрицы
вдоль всех столбцов. Поэтому есть мысль, что, может, нужно распараллеливать,
чтобы убрать эту синхронизацию.
То есть перед "FOR I = 1, N" из моего примера стоит синхронизация.
вдоль всех столбцов. Поэтому есть мысль, что, может, нужно распараллеливать,
чтобы убрать эту синхронизацию.
То есть перед "FOR I = 1, N" из моего примера стоит синхронизация.
А трёхдиагональные матрицы разве прогонкой не решаются?
да, но прогонка плохо параллелится. Ну т.е. вообще не параллелится, там рекуррентная формула.
Я правильно понимаю, что тут распараллеливание - скорее академическое чем практическое?
Здесь — это в задаче ТС? Мне кажется, там вполне практическое, потому что данные на узлах по частям. У меня в принципе тоже, известно, задача плохо поддается параллелизации (если вообще, не помню).
Чем отличается практическое распараллеливание от теоретического?
Практическое вызвано необходимостью. Здесь этого как бы нет.
Вообще LU-разложение параллелится.
Но вот насчёт достаточной для топикстартера эффективности не уверен.
Где-то у меня валялась литература про это - надо будет глянуть.
Но вот насчёт достаточной для топикстартера эффективности не уверен.
Где-то у меня валялась литература про это - надо будет глянуть.
Как выглядит LU-разложение трехдиагональной матрицы? Метод прогонки за линейное время от размера матрицы работает если что.
оно трёхдиагональное. причём при правильной реализации LU-разложение ложится на ту же память, где была исходная матрица.
и тоже работает за линейное время.
и тоже работает за линейное время.
Но вряд ли всё же быстрее, чем прогонка. В чём профит? Оно параллелится?
Я так понял, у автора узкое место - обмен данными между потоками. Как там с этим?
Я так понял, у автора узкое место - обмен данными между потоками. Как там с этим?
Посмотрите на мой пост, где приведены вычисления с latency.
Если они верные, то ожидать ускорение более, чем в 2-3 раза
не приходится в НЕ ЗАВИСИМОСТИ от количества процессов.
Борьба на самом деле идет за удаление синхронизации матрицы
перед блоком вычисления трехдиагональной системы.
Пока я не очень понимаю, как соотносятся решение системы
и синхронизация (скорость ее также зависит от кол-ва процессов).
Есть несколько идей как оптимизировать синхронизацию и решение
системы, но хочется посмотреть и на полностью параллельный алгоритм.
Поэтому если у вас есть ссылка на алгоритм, который можно реализовать,
( или есть уже написанный ) был бы очень признателен.
Если они верные, то ожидать ускорение более, чем в 2-3 раза
не приходится в НЕ ЗАВИСИМОСТИ от количества процессов.
Борьба на самом деле идет за удаление синхронизации матрицы
перед блоком вычисления трехдиагональной системы.
Пока я не очень понимаю, как соотносятся решение системы
и синхронизация (скорость ее также зависит от кол-ва процессов).
Есть несколько идей как оптимизировать синхронизацию и решение
системы, но хочется посмотреть и на полностью параллельный алгоритм.
Поэтому если у вас есть ссылка на алгоритм, который можно реализовать,
( или есть уже написанный
) был бы очень признателен.узел хранит не всю матрицу ARRAY а только допустим A(I, JJ1:JJ2, T).А он заодно B(I, JJ1:JJ2, T) и C(I, JJ1:JJ2, T) не знает?
Поэтому сейчас перед такого рода циклами стоит синхронизация массива по столбцам
Встречная прогонка поможет, но не более чем вдвое время сократится.
PS Подробнее отпишусь как-нибудь.
один из первых алгоритмов параллельный похоже этот
A new parallel algorithm for tridiagonal symmetric positive definite systems of equations Fred G. Gustavson and Anshul Gupta
http://www.springerlink.de/content/p56h17146162308m
Ещё есть куча, например когда решается много 3диагональных систем одна за другой на параллельных узлах. Искать в инете по словам parallel tridiagonal и т.п.
A new parallel algorithm for tridiagonal symmetric positive definite systems of equations Fred G. Gustavson and Anshul Gupta
http://www.springerlink.de/content/p56h17146162308m
Ещё есть куча, например когда решается много 3диагональных систем одна за другой на параллельных узлах. Искать в инете по словам parallel tridiagonal и т.п.
Оставить комментарий
kataich
Хотелось задать следующий вопросКакой алгоритм для решения
трехдиагональной системы уравнений вы бы посоветовали, который бы
хорошо работал в следующих условиях:
1. Матрица хранится по строчкам/столбцам на разных вычислительных узлах,
узлы не знают ничего о строчках/стобцах своих соседей.
2. Система не есть система большой размерности (~300-1000)
3. Решение подобных систем вызывается довольно часто
(зависит от конфигурации, но порядка 20000 раз).
4. Количество задействованных узлов при решении (<30)
сейчас подобная задача обходится непараллельным методом, а именно
матрица собирается на всех узлах и решается одновременно. Хотелось
бы посоветоваться, можно ли использовать параллельный алгоритм.
Буду благодарен за любые советы.