Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА
В работе предложены принципы и схемы параллельных вычислений в обобщённом релаксационном итерационном алгоритме МГУА. Разработанные схемы позволяют увеличить скорость работы алгоритма пропорционально количеству вычислителей, достигая при этом максимальной загрузке вычислителей....
Gespeichert in:
| Datum: | 2013 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2013
|
| Schriftenreihe: | Індуктивне моделювання складних систем |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/83674 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА / А.В. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 220-225. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83674 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-836742015-06-22T03:02:20Z Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА Павлов, А.В. Наукові статті В работе предложены принципы и схемы параллельных вычислений в обобщённом релаксационном итерационном алгоритме МГУА. Разработанные схемы позволяют увеличить скорость работы алгоритма пропорционально количеству вычислителей, достигая при этом максимальной загрузке вычислителей. У роботі запропоновані принципи і схеми паралельних обчислень в узагальненому ре-лаксаційному ітераційному алгоритмі МГУА. Розроблені схеми дозволяють збільшити шви-дкість роботи алгоритму пропорційно кількості обчислючачів, досягаючи при цьому макси-мальної їх завантаженості. The paper suggests schemes and formulates principles of parallel computations for general-ized relaxational iterative algorithm. The schemes developed allow to speedup the algorithm proportianaly to number of CPU cores with maximal load each of them. 2013 Article Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА / А.В. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 220-225. — Бібліогр.: 8 назв. — рос. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/83674 681.513.8 ru Індуктивне моделювання складних систем Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Наукові статті Наукові статті |
| spellingShingle |
Наукові статті Наукові статті Павлов, А.В. Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА Індуктивне моделювання складних систем |
| description |
В работе предложены принципы и схемы параллельных вычислений в обобщённом релаксационном итерационном алгоритме МГУА. Разработанные схемы позволяют увеличить скорость работы алгоритма пропорционально количеству вычислителей, достигая при этом максимальной загрузке вычислителей. |
| format |
Article |
| author |
Павлов, А.В. |
| author_facet |
Павлов, А.В. |
| author_sort |
Павлов, А.В. |
| title |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА |
| title_short |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА |
| title_full |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА |
| title_fullStr |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА |
| title_full_unstemmed |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА |
| title_sort |
принципы параллельных вычислений в релаксационном итерационном алгоритме мгуа |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2013 |
| topic_facet |
Наукові статті |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83674 |
| citation_txt |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА / А.В. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 220-225. — Бібліогр.: 8 назв. — рос. |
| series |
Індуктивне моделювання складних систем |
| work_keys_str_mv |
AT pavlovav principyparallelʹnyhvyčislenijvrelaksacionnomiteracionnomalgoritmemgua |
| first_indexed |
2025-07-06T10:29:28Z |
| last_indexed |
2025-07-06T10:29:28Z |
| _version_ |
1836893096993882112 |
| fulltext |
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА
УДК 681.513.8
ПРИНЦИПЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В
РЕЛАКСАЦИОННОМ ИТЕРАЦИОННОМ АЛГОРИТМЕ МГУА
А.В. Павлов
Международный научно-учебный центр ЮНЕСКО информационных технологий и систем
НАНУ и МОНУ, 03680, Киев, пр. Глушкова 40
andriypavlove@gmail.com
У роботі запропоновані принципи і схеми паралельних обчислень в узагальненому ре-
лаксаційному ітераційному алгоритмі МГУА. Розроблені схеми дозволяють збільшити шви-
дкість роботи алгоритму пропорційно кількості обчислючачів, досягаючи при цьому макси-
мальної їх завантаженості.
Ключові слова: узагальнений релаксаційний ітераційний алгоритм, паралельні обчис-
лення, принципи, схеми, метод групового урахування аргументів.
The paper suggests schemes and formulates principles of parallel computations for general-
ized relaxational iterative algorithm. The schemes developed allow to speedup the algorithm
proportianaly to number of CPU cores with maximal load each of them.
Key words: generalized relaxational iterative algorithm, parallel computations, principles,
schemes, group method of data handling.
В работе предложены принципы и схемы паралелльных вычислений в обобщённом ре-
лаксационном итерационном алгоритме МГУА. Разработанные схемы позволяют увеличить
скорость работы алгоритма пропорционально количеству вычислителей, достигая при этом
максимальной загрузке вычислителей.
Ключевые слова: обобщённый релаксационный итерационный алгоритм МГУА, парал-
лельные вычисления, принципы, схемы, метод группового учёта аугментов.
Вступление
Безостановочный технический прогресс в области вычислительных ре-
сурсов побуждает инженеров, научных исследователей и программистов ста-
вить перед собой новые научно-технические задачи, в первую очередь, деком-
позицию и распределение вычислительно-трудоёмких задач на задачи меньшей
сложности, которые могут быть решены параллельно на нескольких вычисли-
телях за приемлемое время.
Сложность вычислений в алгоритмах метода группового учёта аргумен-
тов (МГУА) характеризуются двумя параметрами: n – количество наблюдений,
m – число переменных. При этом, как отмечается в [1], число m – может быть
включать как исходные так и преобразованные переменные, что зависит от
конкретного алгоритма МГУА. Хорошо известно, что алгоритмы МГУА имеют
высокую сложность вычислений, в частности, итерационные – не менее поряд-
ка nm2 + m3[2] при осуществлении m итераций и свободой выбора решений на
каждой из них F = m, а комбинаторные – не менее порядка nm2 + m4 [3]. Однако,
они достаточно легко могут быть распараллелены. Сделаем обзор существую-
Індуктивне моделювання складних систем, випуск 5, 2013 220
mailto:andriypavlove@gmail.com
Павловв А.В.
щих решений по распараллеливанию как комбинаторных, так и итерационных
алгоритмов МГУА.
1. Обзор работ
В первую очередь были распараллелены комбинаторные алгоритмы [4 5],
поскольку являются более вычислительно трудоёмкими нежели итерационные,
а также страдают «проклятием размерности» из-за полного перебора, что есть
NP-сложная задача. Если однопроцессорные системы позволяют решать задачу
комбинаторного перебора с количеством переменных m = 20 за 10 сек., строя
при этом 220 = 1,048,576 моделей, то распараллеливание позволяет увеличивать
число моделей пропорционально увеличению количества вычислителей систе-
мы, т.е., например, строить 226 = 67,108,864 моделей за то же время, на 64 про-
цессорах. Однако, всё же это не преодолевает NP-сложность этой задачи, по-
скольку, как показано в примере выше, это позволило увеличить число m толь-
ко на 6 переменных.
Основной задачей распараллеливания комбинаторных алгоритмов явля-
лось равномерная загрузка всех процессоров, поскольку в зависимости от коли-
чества аргументов модели время её построения существенно различается [4].
В [4] предложено использовать обратные структурные вектора, т.е. про-
цессор строит модель, структурный вектор которой имеет вид (1101110), он
также обязан построить модель вида (0010001). Этот способ позволил получить
загруженность процессоров на уровне 96% каким бы ни было число m и коли-
чество процессоров. В [5] предложено использовать способ генерации струк-
турных векторов с последовательным усложнением – изменением «0» на «1» в
какой-либо ячейке вектора. Что позволило достичь почти максимальной за-
грузки – 99.8%.
Способы и принципы распараллеливания итерационных алгоритмов
МГУА рассмотрены в работах [6-7].
В [6] предложено распараллеливание алгоритма GAME – нейронной
МГУА-сети с различными типами нейронов и межслойными связями на базе
симметричной многопроцессорной (SMP) архитектуры, позволяющей несколь-
ким процессорам или ядрам обращаться к одной общей памяти. Поскольку ка-
ждый нейрон вычислительно независим от других, а время создание потоков
несравнимо мало с временем расчёта одного нейрона, было принято решение
рассчитывать каждый нейрон в отдельном параллельном потоке. Синхрониза-
ции требовал этап отбора нейронов, переходящих на следующий слой. Свойст-
во расширяемости (scalability) GAME оказалось достаточно низкой: если для
двух ядер получено ускорение в 1.7 раза, то для 8 ядер алгоритм работал только
в 3.5 раз быстрей, чем последовательная версия.
Работа [7] рассматривает три разных вида ускорения: 1) за счёт распарал-
леливания задач по потокам (процессорам); 2) векторная параллельная обра-
ботка (векторизация), за счёт использования расширенного набора команд про-
цессора (SSE – Streaming SIMD Extensions); 3) за счёт использования 64-
разрядной операционной системы. Принцип распараллеливания задач был сле-
Індуктивне моделювання складних систем, випуск 5, 2013 221
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА
дующий: низкоуровневые базовые вычисления (простые циклы) выполняются
используя векторный параллелизм, а более сложные (повторяющиеся функцио-
нальные задачи, состоящие из функций инициализации, манипуляции данными,
множество вычислительных подзадач и циклов, чтение и запись данных) вы-
полняются одновременно во многих потоках. Результаты расширяемости тех-
нологии распараллеливания по потокам показали почти линейных характер:
начиная от 2 ядер – ускорение в 2 раза, заканчивая 8 ядрами – ускорение в 7.4
раза. Эти результаты можно обобщить на разрядность операционных систем и
использование векторизации. Использование 64-разрядной системы даёт уско-
рение в 1.5 раза по сравнению с 32-х разрядной. Использование векторизации
даёт ускорение в 1.5 раза.
2. Постановка задачи
В [1] описан наиболее быстрый на сегодняшний день итерационный ал-
горитм МГУА. В отличие от всех остальных алгоритмов на этапе построения
моделей он не зависит от количества наблюдений и имеет линейную сложность
относительно числа аргументов модели. Несмотря на его колоссальное быстро-
действие – построение модели от 30-ти аргументов (итераций), n = 100000, m =
1000 лишь за 2 мин. – это время можно уменьшить за счёт распараллеливание
вычислений. Поэтому целью данной работы является выработка принципов и
схем распараллеливания основных операций обобщённого релаксационного ал-
горитма (ОРИА).
3. Принципы распараллеливания операций в ОРИА
В работе предлагается осуществить распараллеливание операций на базе
архитектуры SMP [7], рассмотренной в [6]. При распараллеливании нужно вы-
делить участки алгоритма, выполнение которых занимает основное время его
работы. Процесс работы ОРИА состоит из трёх стадий [1]: 1) преобразование
исходной матрицы; 2) расчёт матриц нормальных уравнений; 3) стадия итера-
ций, где осуществляется непосредственное построение моделей. Практически
основное время работы алгоритма расходуется на последние две стадии. В за-
висимости от количества наблюдений n, числа аргументов m и свободы выбора
F, распределение времени между ними может быть любым. Поэтому распарал-
леливанию подлежат последние две стадии.
3.1 Распараллеливание стадии подготовительных вычислений
На стадии подготовительных вычислений необходимо рассчитать вели-
чины
A
T
AXX , , , , , , (1) B
T
B XX A
T
AyX B
T
ByX A
T
Ayy B
T
Byy
где , – матрица входных перменных и вектор выхода соот-
ветсвенно; индексы A и B обозначают обучающую и проверочную последова-
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=
B
A
X
X
X ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=
B
A
y
y
y
Індуктивне моделювання складних систем, випуск 5, 2013 222
Павловв А.В.
тельности соответственно. Алгоритм расчёта первых четырёх величин в (1)
представлен ниже.
for ( i = 0; i < n; i++ )
for ( j = i; j ≤ n; j++ )
{
if ( j ≠ n )
{
for ( l = 0; j < nA; l++ )
{
value += XA[i][l]*XA[j][l];
}
XATXA[i][j] = value; value = 0;
for ( l = 0; j < nB; l++ ) B
{
value += XB[i][l]*XB BB[j][l];
}
XBTXB[i][j] = value; B
}
else
{
for ( l = 0; j < nA; l++ )
{
XATyA[ind] += XA[i][l]*yA[l];
}
for ( l = 0; j < nB; l++ ) B
{
XBTyB[ind] += XB BB[i][l]*yB[l]; B
}
ind++;
}
}
Для равномерной загрузки вычислителей минимальная задача, подавае-
мая на вычислитель будет состоять из расчёта (1) для двух значений i, равно-
удалённых от значения n/2, т.е., для i = 0 и i = n – 1, i = 1 и i = n – 2,… Т.е. в об-
щей сложности имеем n/2 задач при чётном n. Если n нечётно, n/2 + 1 задач, од-
на из которых средней сложности для значения i = n/2 + 1. Не ограничивая
общности, пусть n – чётное. Имея k вычислителей, каждый из них получает:
⎣ ⎦ ⎡ ⎤ ⎡ ⎤⎩
⎨
⎧
−+
−=
=
)2/(,1)2/()2/(
,)2/( 11
knостальныеknполучаютейвычислителknпервые
целоеNеслизадачknN
N ,
где - остаток от деления, ⎣ ⎦ ⎡ ⎤ - результат деления с отбрасываниям остатка.
Расчёт величин , можно реализовать паралельно на двух вычисли-
телях.
A
T
Ayy B
T
Byy
3.2 Распараллеливание стадии построения моделей
Процесс построения модели
i
m
i
ixy ∑
=
=
1
θ
Індуктивне моделювання складних систем, випуск 5, 2013 223
Принципы параллельных вычислений в релаксационном итерационном алгоритме МГУА
в ОРИА состоит в итеративном добавлении к текущей модели ry) r-й итерации
нового аргумента xi ∈ miix ,1}{ ==ℵ , при этом строиться m моделей вида
irirririr xyy ,,,,1 ωϖ )))) +=+ , Ii∈ , (2)
где I – множество индексов аргументов. На каждой итерации выполняется се-
лекция F лучших моделей Fjjry ,1,1 }{ =+
)
, которые будут усложняться по фор-
муле (2) на следующей итерации ОРИА. Поэтому общее число моделей, кото-
рые нужно построить на r-й итерации равно mF.
Для поиска оценок коэффицентов ir,ϖ) , ir ,ω) решается Fm задач вида:
||minarg},{ ,,,,,,,,,
,,
irArjrArAjirjir
jiji
xyy ωϖωϖ
ωϖ
−−=
ℜ∈ℜ∈
)))
, mi ,1= , Fj ,1= , (3)
Для выбора F лучших моделей r + 1 итерации решаются следующие Fm
задач:
||minarg||minarg}{ ,,,,
,1,,1
,,1,
,1,,1,1,1, irBrjrBrB
Fjmi
jirBB
FjmiFllrB xyyyyy ωϖ ))))) −−=−=
==
+
===+ (4)
Таким образом на каждой итерации имеем Fm задач (3), (4), которые мо-
гут решаться независимо.
Эта стадия распараллеливается аналогично работе [6], однако количество
создаваемых потоков должно быть равно количеству вычислителей, дабы опе-
рационная система не тратила время на переключение между потоками, как это
происходит в [6], когда количество потоков больше числа вычислителей. Син-
хронизации потоков подлежит стадия селекции лучших F моделей.
Пусть мы имеем k вычислителей, тогда при распределении Fm задач мо-
гут возникнуть такие случаи:
1. Fm < k. Каждый из Fm первых вычислителей загружен одной задачей,
остальные (k – Fm) – свободны.
2. Fm = k. Все вычислтели загружены и каждый из них решает одну за-
дачу.
3. Fm > k. Первые вычислителей решают ⎣ kFm / ⎦ ⎡ ⎤kFm / + 1 задач, а ос-
тальные – задач. ⎡ kFm / ⎤
Предложенные схемы распараллеливания двух основных стадий ОРИА
позволяют получить максимальную загрузку вычислителей при любом их ко-
личестве.
Індуктивне моделювання складних систем, випуск 5, 2013 224
Павловв А.В.
4. Выводы
Предложенные в работе принципы и схемы распараллеливаня вычисле-
ний обобщённого релаксационного итерационного алгоритма МГУА позволяют
увеличить скорость работы алгоритма пропорционально количеству вычисли-
телей при максимальной (почти равномерной) их загрузке.
Литература
1. Павлов А. В. Обобщённый релаксационный итерационный алгоритм
МГУА // Індуктивне моделювання складних систем. Зб. наук. праць, вип. 2. –
К.: МННЦІТС НАНУ, 2011. – С. 95-108.
2. А. В. Павлов, В. С. Степашко Рекуррентные алгоритмы расчёта коэф-
фициентов и критериев селекции в релаксационном алгоритме МГУА // Кибер-
нетика и вычислительная техника. – 2011. – Вып. 165. – С. 72-82.
3. Єфіменко С.М., Степашко В.С. Рекурентний алгоритм методу Гауса для
розв’язання систем лінійних рівнянь у задачі оцінювання параметрів
регресійних моделей // Відбір і обробка інформації. Міжвідомчий збірник нау-
кових праць. – №36 (112). – 2012. – С. 48-55
4. O.A. Koshulko, A.I. Koshulko Adaptive parallel implementation of the
Combinatorial GMDH algorithm. // Proc. of IWIM 2007. International workshop on
inductive modeling, CTU in Prague, 2007, p. 71-77. ISBN 978-80-01-03881-9
5. Volodymyr Stepashko, Serhiy Yefimenko Optimal Paralleling for Solving
Combinatorial Modelling Problems // Proc. of IСIM 2008. 2nd International confer-
ence on inductive modeling, Kyiv, 2008, p. 172-175. ISBN 978-966-02-4889
6. Pavel Kordik, Jakub Spirk, Ivan Simecek Parallel computing of GAME
models // Proc. of IСIM 2008. 2nd International conference on inductive modeling,
Kyiv, 2008, p. 160-163. ISBN 978-966-02-4889
7. Frank Lemke Parallel Self-organizing Modeling // Proc. of IСIM 2008. 2nd
International conference on inductive modeling, Kyiv, 2008, p. 176-183. ISBN 978-
966-02-4889
8. http://en.wikipedia.org/wiki/Symmetric_multiprocessing.
Індуктивне моделювання складних систем, випуск 5, 2013 225
|