О реализации параллельного алгоритма для решения задач равновесной упаковки
Рассматривается параллельная реализация метода мультистарта для нахождения решений задач равновесной упаковки неодинаковых кругов в круг наименьшего радиуса. Приведены результаты решения задачи на вычислительном кластере в системе MPI. Для вычислительных экспериментов использовался кластер Института...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2015 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/112413 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О реализации параллельного алгоритма для решения задач равновесной упаковки / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — С. 154-159. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860243000826789888 |
|---|---|
| author | Лиховид, А.П. |
| author_facet | Лиховид, А.П. |
| citation_txt | О реализации параллельного алгоритма для решения задач равновесной упаковки / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — С. 154-159. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматривается параллельная реализация метода мультистарта для нахождения решений задач равновесной упаковки неодинаковых кругов в круг наименьшего радиуса. Приведены результаты решения задачи на вычислительном кластере в системе MPI. Для вычислительных экспериментов использовался кластер Института кибернетики им. В.М. Глушкова НАН Украины СКИТ.
Розглядається паралельна реалізація методу мультистарта для знаходження розв’язків задач рівноважної упаковки неоднакових кіл у коло найменшого радіуса. Наведено результати розв'язання задачі на обчислювальному кластері в системі MPI. Для обчислювальних експериментів використовувався кластер Інституту кібернетики імені В.М. Глушкова НАН України СКІТ.
A parallel implementation of multistart method for finding solutions of problems of balance circular packing unequal circles into a circle of least radius is considered. The results of solution of the problem on a computing cluster in MPI system are presented. For the computational experiments a cluster of the Institute of Cybernetics SCIT was used.
|
| first_indexed | 2025-12-07T18:32:21Z |
| format | Article |
| fulltext |
154 Теорія оптимальних рішень. 2015
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Рассматривается параллельная
реализация метода мультистар-
та для нахождения решений за-
дач равновесной упаковки неоди-
наковых кругов в круг наименьше-
го радиуса. Приведены результа-
ты решения задачи на вычисли-
тельном кластере в системе MPI.
Для вычислительных эксперимен-
тов использовался кластер Инсти-
тута кибернетики им. В.М. Глуш-
кова НАН Украины СКИТ.
А.П. Лиховид, 2015
УДК 519.8
А.П. ЛИХОВИД
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО
АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧ
РАВНОВЕСНОЙ УПАКОВКИ
Введение. В данной статье рассматривается
параллельная реализация алгоритма для
нахождения решений задачи равновесной
упаковки неодинаковых кругов в круг
наименьшего радиуса, описанной в работе
[1]. Задача равновесной упаковки неодина-
ковых кругов в круг наименьшего радиуса
возникает в задачах плотной упаковки па-
раллельных одинаковых по высоте круговых
цилиндров в цилиндрический контейнер при
ограничениях на динамическое равновесие
системы [2, 3]. Динамическое равновесие
определяется требованием, чтобы центр тя-
жести системы круговых цилиндров нахо-
дился в центре кругового контейнера.
Математическая модель задачи равновес-
ной упаковки неравных кругов может быть
сформулирована в виде различных многоэкс-
тремальных задач математического про-
граммирования [4]. Одна из данных форму-
лировок – это предмет исследования в дан-
ной работе. Для нее приводится алгоритм
нахождения ее глобального оптимального
решения, который базируется на использова-
нии параллельной реализации метода муль-
тистарта, в котором для поиска локальных
решений выбран r -алгоритм Шора [5].
Также приведены результаты вычислитель-
ных экспериментов. Для вычислительных
экспериментов использовался кластер Инсти-
тута кибернетики им. В.М. Глушкова НАН
Украины СКИТ (суперкомпьютер для реали-
зации информационных технологий) [6].
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА …
Теорія оптимальних рішень. 2015 155
Математическая модель задачи. Имеется семейство кругов iS с радиуса-
ми ir и весами iw , =1, ,i m . Полагаем, что центр тяжести круга iS находится
в его центре. Равновесной упаковкой семейства кругов iS , =1, ,i m , в круг S
назовем такую их упаковку, чтобы радиус круга S был минимальным и центр
тяжести семейства кругов iS , =1, ,i m , совпадал с центром круга S .
Не ограничивая общности будем считать, что центр круга S находится в
начале неподвижной системы координат. Пусть ( , )i ix y – неизвестный центр
круга iS , r – неизвестный радиус круга S . Обозначим известные величины
=1
= /
m
i i ii
w w , =1, ,i m , и очевидную нижнюю границу на искомый радиус
=1, ,
= maxlow i
i m
r r . Тогда равновесной упаковке семейства кругов iS , =1, ,i m ,
соответствует многоэкстремальная задача нелинейного программирования:
*
, ,
= min
r x y
r r (1)
при ограничениях
2 2 2( ) , = 1, , ,i i ix y r r i m (2)
2 2 2( ) ( ) ( ) , 1 < ,i j i j i jx x y y r r i j m (3)
=1 =1
= 0, = 0,
m m
i i i i
i i
x y (4)
lowr r , (5)
где
1( ,..., )mx x x , 1( ,..., )my y y .
С помощью негладких штрафов задачу (1) – (5) можно свести к задаче
безусловной минимизации негладкой штрафной функции. Тогда алгоритм
поиска наилучшего решения задачи (1) – (5), основанный на методе
мультистарта, состоит в следующем. Для заданного набора стартовых точек
осуществляется поиск локальных минимумов негладкой штрафной функции с
помощью модификации r-алгоритма. Наилучший из локальных минимумов
функции, для которого штрафная функция близка к нулю, принимается за
решение задачи (1) – (5).
Параллельная реализация метода мультистарта. Метод мультистарта
для нахождения глобального оптимального решения многоэкстремальной зада-
чи можно представить в виде следующей процедуры: с помощью алгоритмов
локального поиска находятся оптимальные локальные решения с различных
начальных точек, генерируемых случайным или детерминированным образом, и
среди полученных решений выбирается наилучшее (минимальное или макси-
мальное). При достаточно большом количестве запусков поиска локальных ре-
шений есть вероятность найти глобальное оптимальное решение. Очевидно, что
этот метод является существенно трудоемким, но при этом его легко можно
распараллелить и реализовать вычисления, например, на кластере.
А.П. ЛИХОВИД
156 Теорія оптимальних рішень. 2015
В данной работе для параллельной реализации метода мультистарта исполь-
зовалась процедура «Master-Slave» [7]. Решение задачи проводится на p про-
цессорах. Сгенерированная случайным образом в «ведущем» (Master) процес-
соре начальная точка передается на любой другой свободный ( 1)p (Slave)
процессор с помощью операции пересылки системы MPI. Там происходит вы-
числение локального оптимального решения для этой начальной точки с помо-
щью r-алгоритма. Затем найденное оптимальное решение передается в «веду-
щий» процессор, где происходит сравнение полученного оптимального решения
с наилучшим из найденных до этого момента значением («рекордом»). Если те-
кущее решение меньше «рекорда», то оно становится «рекордом». По истечении
заданного количества запусков поиска локального решения значение «рекорда»
принимается за решение исходной задачи. Дополнительно значение «рекорда»
используется для генерации начальных точек в круге радиуса равного этому
значению.
Приведенный параллельный метод мультистарта был реализован на языке
программирования С++ в программной среде MPI. Для нахождения локальных
решений многоэкстремальной задачи использовался ( )r -алгоритм с постоян-
ным коэффициентом растяжения пространства и адаптивной регулировкой
шага в направлении нормированного антисубградиента. Начальные точки для
метода мультистарта генерировались случайным образом с помощью генератора
равномерного распределения в круге заданного радиуса, который последова-
тельно уточнялся по мере нахождения лучшего локального минимума. В каче-
стве генератора псевдослучайных чисел в интервале [0,1]n
использовалась реа-
лизация эффективного алгоритма, который называется «Вихрь Мерсенна» [8].
Далее приводятся результаты численных экспериментов на кластерном
комплексе СКИТ Института кибернетики имени В.М. Глушкова НАН Украины
для решения одной задачи равновесной упаковки [1].
Вычислительный эксперимент. Вычислительные эксперименты проводи-
лись для вышеописанной задачи со следующими параметрами:
m=40;
ir =[106 112 98 105 93 103 82 93 117 81 89 92 109 104 115 110
114 89 82 120 108 86 93 100 102 106 111 107 109 91 111 91 101
91 108 114 118 85 87 98];
iw =[11 12 9 11 8 10 6 8 13 6 7 8 11 10 13 12 12 7 6 14 11 7 8
10 10 11 12 11 11 8 12 8 10 8 11 12 13 7 7 9].
Для данного примера вначале выполнялось исследование параллельного
ускорения и эффективности алгоритма. Параллельное ускорение вычисляется по
формуле
0 / , 1, ,i iS t t i n , где
0t – время работы последовательного алгорит-
ма, а
it – время решения задачи параллельным алгоритмом с использованием i
процессоров. Эффективность параллельного алгоритма вычисляется по формуле
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА …
Теорія оптимальних рішень. 2015 157
/i iE S i . Для этого исследования количество генерируемых точек для метода
мультистарта и, соответственно, запусков поиска локального решения
равнялось 50. Общее количество процессоров кластера варьировалось от 1 до
24.
Результаты исследования параллельного ускорения и эффективности для те-
стовой задачи представлены в табл.1 и на рисунке. Здесь n – общее число про-
цессоров, t – время решения задачи в секундах,
iS – параллельное ускорение,
iE – эффективность параллельного алгоритма. На рисунке показана зависимость
времени решения тестового примера от количества использованных процессо-
ров. Из табл. 1 и рисунка видно, что, например, для четырех процессоров время
решения задачи уменьшается в 2,65 раза, для восьми – в 5,38 раза, шестнадцати
– в 7,87 раза, а для двадцати четырех – в 9,37 раза. Начиная с количества про-
цессоров равного 12, дальнейшее добавление процессоров не влияет существен-
но на время решения задачи.
ТАБЛИЦА 1. Время решения, параллельное ускорение и эффективность
для первого вычислительного эксперимента
n t
iS
iE
1 26.51 1.00 1.00
2 26.71 0.99 0.50
3 15.05 1.76 0.59
4 10.01 2.65 0.66
5 7.94 3.36 0.67
8 4.92 5.38 0.67
12 3.20 8.27 0.69
16 3.37 7.87 0.49
20 2.32 11.45 0.57
24 2.83 9.37 0.39
26,51 26,71
15,05
10,01
7,94
4,92
3,20 3,37 2,32 2,83
0,00
5,00
10,00
15,00
20,00
25,00
30,00
1 2 3 4 5 8 12 16 20 24
количество процессоров
в
р
е
м
я
р
е
ш
е
н
и
я
А.П. ЛИХОВИД
158 Теорія оптимальних рішень. 2015
РИСУНОК. Зависимость времени решения от количества процессоров
Вторым вычислительным экспериментом был запуск программы для решения
тестового примера для большого количества начальных точек. Проведено два
расчета на кластере СКИТ-3. В-первом количество генерируемых точек было
выбрано 10000, а во втором – 100000. В обоих случаях количество процессоров
равнялось 24. В табл. 2 приведены найденные лучшие оптимальные значения
радиусов и времена нахождения решений.
ТАБЛИЦА 2. Время решения и полученные оптимальные значения
для второго вычислительного эксперимента
Количество
генерируемых точек
Полученные
оптимальные значения
Времена нахождения
решений (сек)
10000 715.61 360
100000 714.91 4665
Как видно из табл. 2 в результате вычислительных экспериментов найдено
рекордное решение со значением оптимального радиуса 714.91.
Заключение. Результаты вычислительных экспериментов подтверждают
возможность применения параллельной реализации метода мультистарта для
нахождения решений практических задач равновесной упаковки. Эту реализа-
цию можно улучшить, используя более совершенные схемы генерации началь-
ных точек. В настоящее время разрабатывается программное обеспечение для
решения задач равновесной упаковки на кластере СКИТ.
О.П. Лиховид
ПРО РЕАЛІЗАЦІЮ ПАРАЛЕЛЬНОГО АЛГОРИТМУ ДЛЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ
РІВНОВАЖНОЇ УПАКОВКИ
Розглядається паралельна реалізація методу мультистарта для знаходження розв’язків задач
рівноважної упаковки неоднакових кіл у коло найменшого радіуса. Наведено результати
розв'язання задачі на обчислювальному кластері в системі MPI. Для обчислювальних експе-
риментів використовувався кластер Інституту кібернетики імені В.М. Глушкова НАН України
СКІТ.
O.P. Lykhovyd
ON IMPLEMENTATION OF PARALLEL ALGORITHM FOR SOLVING BALANCE
CIRCULAR PACKING PROBLEMS
A parallel implementation of multistart method for finding solutions of problems of balance circular
packing unequal circles into a circle of least radius is considered. The results of solution of the
О РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА …
Теорія оптимальних рішень. 2015 159
problem on a computing cluster in MPI system are presented. For the computational experiments a
cluster of the Institute of Cybernetics SCIT was used.
1. Стецюк П.И., Романова Т.Е., Коваленко А.А. Комп’ютерна програма Balance circular
packing // Свідоцтво про реєстрацію авторського права на твір № 55689. Україна. Мініс-
терство освіти і науки. Державний департамент інтелектуальної власності. – Дата реєст-
рації 21.07.2014.
2. Коваленко А.А., Панкратов А.В., Романова Т.Е., Стецюк П.И. Упаковка круговых цилин-
дров в цилиндрический контейнер с учетом специальных ограничений поведения системы
// Журнал обчислювальної та прикладної математики. – 2013. – № 1(111). – С. 126 – 134.
3. Stoyan Yu., Romanova T. Mathematical Models of Placement Optimisation: Two- and Three-
Dimensional // In book «Modeling and Optimization in Space Engineering. Springer Optimiza-
tion and Its Applications» / G. Fasano, J.D. Pintеr, eds. – Springer. – New York. – 2012. –
P. 363 –388.
4. Ненахов Э.И., Романова Т.Е., Стецюк П.И. Равновесная упаковка кругов в круг
минимального радиуса // Теорія оптимальних рішень. – К.: Ін-т кібернетики імені
В.М. Глушкова НАН України, 2013. – С. 143 – 153.
5. Шор Н.З., Стецюк П.И. Использование модификации r-алгоритма для нахождения гло-
бального минимума полиномиальных функций // Кибернетика и системный анализ. –
1997. – № 4. – C. 28 – 49.
6. Кластерный комплекс Института кибернетики. Кластерный комплекс СКИТ.
https://icybcluster.org.ua/.
7. Mersenne Twister home page, with C code.
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
8. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.
– 608 с.
Получено 10.03.2015
https://icybcluster.org.ua/
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
|
| id | nasplib_isofts_kiev_ua-123456789-112413 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:32:21Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Лиховид, А.П. 2017-01-20T21:57:20Z 2017-01-20T21:57:20Z 2015 О реализации параллельного алгоритма для решения задач равновесной упаковки / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — С. 154-159. — Бібліогр.: 8 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112413 519.8 Рассматривается параллельная реализация метода мультистарта для нахождения решений задач равновесной упаковки неодинаковых кругов в круг наименьшего радиуса. Приведены результаты решения задачи на вычислительном кластере в системе MPI. Для вычислительных экспериментов использовался кластер Института кибернетики им. В.М. Глушкова НАН Украины СКИТ. Розглядається паралельна реалізація методу мультистарта для знаходження розв’язків задач рівноважної упаковки неоднакових кіл у коло найменшого радіуса. Наведено результати розв'язання задачі на обчислювальному кластері в системі MPI. Для обчислювальних експериментів використовувався кластер Інституту кібернетики імені В.М. Глушкова НАН України СКІТ. A parallel implementation of multistart method for finding solutions of problems of balance circular packing unequal circles into a circle of least radius is considered. The results of solution of the problem on a computing cluster in MPI system are presented. For the computational experiments a cluster of the Institute of Cybernetics SCIT was used. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О реализации параллельного алгоритма для решения задач равновесной упаковки Про реалізацію паралельного алгоритму для розв’язування задач рівноважної упаковки On implementation of parallel algorithm for solving balance circular packing problems Article published earlier |
| spellingShingle | О реализации параллельного алгоритма для решения задач равновесной упаковки Лиховид, А.П. |
| title | О реализации параллельного алгоритма для решения задач равновесной упаковки |
| title_alt | Про реалізацію паралельного алгоритму для розв’язування задач рівноважної упаковки On implementation of parallel algorithm for solving balance circular packing problems |
| title_full | О реализации параллельного алгоритма для решения задач равновесной упаковки |
| title_fullStr | О реализации параллельного алгоритма для решения задач равновесной упаковки |
| title_full_unstemmed | О реализации параллельного алгоритма для решения задач равновесной упаковки |
| title_short | О реализации параллельного алгоритма для решения задач равновесной упаковки |
| title_sort | о реализации параллельного алгоритма для решения задач равновесной упаковки |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/112413 |
| work_keys_str_mv | AT lihovidap orealizaciiparallelʹnogoalgoritmadlârešeniâzadačravnovesnoiupakovki AT lihovidap prorealízacíûparalelʹnogoalgoritmudlârozvâzuvannâzadačrívnovažnoíupakovki AT lihovidap onimplementationofparallelalgorithmforsolvingbalancecircularpackingproblems |