Особливості компіляції схем паралельних алгоритмів
Проаналізовано сигнатуру алгоритмічних алгебр Глушкова. З метою формалізованого запису паралельних алгоритмів сигнатуру
 доповнено операцією паралельної композиції операторів. Створено параметричний компілятор схем паралельних алгоритмів. В
 статті наведено приклад компіляції паралел...
Gespeichert in:
| Datum: | 2004 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2004
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/2299 |
| 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: | Особливості компіляції схем паралельних алгоритмів / О.І. Захаров, С.Д. Погорілий// Проблеми програмування. — 2004. — N 2,3. — С. 238-243. — Бібліогр.: 8 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860133476936712192 |
|---|---|
| author | Захаров, О.І. Погорілий, С.Д. |
| author_facet | Захаров, О.І. Погорілий, С.Д. |
| citation_txt | Особливості компіляції схем паралельних алгоритмів / О.І. Захаров, С.Д. Погорілий// Проблеми програмування. — 2004. — N 2,3. — С. 238-243. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| description | Проаналізовано сигнатуру алгоритмічних алгебр Глушкова. З метою формалізованого запису паралельних алгоритмів сигнатуру
доповнено операцією паралельної композиції операторів. Створено параметричний компілятор схем паралельних алгоритмів. В
статті наведено приклад компіляції паралельного алгоритму
The signature of Glushkov’s algorithmic algebras is analyzed. For formal notation of parallel algorithms the operation of parallel
composition is added to the signature. The parametric compiler of parallel algorithm schemes is developed. An example of parallel algorithm
compilation is adduced in the article.
|
| first_indexed | 2025-12-07T17:46:04Z |
| format | Article |
| fulltext |
УДК 681.3
ОСОБЛИВОСТІ КОМПІЛЯЦІЇ СХЕМ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ
О. І. Захаров, С. Д. Погорілий.
Київський національний університет імені Тараса Шевченка. 01033, Київ, вул. Володимирська 64.
e-mail: sdp@rpd.univ.kiev.ua, zakharov@mail.univ.kiev.ua
Проаналізовано сигнатуру алгоритмічних алгебр Глушкова. З метою формалізованого запису паралельних алгоритмів сигнатуру
доповнено операцією паралельної композиції операторів. Створено параметричний компілятор схем паралельних алгоритмів. В
статті наведено приклад компіляції паралельного алгоритму.
The signature of Glushkov’s algorithmic algebras is analyzed. For formal notation of parallel algorithms the operation of parallel
composition is added to the signature. The parametric compiler of parallel algorithm schemes is developed. An example of parallel algorithm
compilation is adduced in the article.
Однією з основних характеристик обчислювальної системи є такий показник, як продуктивність —
величина, що показує, яку кількість арифметичних операцій він може виконати за одну секунду. Принципово
важливими рішеннями в підвищенні продуктивності обчислювальних систем є:
• введення конвеєрної організації виконання процесорних команд;
• включення в систему команд векторних операцій, які дозволяють однією командою обробляти масиви
даних;
• розподілення обчислень на множину процесорів.
Перші два напрямки підвищення продуктивності є апаратними, тому основна увага в збільшенні
продуктивності програмними засобами приділяється методам паралельного обчислення для багатопроцесорних
систем.
З іншого боку не менш актуальним напрямком дослідження та оптимізації обчислювальних алгоритмів є
формалізований синтез програм, суть якого полягає у створенні схеми алгоритму та подальшої трансформації ії
у програму шляхом підстановки замість формальних специфікацій їх реалізацій певною мовою програмування.
В [1] розглянуто інструментальний комплекс автоматизованого синтезу програм у візуальних середовищах
програмування, в якому схеми алгоритмів представлені мовою САА/1, що базується на системі алгоритмічних
алгебр В. М. Глушкова (САА) [2, 3].
Наявність систем формалізованого синтезу програм [1, 4] та розвиток методів розподілення обчислень
між процесорами висуває дві задачі:
• доповнення САА операціями паралельного виконання операторів;
• створення компілятора схем паралельних алгоритмів.
Розширення сигнатури САА
Проаналізуємо існуючі операції САА SAAO% з точки зору паралельного виконання.
Булеві операції — кон’юнкція ( 1 2α α∧ ), диз’юнкція ( 1 2α α∨ ), заперечення (α )
Паралельне обчислення булевих функцій неефективне, тому що майже всі сучасні процесори виконують
їх за одну машинну команду, і навіть за один процесорний такт. Так як синхронізація процесів вимагає значної
кількості машинного коду, то час паралельного обчислення булевого виразу значно перевищує час виконання
на одному процесорі.
Композиція ( 1 2O O∗ )
Нехай 1 11 2 1 2
1 1 1 1 1 1 1 1( , ,..., , , ,..., )n kO O v v v u u u= , 2 21 2 1 2
2 2 2 2 2 2 2 2( , ,..., , , ,..., )n kO O v v v u u u= , де 1 2 1 2, , 1... , 1...i jv v i n j n= = —
змінні, значення яких використовується у відповідних операторах; 1 2 1 2, , 1... , 1...i ju u i k j k= = — змінні, значення
яких модифікується. Операцію композиції можна виконати паралельно лише за умови
{ } { }1 2 1 2, 1... , 1...i jv u i n j k= ∅ = =I та { } { }2 1 2 1, 1... , 1...i jv u i n j k= ∅ = =I , тобто тоді і тільки тоді, коли вона має
властивість комутативності 1 2 2 1O O O O∗ ≡ ∗ (будемо казати, що оператори 1O та 2O незалежні). Отже, введемо
операцію паралельного виконання операторів 1O та 2O : 1 2O O∗% . Зрозуміло, що наведена операція також має
властивість комутативності 1 2 2 1O O O O∗ ≡ ∗% % .
Альтернатива (α -диз’юнкція) [ ]( )1 2,O Oα
При виконанні операції паралельно можна обчислювати як умову α , так і оператори 1O та 2O . Слід
зауважити, що після визначення значення умови α необхідно виконати лише один оператор 1O (умова істинна)
чи 2O (умова хибна). Паралельне обчислення операторів 1O і 2O можливе лише за умови, коли α і 1O , α і 2O
є попарно незалежними, та є ефективним, якщо час обчислення α , 1O і 2O збігається за порядком. В цьому
випадку існує перетворення [ ]( ) [ ]( )1 2 1 2, ,O O O O Oαα α′ ′= ∗ таке, що час виконання умови α ′ буде набагато
меншим за α (α ′ зведеться до обчислення булевих функцій), а, отже, паралельне виконання альтернативи
зведеться до паралельної композиції [ ]( )1 2,O O Oα α′ ′∗% .
Цикл (α -ітерація) [ ]{ }Oα
В загальному випадку цикл неможливо виконувати паралельно, але якщо обчислення довільної ітерації
не залежить від попередніх, або може бути зведене певним перетворенням до незалежного, то цикл можна
розбити на декілька [ ]{ } [ ]{ } [ ]{ } [ ]{ }1 1 2 2 ... n nO O O Oα α α α= ∗ ∗ ∗ (кількість n дорівнює кількості процесів) так,
що кожний утворений цикл може виконуватись в окремому процесі. Прикладом може бути обчислення суми
ряду, кожний член якого не залежить від попередніх, наприклад
1
1n
i i=
∑ . Отже знову бачимо, що паралельне
обчислення циклу зводиться до паралельного виконання композицій [ ]{ } [ ]{ } [ ]{ } [ ]{ }1 1 2 2 ... n nO O O Oα α α α= ∗ ∗ ∗% % % .
З вищенаведеного видно, що для формального запису паралельного алгоритму в сигнатурі алгоритмічної
алгебри Глушкова достатньо ввести одну операцію паралельного виконання операторів 1 2O O∗% .
Введення узагальнених операторів синхронізації процесів
Очевидно, що кожний з процесів, які виконують паралельний алгоритм, виконує певний машинний код,
який може бути представлений деяким алгоритмом, записаним у сигнатурі САА. Тоді зрозуміло, що задача
компіляції паралельної схеми зводиться до її тотожного перетворення у кілька однопроцесорних формул,
кількість яких дорівнює кількості виконуючих процесів (цей параметр повинен бути заданий на етапі
компіляції). Отже, до операції паралельного виконання операторів 1 2O O∗% необхідно застосувати тотожне
перетворення, в результаті якого отримаємо дві формули: 1 1 1
b eO O O∗ ∗ та 2 2 2
b eO O O∗ ∗ , де 1
bO та 2
bO —
початкові, а 1
eO та 2
eO — кінцеві синхронізуючі оператори.
Конкретне представлення цих операторів залежить насамперед від:
• архітектури розподіленої системи,
• операційної системи,
• мови програмування.
Розглянемо види синхронізації процесів та визначимо загальне представлення синхронізуючих
операторів, конкретна реалізація яких буде залежати від факторів, наведених вище.
Синхронізація за часом виконання
Виникають ситуації, при яких деякий процес для продовження обчислень повинен чекати завершення
виконання певних операторів, які в даний момент часу обробляються іншими процесами. Відповідно процеси,
які закінчили обробляти деякий оператор, повинні про це повідомити. Тому доцільно ввести оператори
очікування та повідомлення, а також булеву функцію перевірки стану певного оператору:
Таблиця 1. Оператори синхронізації за часом виконання.
1 2( , ,..., )nWaitAny O O O
Блокуючий оператор (виконання завершиться тільки при виконання
певної умови) очікування завершення хоча б одного з операторів
1 2, ,..., nO O O
1 2( , ,..., )nWaitAll O O O
Блокуючий оператор очікування завершення всіх операторів
1 2, ,..., nO O O .
( )Test O Булева функція перевірки стану оператора O , яка буде істинною якщо
O виконаний, в протилежному випадку хибною
( )Signal O Сигнал про завершення процесом оператора O
Синхронізація даних
У випадку системи з загальною пам’яттю, в якій дані доступні одночасно всім процесам, не потрібно
виконувати синхронізацію змінних. В системах з розподіленою пам’яттю кожний процес використовує власну
область пам’яті, яка недоступна для інших процесів, то виникає необхідність у синхронізації даних, які
отримуються в результаті обчислень. В цьому випадку єдиним можливим механізмом взаємодії між процесами
є механізм передачі повідомлень. Звичайно, для досягнення максимальної продуктивності реалізація механізму
повідомлень повинна базуватися на властивостях архітектури багатопроцесорної системи. Але в більшості
випадків синхронізацію можна виконати найбільш загальними операторами обміну змінними між процесами.
Слід зауважити, що необхідно ввести як повідомлення між двома процесами, так і широкомовні повідомлення
(broadcast). Отже визначимо наступні оператори:
Таблиця 2. Оператори синхронізації за даними.
1 2( , , ,..., )nSend P v v v Передача процесу P значень змінних 1 2, ,..., nv v v .
1 2( , ,..., )nSendBroadcast v v v Широкомовне повідомлення з передачею значень змінних 1 2, ,..., nv v v
1 2( , , ,..., )nReceive P v v v Одержання з процесу P значень змінних 1 2, ,..., nv v v .
Необхідно також визначити оператори початкової ініціалізації та звільнення ресурсів:
Таблиця 3. Оператори початкової ініціалізації та звільнення ресурсів.
Initialize Оператор початкової ініціалізації. Повинен бути першим оператором
процесу
Finalize Оператор звільнення ресурсів, які використовувались для забезпечення
синхронізації та обміну повідомленнями між процесами. Повинен бути
останнім
Розглянемо приклад застосування вищенаведених операторів. Нехай маємо оператор
1 2 3( , ) ( , ) ( , )rw r r rw rw rwO O a b O b c O a c= ∗ ∗% % , який представлено композицією деяких простих операторів 1 2 3, ,O O O ,
та змінними , ,a b c (верхній індекс змінної r означає, що її значення використовується при виконанні даного
оператору, w — значення змінної модифікується). Для системи з двома процесорами 1P та 2P відповідно
отримаємо:
1 2 2 1 2 3: ( , , ) ( ) ( , )P Initialize Send P a b O WaitAny O Recieve P a O Finalize∗ ∗ ∗ ∗ ∗ ∗
2 1 1 1 1: ( , , ) ( ) ( , )P Initialize Receive P a b O Signal O Send P a Finalize∗ ∗ ∗ ∗ ∗
На наведених нижче рисунках зображено виконання оператору O у випадку однопроцесорної системи
(рис 1а) та двохпроцесорної системи (рис 1б).
2P 2O
1P 1O 3O
t
Очікування Синхронізація
Обчислення Передача повідомлення
1P 1O 3O
t
Обчислення
2O
Рис 1. Виконання оператору O : a) на однопроцесорній системі; б) на двохпроцесорній системі.
Компілятор схем паралельних алгоритмів
На рис. 2 наведено структурну схему компілятора
Лексичний
аналізатор
Синтакичний
аналізатор
Блок
оптимізації
Блок
синтезу
Блок роботи з таблицею
ідентифікаторів
Блок зберігання та
обробки формул
Блок перетворення
паралельних формул у
низку послідовних
Рис 2. Структурна схема компілятора
Блок лексичного аналізу виконано у вигляді скінченого детермінованого автомату. Так як в мові САА/1
тип лексеми однозначно визначається в тому місці тексту, де вона знаходиться, то застосовано прямий
лексичний аналізатор. Для запису паралельних алгоритмів мова САА/1 доповнена лексемою паралельного
виконання операторів “||”.
На вхід синтаксичного аналізатору подається потік лексем, який надходить з блоку лексичного аналізу.
Так як алгоритм можна представити у вигляді графу, то на виході синтаксичного аналізатору будується дерево,
що відповідає алгоритму вхідної програми. Якщо ідентифікатор головної формули описується окремою
формулою, то дерево, яке їй відповідає, підставляється замість цього ідентифікатора у головну формулу. Таким
чином, після завершення синтаксичного аналізу будується дерево, листками якого є елементарні
ідентифікатори, які не задаються формулами. Для таких ідентифікаторів необхідна наявність реалізації в базі
даних.
Блок зберігання та обробки формул необхідний для виконання основних операцій над деревами
формул, такі як вставка піддерева, обхід дерева, тощо.
Модуль роботи з таблицею ідентифікаторів – єдиний модуль компілятора, що безпосередньо працює з
базою даних. Після проведення синтаксичного аналізу та перетворень формули алгоритму блок вилучає з бази
даних необхідну інформацію (реалізації, опис змінних, тощо) для елементарних ідентифікаторів.
Блок перетворення паралельних формул у низку послідовних необхідний для компіляції паралельних
алгоритмів. Його робота полягає у пошуку в дереві алгоритму операцій паралельної композиції, та тотожному
перетворенні дерева у декілька, які представляють послідовні алгоритми з включенням необхідних операторів
синхронізації.
Важливим етапом роботи компілятора є тотожні перетворення формул з метою оптимізації алгоритму та
вихідної програми, які виконує блок оптимізації. Модуль виконує наступні типи оптимізації:
• за часом виконання алгоритму,
• за розміром коду вихідної програми,
• за розміром сегменту даних, тобто розміром глобальних змінних,
• за розміром стеку програми, тобто розміром локальних змінних процедур.
Останній блок компілятора – блок синтезу коду. Він служить для генерації тексту вихідної програми на
основі побудованих формул алгоритму. Система може настроюватись на різні вихідні мови програмування.
Таке настроювання здійснюється шляхом застосування технології підключення додаткових модулів (plug-ins).
Приклад
Розглянемо приклад паралельного обчислення на двохпроцесорній системі числа π за формулою
( )
2
1
1 1 1
1 1 1
1
4 2 1 4 3 4 1
n n n
i
i i ii i i
π +
= = =
= − = −
− − −∑ ∑ ∑
САА формула для цього прикладу має вигляд:
"Cycle1 initialization" "Index1 assign to 1" "Sum1 assign to 0"= ∗
"Cycle1 body" "Add to sum1 next member" "Increment index1"= ∗
[ ]{ }"Cycle1" "Cycle1 initialization" "Cycle1 condition" "Cycle1 body"= ∗
"Cycle2 initialization" "Index2 assign to 1" "Sum2 assign to 0"= ∗
"Cycle2 body" "Add to sum2 next member" "Increment index2"= ∗
[ ]{ }"Cycle2" "Cycle2 initialization" "Cycle2 condition" "Cycle2 body"= ∗
"Pi Calculation" "Cycle1" "Cycle2" "Calculate sum" "Show answer"= ∗ ∗ ∗%
Та ж схема, записана мовою САА/1 виглядає так:
scheme “Pi Calculation” = “CalcPi”;
“Pi Calculation” = “Cycle1” || “Cycle2” * “Calculate sum” * “Show answer”;
“Cycle1” = “Cycle1 initialization” * while ‘Cycle1 condition’ do (“Cycle1 body”);
“Cycle2” = “Cycle2 initialization” * while ‘Cycle2 condition’ do (“Cycle2 body”);
“Cycle1 initialization” = “Index1 assign to 1” * “Sum1 assign to 0”;
“Cycle1 body” = “Add to sum1 next member” * “Increment index1”;
“Cycle2 initialization” = “Index2 assign to 1” * “Sum2 assign to 0”;
“Cycle2 body” = “Add to sum2 next member” * “Add to sum2 next member”;
end.
Список понять алгоритму, їх реалізації та параметри
Таблиця 4. Поняття алгоритму, їх реалізації та параметри.
Змінні
Поняття Реалізація
О
п
ер
ат
ор
ч
и
ум
ов
а
Назва Тип
Область
видимості
Ч
и
та
н
н
я
За
п
и
с
Index1 assign to 1 I1:=1 O I1 Integer Параметр •
Sum1 assign to 0 S1:=0 O S1 Extended Глобальна •
S1 Extended Глобальна • •
Add to sum1 next member S1:=S1+1/(4*I1-3) O
I1 Integer Параметр •
Increment index1 Inc(I1) O I1 Integer Параметр • •
Cycle1 condition I1<=N У I1 Integer Параметр •
Index2 assign to 1 I2:=1 O I2 Integer Параметр •
Sum2 assign to 0 S2:=0 O S2 Extended Глобальна •
S2 Extended Глобальна • •
Add to sum2 next member S2:=S2+1/(4*I2-1) O
I2 Integer Параметр •
Increment index2 Inc(I2) O I2 Integer Параметр • •
Cycle2 condition I2<=N У I2 Integer Параметр •
S Extended Глобальна •
S1 Extended Глобальна • Calculate sum S=4*(S1-S2) O
S2 Extended Глобальна •
Show answer WriteLn(S) O S Extended Глобальна •
Синтезована програма
program CalcPi;
{$APPTYPE CONSOLE}
uses Windows;
const
N = 1000000;
var
S, S1, S2: Extended;
I1: Integer;
Process1Id: Longword;
Process1Handle: THandle;
Signal1Handle: THandle;
function Process1(lpParameter: Pointer): Longword; stdcall;
var
I2: Integer;
begin
S2 := 0;
I2 := 1;
while (I2 < N) do
begin
S2 := S2 + 1 / (4 * I2 - 1);
Inc(I2);
end;
SetEvent(Signal1Handle);
ExitThread(0);
Result := 0;
end;
begin
Signal1Handle := CreateEvent(nil, False, False, nil);
Process1Handle := CreateThread(nil, 0, @Process1, nil, 0, Process1Id);
S1 := 0;
I1 := 1;
while (I1 <= N) do
begin
S1 := S1 + 1 / (4 * I1 - 3);
Inc(I1);
end;
WaitForSingleObject(Signal1Handle, INFINITE);
s := 4 * (S1 - S2);
WriteLn(S);
WaitForSingleObject(Process1Handle, INFINITE);
CloseHandle(Process1Handle);
CloseHandle(Signal1Handle);
end.
Синтез виконаний для операційної системи Microsoft Windows NT та мови програмування Borland
Delphi.
Висновки
В результаті виконання роботи:
• Виконано аналіз сигнатури САА і запропоновано її доповнення операцією паралельного виконання
операторів та засобами синхронізації за часом виконання та за даними.
• Створено параметричний компілятор для трансформування схем паралельних алгоритмів у програми
для багатопроцесорних систем. Компілятор реалізовано у середовищі Borland Delphi 7.0. Перевагою
створеного компілятора є можливість параметричного настроювання на різні цільові мови
програмування.
Література
1. Погорілий С.Д., Захаров О.І. Створення інструментальних засобів синтезу програм у візуальних середовищах. // Проблемы
программирования // Специальный выпуск №1-2, 2002.
2. Погорілий С.Д. Автоматизація наукових досліджень. Основоположні теоретичні відомості. Програмне забезпечення. За редакцією
академіка АПН України Третяка О.В. — К: Видавничо-поліграфічний центр “Київський університет”, 2002. — 288 с.
3. Цейтлин Г.Е. Введение в алгоритмику. — Киев: Сфера, 1998. — 310 с.
4. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ: Теоретические основы,
инструментарий. — Москва: Финансы и статистика, 1989. — 208 с.
5. Математическая энциклопедия. — Москва: Советская энциклопедия, 1985.
6. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. — 600 с.
7. MPI: A Message-Passing Interface Standard. Message Passing Interface Forum. — Version 1.1. 1995. — http://www-unix.mcs.anl.gov/mpi
8. MPI: The Complete Reference. — http://rsusu1.rnd.runnet.ru/ncube/mpi/mpibook/mpi-book.html
|
| id | nasplib_isofts_kiev_ua-123456789-2299 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:46:04Z |
| publishDate | 2004 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Захаров, О.І. Погорілий, С.Д. 2008-09-17T12:31:41Z 2008-09-17T12:31:41Z 2004 Особливості компіляції схем паралельних алгоритмів / О.І. Захаров, С.Д. Погорілий// Проблеми програмування. — 2004. — N 2,3. — С. 238-243. — Бібліогр.: 8 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2299 681.3 Проаналізовано сигнатуру алгоритмічних алгебр Глушкова. З метою формалізованого запису паралельних алгоритмів сигнатуру
 доповнено операцією паралельної композиції операторів. Створено параметричний компілятор схем паралельних алгоритмів. В
 статті наведено приклад компіляції паралельного алгоритму The signature of Glushkov’s algorithmic algebras is analyzed. For formal notation of parallel algorithms the operation of parallel
 composition is added to the signature. The parametric compiler of parallel algorithm schemes is developed. An example of parallel algorithm
 compilation is adduced in the article. uk Інститут програмних систем НАН України Параллельное программирование Распределенные системы и сети Особливості компіляції схем паралельних алгоритмів Article published earlier |
| spellingShingle | Особливості компіляції схем паралельних алгоритмів Захаров, О.І. Погорілий, С.Д. Параллельное программирование Распределенные системы и сети |
| title | Особливості компіляції схем паралельних алгоритмів |
| title_full | Особливості компіляції схем паралельних алгоритмів |
| title_fullStr | Особливості компіляції схем паралельних алгоритмів |
| title_full_unstemmed | Особливості компіляції схем паралельних алгоритмів |
| title_short | Особливості компіляції схем паралельних алгоритмів |
| title_sort | особливості компіляції схем паралельних алгоритмів |
| topic | Параллельное программирование Распределенные системы и сети |
| topic_facet | Параллельное программирование Распределенные системы и сети |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/2299 |
| work_keys_str_mv | AT zaharovoí osoblivostíkompílâcííshemparalelʹnihalgoritmív AT pogoríliisd osoblivostíkompílâcííshemparalelʹnihalgoritmív |