Команда "крок" в паралельних відладчика
А.Я. Калинов, К.А. Карганов, К.В. Хоренко
Анотація.
В
статті розглядається нова схема команд переміщення в паралельних відладчика
на прикладі команди "крок". Основна відмінність запропонованої схеми від
існуючих полягає в тому, що відладчик на основі моделі паралельної
програми аналізує момент завершення "кроку" програми, чим
наближає налагодження паралельної програми до налагодження послідовної програми.
Розглянуто проблеми, що виникають при реалізації даної схеми для усунення несправностей
MPI-програм, і описана її реалізація в відладчик mpC-програм.
1. Введення
Однією
з найважливіших можливостей, які надає відладчиком, є можливість
управління виконанням програми. Семантика команд управ-ління виконанням у
послідовних відладчика (коли регламентуватиме один процес з одним потоком
управління) досить ясна. Наприклад, семантика команди покрокового виконання
послідовної програми полягає в наступному - виконати оператори
поточного рядка і перервати виконання налагоджують програму. Якщо оператори
поточного рядка не виконані, то користувач аналізує причину (наприклад,
очікування взаємодії із зовнішнім світом, довгий рахунок і т.д.) і робить
або не робить будь-які дії. Причини невиконання кроку
послідовної програми назвемо "послідовними". Природний
розширення цієї семантики на випадок паралельного відладчика (коли регламентуватиме
декілька потоків управління, можливо, в декількох процесах) - виконати
оператори поточних рядків для виділених потоків управління і перервати їх
виконання. Однак, у випадку паралельного відладчика, деякі потоки можуть не
виконати крок не тільки за "послідовною", але й по
"паралельним" причин, пов'язаних із взаємодією між
потоками/процесами паралельної програми.
Більшість
існуючих паралельних відладчиком є багато-цільовими, не
орієнтованими на підтримку якого-небудь конкретного паралельного мови
програмування або комунікаційного пакету. У них застосовується комбінація
двох основних схем реалізації команди "крок":
синхронна
- Команда видається для всіх процесів групи, очікується завершення кроки для
всіх процесів групи, є можливість примусового переривання --
основна схема в Mantis [1,2];
асинхронна
- Команда видається для всіх процесів групи завершили попередній крок на
даний момент, управління в відладчик передається користувачеві без очікування
закінчення виконання команди - основна схема в TotalView [3].
При
цьому відповідальність за аналіз та обробку всіх "паралельних" причин
незавершення кроку покладається на користувача.
В
Водночас, якщо розглядати не паралельну програму взагалі, а
MPI-програми або програми на паралельному мовою високого рівня, то серед
"паралельних" причин незавершення кроку більшість є
"тривіальними", обробку яких може виробляти відладчик,
наближаючи тим самим, наскільки це можливо, налагодження паралельної програми до
налагодження послідовної програми. Звичайно, це можливо тільки в тому випадку,
якщо відладчик розуміє семантику паралельної програми і має відповідну
підтримку з боку реалізації бібліотеки або мови.
В
даній статті обговорюється можливість реалізації синхронної моделі виконання
команди "крок", яка відрізняється від традиційної тим, що:
послідовна
команда "крок" виконується тільки тими процесами, які завершили
виконання попередньої команди переміщення;
"тривіальні
паралельні "причини незавершення кроку обробляються відладчиком.
Розглядаються
проблеми, що виникають при реалізації такої моделі для відладчика MPI-програм, і
описується її реалізація для паралельного відладчика для мови mpC [4,5],
який є складовою частиною інтегро-рова системи розробки та
виконання mpC програм mpC Workshop. Стаття організована таким чином: в
першому параграфі дається визначення паралельної команди "крок",
що демонструється на прикладі простої MPI-програми. У другому параграфі
аналізується можливість обліку "тривіальних причин" незавершення
кроку для MPI-програм. Третій параграф дає введення в мову паралельного
програм-мування mpC. У четвертому пункті описується mpC-відладчик.
2. Синхронна модель команди "крок" з
обробкою "тривіальних причин" незавершення кроку на прикладі
MPI-програм
Введемо
визначення команди синхронної команди "паралельного кроку". Приймемо,
що для виконання команди "крок паралельної програми" групою
процесів кожному процесу з групи, що завершився попередні команди
переміщення, необхідно виконати дії, які визначаються командою
"крок" послідовного відладчика ( "послідовною"
команди "крок"). Крок паралельної програми будемо вважати завершеним,
якщо кожен процес налагоджують програму:
а)
виконав дії, покладені на останній даною йому
"послідовно-вательной" командою переміщення (можливо, не командою
"крок") або б) зупинився і не може продовжити виконання без
додаткових дій з боку користувача по відношенню до інших процесів
налагоджений-ваемой програми.
Назвемо
"тривіальної паралельної" причиною незавершення паралельної команди
крок процесом очікування синхронізації з іншими процесами, про яку
відомо, що вона не відбудеться на цьому кроці паралельної програми.
Приклад
1. Розглянемо послідовне виконання наступної MPI-програми:
/* 0 */# include "mpi.h"
/* 1 */int main (int argc, char
** argv) (
/* 2 */int rank, i;
/* 3 */MPI_Init (& argc,
& argv);
/* 4 */MPI_Comm_rank (MPI_COMM_WORLD,
& rank);
/* 5 */if (rank == 1) (
/* 6 */MPI_Status stat;
/* 7 * /
MPI_Recv (& i, 1, MPI_INT, 0,0, MPI_COMM_WORLD, & stat);
/* 8 * /)
/* 9 */if (rank == 0) (
/* 10 */i = 0;
/* 11 * /
MPI_Send (& i, 1, MPI_INT, 1,0, MPI_COMM_WORLD);
/* 12 * /
)
/* 13 * /
MPI_Finalize ();
/* 14 * /
return 0;
/* 15 * /
)
Нехай
відладчик є "розумним", тобто обробляють "тривіальні
паралельні "причини незавершення кроку та інтерпретує обчислення
керуючого вираження умовного оператора як самостійний крок. Нехай,
крім того, команди видаються для всіх процесорів налагоджують програму, і
поточної рядком для всіх процесів є рядок 3. Тоді для
послідовності кроків паралельної програми для різних процесів
поточними будуть наступні рядки:
Крок
Поточні позиції для процесів з rank
Примітка
0
1
інші
1
3
3
3
.
2
4
4
4
.
3
5
5
5
.
4
9
7
9
Процес з rank рівним 1 не може закінчити свій крок по
"тривіальної паралельної" причини - управління не може повернутися
з функції MPI_Recv так як процес з rank рівним 0 ще не викликав функцію
MPI_Send у рядку 11 і не викличе її на цьому кроці.
5
10
7
13
Решта процеси не можуть завершити крок по
"тривіальної паралельної" причини - для завершення роботи
MPI_Finalize її повинні викликати всі процеси.
6
11
7
13
Процес з rank рівним 1 процес повинен закінчити
виконання MPI_Recv.
7
13
9
13
.
8
13
13
13
.
Таблиця
1. Поточні позиції для різних процесів при покроковому виконання MPI
програми.
В
даному прикладі за вісім кроків паралельної програми процес з rank рівним 0
зробив 7 послідовних кроків, процес з rank рівним 1 зробив 6
послідовних кроків, інші процеси зробили 5 послідовних кроків, і
користувачеві не потрібно ніяких додаткових дій для цього.
Основні
відмінності запропонованої схеми виконання команди "крок" від існуючих
схем:
Перші
три кроки в паралельному відладчик з синхронної схемою команди "крок"
будуть ідентичні наведеним вище. Однак користувач не дочекається завершення
кроку 4 в такому відладчиком, оскільки процес з rank рівним 1 не зможе завершити
свою частину команди. Користувачеві доведеться перервати виконання команди. У
результаті він отримає набір процесів, зупинених в різних точках програми.
Він не буде знати, який з процесів зупинився самостійно, виконавши свій
елементарний крок, а який був перерваний користувачем.
Якщо
в відладчик реалізована асинхронна модель паралельної команди
"крок", то користувач, після того, як видав команду і отримав
управління в відладчик (відразу ж після видачі команди), не може бути впевнений,
що всі процеси завершили виконання своїх частин загальної паралельної команди
"крок". Користувач може переконатися-диться в повному завершенні (або
незавершених) загальною команди лише дослідивши статус кожного процесу вручну і
проаналізувавши їх.
Важливо
відзначити, що в обох розглянутих випадках після четвертого кроку процес з
rank 1 буде знаходитися десь усередині функції MPI_Recv. У той же час відладчик
рівня вихідного тексту мови паралельного програм-мування повинен
забезпечувати налагодження в термінах самої мови. Усунення несправностей MPI-програм також
повинен підтримувати налагодження в термінах MPI та мови послідовного
програмування, з якого викликаються функції MPI. Відповідно, для нього
функції MPI повинні бути неподільними примітивами. Для користувача,
налагоджують MPI-програму, отримати інформацію про те, що один з процесів
його програми знаходиться в якій-то внутрішньої функції, викликаної, наприклад,
усередині MPI_Recv також неестес-Твен, як для користувача, налагоджують
послідовну програму на мові високого рівня, отримати інформацію, що
програма виконує якусь із асемблерних операцій. Ми вважаємо це
істотним недоліком існуючих схем паралельних команд переміщення,
який усувається в пропонованому підході.
3. Підхід до обліку "тривіальних причин"
незавершення кроку для MPI-програм
Пропонована
реалізація кроку паралельної програми можлива тільки в тому випадку, якщо
відладчик розуміє семантику функцій MPI і має модель виконання
MPI-програми. Це неможливо без підтримки відладчиком з боку MPI, так само
як налагодження програм на мові високого рівня неможлива без підтримки з
боку компілятора. В даний час підтримка паралельних відладчиком
реалізаціями MPI обмежується інтерфейсом, розробленим для TotalView [7],
який орієнтований тільки на перегляд черг повідомлень і не дозволяє
обробляти "тривіальні паралельні" причини незавершення кроку в
MPI-програмі.
Сучасні
паралельні відладчик (наприклад, p2d2 [6]) мають наступну клієнт-серверну
архітектуру:
Рис.
1
В
ній сервер складається з двох частин: нерозподіленого, яка відповідає за
управління паралельної програми як цілим, і розподіленою, яка відповідає
за безпосереднє управління виконанням кожного з процесів паралельної
програми. Відповідно, нерозподілений частина повинна підтримувати модель
поточного стану паралельної програми і, на підставі інформації,
одержуваної від розподілених частин обробляти "тривіальні
паралельні "причини незавершення кроку.
Розглянемо,
якої інформації не вистачає в поточному інтерфейсі "MPI - відладчик" [7]
на прикладі функції MPI_Send. За допомогою цього інтерфейсу доступна чергу
незакінчених посилок для кожного комунікатора. Елемент цієї черги має тип
структури mqs_pending_operation [8] і містить велику кількість інформації про
посилці. Відомо, що реалізація MPI самостійно приймає рішення про те
буферізіровать, чи ні пересилається. У разі буферизації повідомлення
операція пересилання є локальною і закінчується незалежно від
уівідповідності-твующего запиту на прийом. В іншому випадку вона не є
локальної і не може закінчитися, якщо не був виданий відповідний запит на
прийом. Для того, щоб передати цю інформацію компоненті відладчика, пов'язаної
з конкретним процесом, досить просто додати в структуру
mqs_pending_operation ще одне поле, яке говорило б про те чи було
повідомлення буферізіровано чи ні. Побудова повного інтерфейсу "MPI --
відладчик ", що задовольняє вимогам запропонованого підходу, не є
метою даної роботи. Ми просто хочемо звернути увагу на те, що він може бути
отриманий шляхом незначної доробки вже наявного інтерфейсу.
Ми
реалізували запропонований підхід в відладчик для мови паралельного
програмування mpC, що описаний нижче.
4. Мова паралельного програмування mpC
Мова
паралельного програмування mpC був розроблений в кінці 90х в Інституті
системного програмування РАН. У мові mpC, який є розширенням
мови З, вводиться поняття обчислювального простору, що визначається
як деякий доступне для управління безліч віртуальних процесорів.
Основним поняттям mpC є поняття мережного об'єкта або просто мережі. Мережа
є областю обчислювального простору, яка може бути використана
для обчислення виразів і виконання операторів.
Розміщення
і звільнення мережевих об'єктів в обчислювальному просторі виконується
аналогічно розміщення та звільнення об'єктів даних в пам'яті. Концептуально,
створення нової мережі ініціюється процесором вже існуючої мережі. Цей
процесор називається батьком створюваної мережі. Батько завжди належить
створюваної мережі. Єдиним віртуальним процесором, визначеним від початку і
до кінця виконання програми, є визначений віртуальний
хост-процесор.
Будь-який
мережний об'єкт, оголошений у програмі, має тип. Тип специфікує число і
продуктивності процесорів. Наприклад, оголошення
nettype
SimpleNet (n) (
coord
I = n;
);
вводить
параметризрвані мережний тип з ім'ям SimpleNet, відповідний мереж,
що складається з n віртуальних процесорів. Віртуальні процесори мережі пов'язані з
координатної змінної I, значення якої змінюється від 0 до n-1. Батько
мережі має за замовчуванням координату що дорівнює 0. Це найпростіша мережу, визначення
якої міститься в стандартному файлі mpc.h.
Приклад
2. Розглянемо mpC-програму еквівалентну MPI-програмі, наведеної в прикладі
1.
/* 0 */# include "mpc.h"
/* 1 */int [*] main (int argc, char ** argv)
(
/* 2 */net SimpleNet (2) w;
/* 3 */int [w] i;
/* 4 */[host] i = 0;
/* 5 */[w: I == 1] i = [host] i;
/*
6 */return 0;
/*
7 * /)
Маючи
оголошення мережевого типу, можна оголосити ідентифікатор мережного об'єкта цього
типу. Наприклад, оголошення в рядку 2 вводить ідентифікатор w мережного об'єкта
що складається з 2 віртуальних процесорів.
Об'єкт
даних, розподілений за деякою області обчислювального простору,
складається зі звичайних (нерозподілених) об'єктів одного типу, які розміщені в
процесорних вузлах цієї області таким чином, що кожен процесорний вузол
містить одну і тільки одну компоненту розподіленого об'єкта. Наприклад,
оголошення в рядку 3 вводить цілу змінну i, розподілену по мережі w.
Конструкція [w] є специфікатор розподілу змінної. У
даній програмі використовуються специфікатор розподілу [*] і [host],
відповідні всьому обчислювальному простору і хост-процесору
відповідно, а також [w: I == 1], що виділяє вузол мережі w з координатою I,
рівний 1. Відзначимо, що хост-процесор має у цій мережі координату 0.
Оператор
у рядку 4 присвоює компоненті змінної i, розташованої на
хост-процесорі, значення 0. Це локальне присвоювання.
Присвоєння
у рядку 5 є розширенням привласнення мови С. Воно присвоює
компоненті змінної i, розташованої на вузлі мережі w з координатою I, рівної
1, значення компоненти змінної i, розташованої на хост-процесорі. Це
розподілене присвоювання.
Компілятор
транслює текст вихідної програми на mpC в ANSI C-програму із зверненнями до
функцій системи підтримки виконавчі. Використовується SPMD-модель
цільового коду, коли всі процеси, що складають паралельну програму,
виконують однаковий код.
Система
підтримки виконавчі управляє обчислювальним простором, який
відображається на деяку кількість процесів, що виконуються на цільової
обчислювальної машини з розподіленою пам'яттю (наприклад, на мережі ПК і робочих
станцій), а також забезпечує передачу повідомлень. Вона повністю інкапсулює
кон?? ної комунікаційний пакет (в даний час, підмножина MPI 1.1) і
забезпечує незалежність компілятора від конкретної цільової платформи.
5. Усунення несправностей mpC-програм
mpC
Workshop є інтегрованою середовищем розробки і виконання mpC програм
для Windows, розроблена в Інституті системного програмування РАН для
компанії ATS (www.atssoft.com). Він складається з набору інструментів,
підтримують всі стадії розробки та виконання mpC-програм, основним з
яких є відладчик mpC-програм.
З
кожним віртуальним процесором (процесом паралельної програми) відладчик
пов'язує курсор, який вказує на його поточну виконувану рядок. Курсор
має колір, який вказує на його статус. Кольори визначаються відповідно
зі стилем світлофора, тобто, зелені курсори можуть виконати команду
переміщення, жовті могли б виконати команду переміщення, але зупинені
користувачем і, нарешті, червоні курсори не можуть виконати команду
переміщення, так як вони не закінчили один з попередніх кроків і чекають
синхронізації з іншими віртуальними процесорами для його завершення. Курсори
одного кольору, що вказують на одну й ту ж строчку, об'єднуються в складовою
курсор.
Існує
можливість поміняти колір, як у всього складного курсору, так і у деяких
що входять до нього курсорів. Можна міняти колір курсора тільки з жовтого на зелений
і навпаки. Червоний колір курсора визначається відладчиком. Далі якщо це не
буде обумовлено окремо, ми не будемо робити різниці між простим і складеним
курсором, а також між курсором і віртуальним процесором.
В
відладчик mpC прийнята описана вище синхронна модель. Тобто, відладчик
очікує завершення кроку усіма зеленими курсором. Якщо відладчик знає, що
будь-якої курсор не може закінчити поточний крок по "тривіальної
паралельної "причини, він позначає цей курсор червоним кольором і не очікує
завершення ним послідовного кроку на цьому кроці паралельної програми.
Після того, як на якомусь кроці паралельної програми відбулася подія,
яке дозволяє червоному курсору закінчити незавершений послідовний
крок, відладчик починає чекати його завершення.
Розглянемо
послідовне виконання програми з прикладу 2. Нехай поточна віртуальна
паралельна машина складається з 2 віртуальних процесорів. На початку сесії налагодження
існує тільки один курсор зеленого кольору, що показує на 1-й рядок.
Після
першого кроку з'являється два курсора. Перший з номером 0 відповідає
хост-процесору, який повинен виконати оператор в рядку 4. Другий з номером
1, відповідає вузлу мережі w з координатою 1, який повинен виконати оператор
в рядку 5.
Після
другого кроку курсор з номером 1 залишається в тій же позиції, але змінює свій колір,
тому що він не може виконати оператор в рядку 5 до тих пір, поки його не
почне виконувати хост-процесор.
Після
виконання третього кроку хост-процесором, процес, якому відповідає
курсор з номером 1 також закінчує виконання оператора в рядку 5 і знову
виходить тільки один зелений курсор.
Усунення несправностей
mpC має традиційну модель "клієнт-сервер". Клієнт пов'язаний з
спеціальним процесом - менеджером налагодження, який отримує команди
користувача та управляє виконанням процесів паралельної програми. Коли,
при виконанні кроку, процес паралельної програми виконує дію,
що вимагає синхронізації з іншими процесами, інформація про це передається
менеджеру налагодження. Він розуміє семантику відповідних дій і
підтримує всередині себе модель стану паралельної mpC програми, яка
дозволяє йому визначати, які процеси завершать виконання кроку, а які ні.
Як
зазначалося вище, mpC-компілятор транслює mpC-програму в MPI-програму.
Що виходять в результаті MPI-програма є "безпечною"
( "safe") в сенсі стандарту MPI [9], тобто, для її успішного
виконання не потрібно буферизація повідомлень. Для того щоб усунути
невизначеність, пов'язану зі стандартним режимом, в поточній версії системи
програмування, налагоджувальному режимі, стандартні команди пересилання замінюються
на синхронні. У майбутньому, коли вдасться вирішити проблему з ідентифікацією
вибраний режим виконання стандартної команди пересилання, це обмеження
буде знято.
6. Висновок
Існує
природне протиріччя між спільністю паралельного відладчика і сервісом,
який він міг би надавати при налагодженні програм, розроблених за допомогою
конкретного паралельного мови програмування, чи комунікаційної
платформи. У даній статті ми розглядаємо один з аспектів побудови
спеціалізованих паралельних відладчиком для конкретної комунікаційної бібліотеки
(MPI) і конкретної мови паралельного програмування (mpC), а саме,
реалізацію команд переміщення на прикладі команди "крок".
Пропонована
синхронна схема команди "крок", з обробкою "тривіальних
паралельних "причин незавершення дозволяє, звільнити користувача від
рутинної роботи і, по можливості, наблизити налагодження паралельної програми до
налагодження послідовної програми. Розглянуто можливість реалізації
пропонованої схеми для відладчика MPI-програм і показано, що вона може бути реалізована
при незначному ускладненні існуючого інтерфейсу "MPI --
відладчик ". Описана реалізація запропонованої схеми в відладчик mpC-програм,
який є складовою частиною інтегрованої системи розробки mpC
Workshop.
Список літератури
Steven S. Lumetta, David E. Culler,
"Mantis User's Guide, Version 1.0", 1994,
http://www.cs.berkeley.edu/projects/parallel/castle/mantis/mantis.tr.html.
Steven S. Lumetta, David E. Culler:
The Mantis Parallel Debugger, Proceedings of SPDT'96: SIGMETRICS Symposium on Parallel
and Distributed Tools.
TotalView Users Guide, Etnus, 2003,
http://www.etnus.com/Download/TV.html.
Lastovetsky A.: Parallel Computing
on Heterogeneous Networks, John Wiley & Sons, New Jersey, 2003, 159-254.
A. Lastovetsky, D. Arapov, A. Kalinov,
and I. Ledovskih, "A Parallel Language and Its Programming System for
Heterogeneous Networks ", Concurrency: Practice and Experience, 12 (13),
2000, pp.1317-1343.
Hood, R.: The p2d2 Project: Building
a Portable Distributed Debugger. Proceedings of the 2nd Symposium on Parallel
and Distributed Tools (SPDT'96). Philadelphia PA, USA, 1996.
Cownie, J., Gropp, W.: A standard
interface for debugger access to message queue information in MPI. In Dongarra,
J., Luque, E., Margalef, T., eds.: Recent Advances in Parallel Virtual Machine
and Message Passing Interface. Volume 1697 of Lecture Notes in Computer
Science., Berlin, Springer (1999) 51-58.
http://www-unix.mcs.anl.gov/mpi/mpi-debug/mpi_interface.h.html.
The MPI Standard version 1.1 June
12, 1995, http://www.netlib.org/mpi/mpi-1.1-report.ps
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту
http://www.citforum.ru/
