Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур
Створено паралельні версії алгоритму Флойда-Уоршала для SMP- і MPP-архітектур та досліджено і проаналізовано їх часові характеристики. Визначено доцільність застосування певної архітектури в залежності від розмірності задачі. Созданы параллельные версии алгоритма Флойда-Уоршала для SMP- и MPP-архите...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2011 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83620 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур / С.Д. Погорілий, М.І. Трибрат, Б.Ю. Вітель // Мат. машини і системи. — 2011. — № 4. — С. 20-30. — Бібліогр.: 7 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860245703314374656 |
|---|---|
| author | Погорілий, С.Д. Трибрат, М.І. Вітель, Б.Ю. |
| author_facet | Погорілий, С.Д. Трибрат, М.І. Вітель, Б.Ю. |
| citation_txt | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур / С.Д. Погорілий, М.І. Трибрат, Б.Ю. Вітель // Мат. машини і системи. — 2011. — № 4. — С. 20-30. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Створено паралельні версії алгоритму Флойда-Уоршала для SMP- і MPP-архітектур та досліджено і проаналізовано їх часові характеристики. Визначено доцільність застосування певної архітектури в залежності від розмірності задачі.
Созданы параллельные версии алгоритма Флойда-Уоршала для SMP- и MPP-архитектур, исследованы и проанализированы их временные характеристики. Определена целесообразность применения определенной архитектуры в зависимости от размерности задачи.
Parallel versions of the Floyd-Warshall algorithm for SMP-and MPP-architectures were created. Their temporal characteristics were investigated and analyzed. It was shown that the expediency of particular architecture usage depends on the dimension of the task.
|
| first_indexed | 2025-12-07T18:36:27Z |
| format | Article |
| fulltext |
20 © Погорілий С.Д., Трибрат М.І., Вітель Д.Ю., 2011
ISSN 1028-9763. Математичні машини і системи, 2011, № 4
УДК 681.3
С.Д. ПОГОРІЛИЙ, М.І. ТРИБРАТ, Д.Ю. ВІТЕЛЬ
ДОСЛІДЖЕННЯ ПАРАЛЕЛЬНИХ ВЕРСІЙ АЛГОРИТМУ ФЛОЙДА-УОРШАЛА
ДЛЯ SMP- ТА MPP-АРХІТЕКТУР
Анотація. Створено паралельні версії алгоритму Флойда-Уоршала для SMP- і MPP-архітектур
та досліджено і проаналізовано їх часові характеристики. Визначено доцільність застосування
певної архітектури в залежності від розмірності задачі.
Ключові слова: SMP-архітектури, MPP-архітектури, найкоротший шлях між джерелом даних
та їх приймачем, алгоритм Флойда-Уоршала, механізми взаємодії IPC, синхронізація, спін-
блокування, потік, процес, технологія MPI, кеш-пам’ять.
Аннотация. Созданы параллельные версии алгоритма Флойда-Уоршала для SMP- и MPP-
архитектур, исследованы и проанализированы их временные характеристики. Определена целесо-
образность применения определенной архитектуры в зависимости от размерности задачи.
Ключевые слова: SMP-архитектуры, MPP-архитектуры, кратчайший путь между источником
данных и их приемником, алгоритм Флойда-Уоршала, механизмы взаимодействия IPC, синхрони-
зация, спин-блокировка, поток, процесс, технология MPI, кэш-память.
Abstract. Parallel versions of the Floyd-Warshall algorithm for SMP-and MPP-architectures were
created. Their temporal characteristics were investigated and analyzed. It was shown that the expediency
of particular architecture usage depends on the dimension of the task.
Keywords: SMP-architecture, MPP-architecture, the shortest path between a data source and the
receiver, the Floyd-Warshall algorithm, mechanisms of interaction IPC, synchronization, spin locks,
thread, process, MPI technology, cache memory.
1. Вступ
Одним із головних факторів, що визначає ефективність функціонування сучасних
комп’ютерних мереж, є алгоритм знаходження найкоротшого шляху між джерелом даних
та їх приймачем. На практиці до цих алгоритмів висувається ряд вимог, які включають то-
чність, надійність, стабільність, справедливість (по відношенню до вузлів, які обслугову-
ються) та оптимальність. Задовольняючи цим критеріям, алгоритм може бути покладений
за основу протоколу маршрутизації, який повинен також визначати набір правил взаємодії
вузлів, що приймають участь у процесі маршрутизації. Поряд з алгоритмами Белмана-
Форда (протокол RIP) та Дейкстри (протокол OSPF), алгоритм Флойда-Уоршала дозволяє
знаходити найкоротші шляхи між усіма парами вершин (складність – ( )3nΟ , де n – зага-
льна кількість вузлів мережі). Проте він не може працювати із графами, що мають цикли
від’ємної ваги (на відміну від алгоритму Белмана-Форда).
Алгоритм знаходить оптимальні шляхи, визначаючи на кожному кроці k вагову
матрицю kD (що складається з елементів k
ijd ) через вагову матрицю на попередньому
кроці ( 1−kD ) [1]:
{ 0 при ребра вага
0 при ),min( 111
=→−
≠+
= −−−
kjiijw
kddd
d k
kj
k
ik
k
ij
k
ij .
Кількість кроків дорівнює кількості вузлів графа n . Крім того, на кожній ітерації
визначається матриця передування kP , що на перетині i -го рядка та j -го стовпчика міс-
тить елемент k
ijπ – номер вершини, яка передує j -тій у найкоротшому шляху з i в j :
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 21
{ або при
випадкуіншому в
∞=== ijwjiNIL
i
k
ijπ ,
{ )( при
випадкуіншому в
1111
1
−−−−
−
+≤=
k
kj
k
ik
k
ij
k
j
k
kj
k
ij
dddiπ
π
π .
Мета роботи полягає у дослідженні часу виконання паралельних реалізацій алгори-
тму Флойда-Уоршала в залежності від кількості вузлів (MPP-архітектури) та ядер мікроп-
роцесора (SMP-архітектури).
2. Архітектура комп’ютерних систем зі спільною та розподіленою пам’яттю
З появою багатоядерних процесорів, парадигми паралельних кластерних обчислень
з’явилась можливість оптимізувати роботу алгоритмів за критерієм часу, використовуючи
технології розпаралелювання. Створені таким чином реалізації алгоритмів призначені для
виконання в системах із розподіленою пам'яттю або в системах зі спільною пам'яттю.
До систем зі спільною пам’яттю належать багатоядерні комп’ютери та мультипро-
цесори. Їх особливість полягає у тому, що всі обчислювальні одиниці (ядра чи процесори)
мають доступ до усієї наявної в системі пам'яті на відміну від систем із розподіленою
пам’яттю (мультикомп’ютери, кластери), де кожен обчислювальний вузол контролює дос-
туп до своєї ділянки. З одного боку, це приводить до того, що такі системи легше програ-
муються, ніж системи із розподіленою пам’яттю. Проте, з іншого боку, їх апаратна
реалізація складніша. Ці системи поділяють на такі підкласи, як UMA, NUMA, COMA,
різниця між якими визначається часом доступу до різних частин оперативної пам'яті та її
організацією (розподілом між обчислювальними вузлами) [2]. Методи побудови застосу-
вань для систем зазначених двох класів є суттєво різними.
3. Підходи до створення паралельних застосувань для систем зі спільною пам'яттю
Створення паралельних застосувань у системах зі спільною пам'яттю цілком залежить від
цільової операційної системи (ОС). Остання, виконуючи роль інтерфейсу між застосуван-
ням і апаратним забезпеченням, постачає ряд методів для доступу до ресурсів та створення
паралельних потоків інструкцій на окремих вузлах системи. Більшість нових технологій
грунтуються на цих ключових методах і призначені спростити процесс побудови пара-
лельних застосувань, пропонуючи нові підходи.
Центральними сутностями сучасних ОС є потік та процесс [3, 4]. Основне їх при-
значення – ефективне планування використання ресурсу процесорного часу та захист за-
стосувань від взаємного впливу. Саме по собі застосування є статичним набором команд,
проте процес ОС – це набір ресурсів, даних та правил роботи ОС з ними. При створенні
процес отримує такі ресурси, як віртуальний адресний простір, процесорний час, початко-
вий потік. Будь-які два процеси в системі ізольовані і не можуть (без додаткових
механізмів ОС) впливати один на одного. Одним із підходів до створення паралельних за-
стосувань для систем зі спільною та розподіленою пам'яттю є використання паралельних
процесів, які виконуються на обчислювальних вузлах системи. Інший підхід грунтується
на використанні набору паралельних потоків у межах одного процессу. Потік фактично
являє собою набір інструкцій, що послідовно обробляються одним вузлом системи. Проте
з потоками також асоціюють додаткові ресурси – контекст (збережений набір регістрів
CPU, що використовується ОС у процесах планування виконання потоків), стек (область
віртуального адресного простору з динамічним виділенням пам'яті і LIFO-способом досту-
пу), локальна пам'ять потоку (TLS – пам'ять, що доступна лише даному потоку). Різниця в
зазначених методах формування паралельного застосування полягає в тому, що потоки в
межах процесу не є ізольованими (окрім TLS-ресурсу) і тому фактично можуть
22 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Бар’єр, що підтримує
Атомарна зміна лічильника
Активне очікування
Атомарне умовне скидання лічильника
Spin-block
1
Spin-block
2
Потік інструкцій
Рис. 1. Бар’єр, що використовує спін-блокування
взаємодіяти між собою без додаткових механізмів системи. Процеси, в свою чергу,
взаємодіють між собою за допомогою механізмів interprocess comunications (IPC) системи,
до яких належать:
• Спільна пам'ять (в Unix-системах – shared memory objects, в Windows – file map-
ping). Підхід, при якому одна і та сама ділянка фізичної пам'яті відображається у віртуаль-
ні адресні простори декількох процесів.
• Гнізда (Berkley sockets). Обмін даними між процесами в мережі грунтується на
цьому механізмі. Можна використовувати як для систем зі спільною, так із розподіленою
пам'яттю.
• Конвейєри (pipes) пропонують підхід з використанням структур типу FIFO для
обміну даними між процесами як в одній системі, так і в різних.
• Інші системно залежні механізми (Windows – mailbox, DDE, console buffer і т.д).
Створення каналу обміну даними зазначеними методами вимагає часового ресурсу.
Далі наведені приклади системних механізмів ОС Windows, що дозволяють значно приш-
видшити обмін даними між процесами, накладаючи при цьому ряд обмежень.
1. Використання процесів-відлагоджувачів дозволяє безпосередньо виконувати за-
пис-зчитування в чужому адресному просторі, проте цей метод вимагає від таких процесів
знання розподілу виділених сторінок пам'яті (це створює додаткові витрати часу). Крім то-
го, ці процеси мають володіти відповідними правами доступу до чужого адресного прос-
тору.
2. Спільний сегмент пам’яті. При створенні процесу ОС виділяє фізичну пам’ять
для набору інструкцій та даних. При цьому зміна процесом певної сторінки коду приведе
до того, що в фізичній пам’яті з’явиться змінена копія. Оригінальні сторінки пам'яті також
лишаються виділеними (механізм копіювання при записі). При застосуванні можна
змінити дану поведінку копіювання сторінок. Це призведе до того, що декілька процесів
зможуть модифікувати сторінки без копіювання. Але при цьому процеси мають бути по-
роджені з одного виконуваного файла.
3. Буфер консолі. Батьківський і породжений процеси можуть мати спільну консоль
і відповідні буфери вводу-виводу. Але процеси, що взаємодіють таким чином, мають на-
лежати одному дереву процесів з усієї ієрархії.
4. Особливості синхронізації для Windows-платформ
Синхронізація є одним із найважливіших способів взаємодії декількох потоків (одного чи
різних процесів), оскільки забезпечує атомарний доступ до спільних даних. Більшість ме-
ханізмів синхронізації Windows передбачає використання об’єктів ядра системи. Тому їх
застосування ініціює виконання додаткового набору інструкцій, що переводять CPU з од-
ного режиму (кільця захисту) в інший. Виконання цих додаткових команд може значно
знизити продуктивність усього застосування.
Одним із широко застосованих шаблонів паралельного програмування є синхроні-
зація типу
бар’єр. Ідея
такої взаємодії
потоків поля-
гає у тому, що
в кожному з
останніх існує
група інструк-
цій, по досяг-
ненні якої по-
дальше виконання даного потоку припиняється доти, доки всі інші потоки із групи не до-
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 23
сягнуть даного набору. Ці інструкції називають бар’єром. Побудувати такий спосіб взає-
модії на існуючих примітивах ОС можна за допомогою механізму спін-блокування (spin-
blocking). Схему реалізації бар’єра наведено на рис. 1.
Спін-блокування використовує один спільний для всіх потоків у групі лічильник,
доступ до якого атомарний (на Windows-платформі реалізується за допомогою Interlocked-
функцій, що не переводять CPU в інше кільце захисту). Проходячи набір інструкцій, потік
змінює лічильник і входить в очікування, що реалізується за допомогою циклу. Це очіку-
вання активне і споживає ресурс процесорного часу. Для поліпшення часових характерис-
тик спін-блокування можна скористатися іншим механізмом. Кожний системний потік має
пріоритет, що надається йому системою. Для кожного пріоритету ОС містить чергу актив-
них (готових отримати ресурс процесорного часу) потоків. Якщо черга з найвищим пріо-
ритетом не порожня, то потоки з цієї черги обслуговуються CPU. В іншому випадку об-
слуговуються потоки з нижчим пріоритетом. Обслуговування полягає в тому, що система
надає можливість потоку виконуватись на CPU (одному з ядер) певний квант часу
(Windows XP – 10 ms). Після цього стан потоку зберігається в контексті, а сам потік
розміщується в кінці своєї черги. Поведінкою планувальника частково можна керувати
програмою. Windows надає можливість потоку за допомогою API-функції Sleep передати
залишок свого кванта іншому потоку в черзі. Таким чином, активне очікування можна ор-
ганізувати ефективніше, ніж при використанні інших примітивів синхронізації. Вихід із
очікування відбувається за умови проходження останнім потоком з групи атомарної зміни
лічильника. Цих дій достатньо для організації бар'єра, який потоки проходять один раз за
своє існування. Щоб створити бар'єр, який потоки проходять циклічно, слід додати ще од-
не спін-блокування з іншим лічильником. Крім того, після кожного активного очікування
потоки повинні модифікувати вектор лічильників певним чином. Реалізація такого роду
бар'єра була використана в паралельній багатопотоковій та багатопроцесній версіях алго-
ритму. Перевагами спін-блокування є гарна маштабованість, ефективність, мала
ресурсоємність реалізації. Недоліком є активне очікування і складність реалізації для сис-
тем із розподіленою пам'яттю.
5. Взаємодія потоків у системах із розподіленою пам'яттю
Основний спосіб взаємодії потоків у розподілених системах описується шаблоном Message
Passing, ідея якого полягає в тому, що для доступу до даних деякого потоку з групи
реалізується певний інтерфейс чи протокол обміну. Фактично, використовуючи цей
інтерфейс, один потік може запросити відповідні дані чи дію у іншого потоку. При цьому
інший потік має реалізувати певну поведінку для обслуговування запитів до нього. В такій
схемі окремо можна виділити синхронну та асинхронну взаємодії. Виділення в системі го-
ловного потоку (або арбітра) або певної їх сукупності дозволяє створити синхронізацію,
позбавлену тупикових ситуацій.
Частковим випадком Message Passing взаємодії є клієнт-серверна взаємодія, яка
реалізується в таких технологіях, як MPI [5], Windows Communication Foundation (WCF),
Web Services, Win Services. Основою реалізації даного шаблону є механізм сокетів. Цей
вид взаємодії інтегрований в деякі мови програмування (наприклад, F# (MailboxProcessor)
[6], Scala (Actors), ErLang). Реалізація Message Passing шаблону (рис. 2) фактично є реалі-
зацією скінченного автомата.
6. Реалізація послідовної версії алгоритму
На рис. 3 наведено схему обрахунку вагової матриці на k -ому кроці реалізації послідовної
версії алгоритму. Така схема передбачає економію ресурсів оперативної пам’яті, оскільки
кожен крок алгоритму не вимагає додаткових витрат (нове значення k
ijd зберігається в то-
24 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Міжпотокова взаємодія
Локальний індекс i
k
ikd ijd
Дані першого потоку
Дані другого потоку
Виконання другого потоку
Виконання першого потоку
Локальний індекс i
kjd
ijd
ikd
Рис. 4. Розбиття даних на множини, що паралельно обробляються
му місці, де зберігалось 1−k
ijd ). Проте, якщо граф матиме від’ємні ребра при умові відсутно-
сті циклів від'ємної ваги, такий метод роботи із пам’яттю може призвести до невірних ре-
зультатів. Так, якщо на k -ому кроці вага k
ijd – від'ємна, алгоритм модифікує її, що призве-
де до невірних обрахунків інших значень ваги на цій ітерації. Для коректної роботи алго-
ритму в цьому випадку слід використовувати додаткові ресурси пам'яті.
Результати були отримані для графів з кількістю вузлів від 200 до 5000. Графік
(рис. 3) демонструє поліноміальну залежність часу виконання від кількості вузлів
(поліноміальну складність алгоритму).
7. Концепція розпаралелювання алгоритму Флойда-Уоршала
На кожному кроці k алгоритм повністю обраховує нову матрицю kD . При переході від
послідовної версії
алгоритму (1 по-
тік) до паралель-
ної ( n потоків)
слід зауважити,
що кількість да-
них, яку повинен
обробити один
потік з групи, стає
суттєво меншим.
Таким чином, як-
що потоки вико-
нуються парале-
льно, то час вико-
нання паралельної
версії має бути
приблизно в n
разів меншим.
Проте слід зазначити, що оскільки потоки мають на k -му кроці використовувати рядок і
Рис. 3. Час роботи реалізації послідовної версії
алгоритму в залежності від кількості вузлів графа
Рис. 2. Обрахунок матриці D
на k -тій ітерації
D
i
j k
k
ijdikd
kjd
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 25
Рис. 5. Залежність часу роботи алгоритму від
щільності графа. Приведені результати для гра-
фів з кількістю вузлів, рівною 1000, 2000, 3000
стовпчик з номером k , то ця область пам’яті виявляється спільною для кількох потоків.
Якщо потоки виконуються в різних процесах, то існуватимуть затрати часу на обмін цими
даними між ними, оскільки в цьому випадку матриця kD розподілена по системі. Окрім
того, на кожному кроці потоки слід синхронізувати за допомогою бар’єра, бо в іншому ви-
падку існуватиме не нульова імовірність того, що з'явиться потік, який потрапить на на-
ступну ітерацію раніше за інших і буде використовувати некоректні дані.
При створенні багатопотокової реалізації алгоритму вагова матриця kD знаходить-
ся у віртуальному адресному просторі одного процесу, кожен потік якого має безпосеред-
ній доступ до її комірок. Проте багатопроцесна реалізація для систем зі спільною пам’яттю
вимагає створення спільної матриці kD між усіма процесами. Зазначений механізм спіль-
ного сектора даних був використаний в реалізації для створення спільного вектора синх-
ронізації. Для того, щоб зробити спільною для всіх процесів велику ділянку пам'яті, було
використано механізм shared memory. В реалізації алгоритму для систем із розподіленою
пам’яттю було використано технологію MPI (Microsoft реалізація, що входить до складу
HPC Pack SDK). У цьому випадку матриця kD була розподілена між вузлами мережі, і на
кожному кроці певний вузол (що визначався динамічно під час виконання алгоритму) від-
силав рядок з номером k іншим вузлам.
8. Інші особливості експериментальної реалізації
Програмні реалізації виконані за САА-схемами, наведеними в [6]. Основа алгоритму побу-
дована за схемою 3, можливість використання якої зумовлена тим, що програмна реаліза-
ція моделює відсутність зв’язку у графі за допомогою деякої критичної величини ваги реб-
ра (ця величина задається як вхідний параметр). Переваги подібного підходу такі:
• введення критичного значення ваги дає можливість оперувати з порожніми
зв’язками графа так само, як із зв’язками, що мають скінченну вагу;
• зменшення кількості альфа-диз’юнкцій у вкладених альфа-ітераціях (зменшення
числа перевірок на кожному кроці алгоритму).
Проте недоліком у цьому випадку є створене обмеження на максимально можливу
вагу ребра вхідного графа.
Наступні експериментальні резуль-
тати були отримані для графів із фіксова-
ною щільністю (відношенням кількості
зв’язків з критичною вагою до загальної їх
кількості), що дорівнює 0,5. Причиною
цього є наслідки проведених попередніх
досліджень залежності часу виконання ал-
горитму від щільності. Рис. 5 демонструє
цю залежність для послідовної реалізації
алгоритму для графів з кількістю вузлів,
рівною 1000, 2000 та 3000. Аналогічні ре-
зультати були отримані і для багатопото-
кової та багатопроцесної реалізацій, а отже
можна зробити висновок про слабку зале-
жність часу виконання алгоритму від
щільності графів.
Як вже зазначалось, в утворених застосуваннях не було використано прив’язку по-
токів до ядер. З одного боку, це привело до суттєвого поліпшення часових характеристик
реалізацій з використанням розглянутої синхронізації. Проте, з іншого боку, оскільки кон-
текст потоку переміщується з одного ядра на інше неконтрольовано, розкид результатів,
26 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Рис. 6. Залежність часу виконання алгоритму від кількості паралельних потоків
та кількості вузлів графа
що отримувались для одного графа при певній кількості потоків, збільшився. На зображе-
них рисунках наводяться усереднені значення отриманих результатів. Велика відносна по-
хибка спостерігалась при малих кількостях вузлів графа, що пояснюється малим часом ви-
конання алгоритму і недостатньою точністю використаного таймера (було використано
функцію GetSystemTime).
Запуск таймера для створених версій алгоритму відбувався безпосередньо перед
циклом алгоритму, і тому отримані часові характеристики не включають час ініціалізації
вагової матриці та матриці передування. Для багатопотокової та багатопроцесної реалізації
врахований час створення паралельних потоків (процесів), проте для багатопроцесної реа-
лізації не враховано час створення ділянки спільної пам'яті. Якщо ж враховувати повний
час виконання реалізацій, то слід зазначити, що у випадку паралельних програм доцільні-
ше було б організувати паралельне асинхронне зчитування потоками вхідного файла з ва-
говими коефіцієнтами.
Коректність отриманих застосувань було перевірено на заздалегідь обрахованих
графах малої розмірності. Було встановлено відповідність між отримуваними результатами
від різних реалізацій алгоритму.
9. Дослідження швидкодії реалізації алгоритму для систем зі спільною пам’яттю
Дослідження проводилися на графах з кількістю вузлів у діапазоні від 200 до 5000 (з кро-
ком 100 для діапазону 200–2000 та 250 для діапазону 2000–5000) і кількістю потоків (про-
цесів) від 2 до 20 (з кроком 2). Використана апаратна архітектура Intel Core Quad – 2,4
GHz – 64-розрядний, 4 ядра. Програмні реалізації створені мовою С з використанням Win-
32 API (Win-64 API).
На рис. 6 наведено залежності часу виконання алгоритму від кількості вузлів графа
та кількості паралельних потоків (процесів). Час виконання потокової реалізації виявля-
ється меншим за час виконання реалізації, що використовує паралельні процеси, оскільки
додатковий час витрачається на обмін даними між процесами при використанні IPC.
Іншою особливістю результатів є характерні коливання залежності часу від кількос-
ті потоків (процесів). Локальні мінімуми цих коливань мають місце для кількості потоків,
що кратна чотирьом. Це явище пояснюється тим, що дослідження проводилися на системі
з чотирма ядрами. Тому при кількості потоків, що кратна 4, контекст кожного з них збері-
гається в L1 кеш-пам’яті певного ядра, а відповідний час на його завантаження не витрача-
ється. Отже, в цьому випадку протягом виконання застосування кожне з ядер працює із
своєю підмножиною потоків.
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 27
Рис. 7. Залежності відношення часів виконання багатопотокової реалізації з одним потоком
(лівий рисунок) та послідовної реалізації (правий рисунок) до часу виконання багатопотокової
реалізації для 2 та 4 потоків
На рис. 7 подано залежності відношення часу паралельної однопотокової та послі-
довної версій алгоритму до часу багатопотокової (2 та 4 потоки). З цих залежностей можна
зробити такі висновки:
1. Відношення часу виконання послідовної версії алгоритму до паралельної з кіль-
кістю потоків, що рівна двом (чотирьом), більше за два (чотири відповідно) в певному діа-
пазоні вузлів графа. Причиною, найбільш імовірно, є додаткова оптимізація паралельного
коду компілятором (тобто, факт, що набір інструкцій, який виконує один потік у багатопо-
токовій реалізації над своїми даними, відрізняється від потоку інструкцій послідовної вер-
сії алгоритму). Тому більш коректно порівнювати часи виконання одного потоку парале-
льної реалізації з часами цієї ж реалізації, що використовує багато потоків. У цьому випад-
ку максимальне отримане прискорення для двох потоків рівне приблизно 1,8, а для чоти-
рьох – 3,6.
2. На отриманих рисунках чітко виділяються область піку прискорення алгоритму
та область насичення. Причиною такої поведінки залежності прискорення від кількості ву-
злів графа може бути обмеженість ресурсу кеш-пам’яті L2 системи. При певній кількості
вузлів графа починають активно виникати кеш-промахи, що призводить до латентної опе-
рації звертання до оперативної пам’яті. Проте канал взаємодії ядер з оперативною
пам’яттю є спільним, і тому при обробці значного масиву даних паралельна обробка буде
чергуватися із послідовним звертанням до оперативної пам’яті, що на залежності відпові-
дає спаду до насичення. Оскільки кожне ядро процесора, на якому проводились дослі-
дження, володіє власною кеш-пам’яттю, що менша за загальну кеш-пам'ять процесора, то
використання групи паралельних потоків, які виконують алгоритм на графах з невеликою
кількістю вершин (такою кількістю, що достатня для появи кеш-промахів), призведе до
очікування частиною потоків даних з оперативної пам’яті. Отже, оскільки кількість даних,
що обробляє кожен потік з набору, менша за кількість даних, що обробляється потоком в
однопоточній версії, то границя, при якій активно проявляються кеш-промахи, зсувається
в бік графів з великою кількістю вузлів. Це пояснює пік на отриманих характеристиках
прискорення.
3. Отримані залежності для багатопроцесної реалізації (рис. 8) алгоритму подібні до
багатопотокової реалізації, проте максимуми прискорення в даному випадку виявляються
меншими. Це пояснюється тим, що операція створення паралельного потоку потребує ме-
нше ресурсів за операцію створення паралельного процесу.
28 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
Рис. 9. Прискорення відносно послідовної
версії алгоритму паралельної реалізації (1
вузол мережі, 1-4 використаних ядра) для
систем із розподіленою пам’яттю
Слід зазначити, що було проведено додаткові дослідження для підтвердження гіпо-
тези про кеш-пам'ять. При цьому використано звичайний ітераційний алгоритм збільшення
кожної комірки нульової матриці на одиницю паралельно та без використання синхроніза-
ції. Були отримані подібні характеристики. Також, при початкових дослідженнях неопти-
мізованої версії застосування отримані цікаві результати при заміні типів даних вхідних
матриць з double та int на float та short. Для нових типів пік прискорення зміщувався в бік
більшої кількості вузлів приблизно в 1,6 разів у порівнянні з початковою точкою макси-
муму. Якщо ж узяти до уваги обмеженість кеш-памяті, то теоретичне зміщення мало б бу-
ти рівним
41,12
int ≈=
(short)at)+sizeofsizeof(flo
)f(ble)+sizeosizeof(dou .
10. Дослідження швидкодії реалізації алго-
ритму для систем із розподіленою пам’яттю
При створенні застосування було використано
технологію MPI, що надає можливість запуска-
ти паралельні процеси на різних вузлах мережі.
Перші дослідження були спрямовані на
перевірку отриманих результатів попередніх
етапів (паралельних реалізацій для систем зі
спільною пам’яттю). Тому спочатку було вико-
ристано один вузол мережі. Отримані залежно-
сті відношення часу послідовної версії алгори-
тму до часу побудованої паралельної реалізації
для розподілених систем продемонстровані на
рис. 9. Тут використано саме час послідовної
версії для порівняння продуктивності парале-
льних реалізацій. Отже, ці залежності за пове-
дінкою відповідають отриманим раніше залеж-
ностям прискорення. Це свідчить про те, що обраний спосіб синхронізації чи обміну дани-
ми між потоками слабко впливає на поведінку прискорення.
Рис. 8. Залежності відношення часів виконання багатопроцесної реалізації з одним процесом
(лівий рисунок) та послідовної реалізації (правий рисунок) до часу виконання багатопроцесної
реалізації для 2 та 4 процесів
ISSN 1028-9763. Математичні машини і системи, 2011, № 4 29
Рис. 10. Час виконання та прискорення відносно послідовної версії алгоритму паралельної реалі-
зації (2 вузли мережі, 1-4 використаних ядра) для систем із розподіленою пам’яттю
Рис. 11. Час виконання та прискорення відносно послідовної версії алгоритму паралельної
реалізації (3 вузла мережі, 1-2 використаних ядра) для систем із розподіленою пам’яттю
Рис. 10 зображує характеристики застосування при використанні на двох
комп’ютерах, з’єднаних між собою мережею. Отримані графіки прискорення мають ряд
особливостей, що дозволяють зробити такі висновки.
1. На відміну від систем зі спільною пам’яттю, прискорення більше одиниці отри-
мується для графів з великою кількістю вузлів. Порівняння прискорення алгоритму, що
виконується на двох ядрах однієї машини, та алгоритму, що використовує одне ядро кож-
ної з двох машин, приводить до висновку, що за певної критичної кількості вузлів графа
друге застосування переважатиме за швидкодією перше. Це є перевагою систем із розподі-
леною пам’яттю. Проте для відносно малих кількостей вузлів графа продуктивність друго-
го застосування гірша за продуктивність послідовної реалізації алгоритму.
2. При малій кількості вузлів графа алгоритм втрачає більше часу на обмін даними
по мережі, ніж на корисну роботу. При великих кількостях даних – навпаки.
3. Викиди в залежності прискорення від кількості вузлів можна пояснити конкурен-
цією ядер за спільний канал обміну даними (це потребує додаткового дослідження).
Рис. 11 зображує отримані результати для трьох вузлів мережі. Відсутність
поліноміальної залежності між часом виконання і кількістю вузлів графа пов'язана з мож-
30 ISSN 1028-9763. Математичні машини і системи, 2011, № 4
ливими затримками передачі даних по мережі або з самою топологією мережі. Отже, мож-
на зробити висновок, що додавання нового вузла обчислень не дає суттєвої переваги у
швидкодії, проте додавання нового ядра на кожному вузлі значно підвищує
продуктивність застосування.
11. Висновки
Дослідження роботи паралельних реалізацій алгоритму Флойда-Уоршала для систем зі
спільною та розподіленою пам’яттю виявило ряд особливостей:
1. Прискорення низки потоків алгоритму (для SMP- та MPP-архітектур) доцільно
рахувати по відношенню до часу виконання одного потоку на відповідній архітектурі.
2. Для систем SMP-архітектури (рис. 7, 8) передуючий викид і подальший спад при-
скорення паралельної реалізації пояснюються обмеженістю об’єму кеш-пам’яті системи.
3. Збільшення кількості вузлів понад два для систем MPP-архітектури (рис. 10, 11)
не дає суттєвої переваги в часі виконання паралельної версії алгоритму.
4. Системи зі спільною пам’яттю доцільно використовувати для графів із кількістю
вузлів, меншою певної величини (для даної серії експериментів приблизно 2500). При пе-
ревищенні цієї межі реалізація для систем із розподіленою пам’яттю буде давати кращі ре-
зультати.
СПИСОК ЛІТЕРАТУРИ
1. Кормен Т. Алгоритмы, построение и анализ / Кормен Т., Лейзерсон Ч., Ривест Р.; пер. з англ.
И.В. Красикова, Н.А. Ореховой, В.Н. Романова; под ред. И.В. Красикова. – М.: Издательский дом
«Вильямс», 2005. – С. 719 – 725.
2. Таненбаум Э. Архитектура комп’ютера / Таненбаум Э. – [5-е изд.]. – СПб.: Питер, 2007. – C. 634
– 667.
3. Джеффри Р. Windows via C/C++. Программирование на языке Visual C++ / Рихтер Джеффри, На-
зар Кристоф; пер. с англ. – М.: Издательство “Русская Редакция”; СПб.: Питер, 2008. – 896 с.
4. Харт М.Дж. Системное программирование в среде Windows / Харт М. Дж.; пер. с англ. – [3-е
изд.]. – М.: Издательский дом «Вильямс», 2005. – C. 200 – 309.
5. Богачёв К.Ю. Основы параллельного программирования / Богачёв К.Ю. – М.: БИНОМ. Лабора-
тория знаний, 2003. – C. 232 – 292.
6. Syme D. Expert F# / Syme D., Granicz A., Cisternino A. – Berkeley: Apress, 2007. – 639 p.
7. Погорілий С.Д. Формування узагальнених паралельних схем алгоритму Флойда-Уоршала /
С.Д. Погорілий, В.А. Мар’яновський, Ю.В. Бойко [та ін.] // Системні дослідження та інформаційні
технології. – 2010. – № 1. – C. 52 – 69.
Стаття надійшла до редакції 22.04.2011
|
| id | nasplib_isofts_kiev_ua-123456789-83620 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:36:27Z |
| publishDate | 2011 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Погорілий, С.Д. Трибрат, М.І. Вітель, Б.Ю. 2015-06-21T09:57:58Z 2015-06-21T09:57:58Z 2011 Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур / С.Д. Погорілий, М.І. Трибрат, Б.Ю. Вітель // Мат. машини і системи. — 2011. — № 4. — С. 20-30. — Бібліогр.: 7 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83620 681.3 Створено паралельні версії алгоритму Флойда-Уоршала для SMP- і MPP-архітектур та досліджено і проаналізовано їх часові характеристики. Визначено доцільність застосування певної архітектури в залежності від розмірності задачі. Созданы параллельные версии алгоритма Флойда-Уоршала для SMP- и MPP-архитектур, исследованы и проанализированы их временные характеристики. Определена целесообразность применения определенной архитектуры в зависимости от размерности задачи. Parallel versions of the Floyd-Warshall algorithm for SMP-and MPP-architectures were created. Their temporal characteristics were investigated and analyzed. It was shown that the expediency of particular architecture usage depends on the dimension of the task. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур Исследование параллельных версий алгоритма Флойда-Уоршала для SMP- та MPP-архитектур Study of parallel algorithm versions of Floyd-Warshall for SMP- and MPP-architectures Article published earlier |
| spellingShingle | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур Погорілий, С.Д. Трибрат, М.І. Вітель, Б.Ю. Обчислювальні системи |
| title | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур |
| title_alt | Исследование параллельных версий алгоритма Флойда-Уоршала для SMP- та MPP-архитектур Study of parallel algorithm versions of Floyd-Warshall for SMP- and MPP-architectures |
| title_full | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур |
| title_fullStr | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур |
| title_full_unstemmed | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур |
| title_short | Дослідження паралельних версій алгоритму Флойда-Уоршала для SMP- та MPP-архітектур |
| title_sort | дослідження паралельних версій алгоритму флойда-уоршала для smp- та mpp-архітектур |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83620 |
| work_keys_str_mv | AT pogoríliisd doslídžennâparalelʹnihversíialgoritmufloidauoršaladlâsmptampparhítektur AT tribratmí doslídžennâparalelʹnihversíialgoritmufloidauoršaladlâsmptampparhítektur AT vítelʹbû doslídžennâparalelʹnihversíialgoritmufloidauoršaladlâsmptampparhítektur AT pogoríliisd issledovanieparallelʹnyhversiialgoritmafloidauoršaladlâsmptampparhitektur AT tribratmí issledovanieparallelʹnyhversiialgoritmafloidauoršaladlâsmptampparhitektur AT vítelʹbû issledovanieparallelʹnyhversiialgoritmafloidauoršaladlâsmptampparhitektur AT pogoríliisd studyofparallelalgorithmversionsoffloydwarshallforsmpandmpparchitectures AT tribratmí studyofparallelalgorithmversionsoffloydwarshallforsmpandmpparchitectures AT vítelʹbû studyofparallelalgorithmversionsoffloydwarshallforsmpandmpparchitectures |