Приклад реалізації паралельних обчислень

Аналізуючи розбиття програми на декілька задач, ми робимо перший крок до реалізації паралелізму в свою програму. В одно процесорному середо­вищі паралелізм реалізується засобами багатозадачності. Це досягається шля­хом перемикання процесів. Кожен процес виконується на протязі деякого коро­ткого інтервалу часу, після чого процесор ²передається² іншому процесу. Це відбувається настільки швидко, що створюється ілюзія одночасного виконання процесів. В багатопроцесорному середовищі процеси, що належать одній прог­рамі, можуть бути призначені одному або різним процесорам. Процеси, призна­чені різним процесорам, виконуються паралельно.

В додатку або системі розрізняють два рівня паралельної обробки: рі­вень процесів і рівень потоків. Паралельна обробка на рівні потоків має назву багато поточність (будемо розглядати пізніше). щоб розумно розділити програ­му на паралельні задачі, необхідно визначити, де ²міститься² паралелізм і де мо­жемо скористатися перевагами від його реалізації. Інколи немає суттєвої нео­бхідності в паралелізмі. Програма може подаватися з врахуванням паралелізму, але і при послідовному виконанні дій вона прекрасно працює. Безумовно, вне­сення паралелізму може підвищити її швидкодію і зменшити рівень складності. Одні програми володіють природнім паралелізмом, а інші більше підходить по­слідовне виконання дій. Програми можуть мати подвійну інтерпретацію.

Таблиця 2.	Поширені архітектури ПЗ, які використовуються для паралельного і розподіленого програмування
Модель	Архітектура	Розподілене програмування	Паралельне програмування
Модель ведучого вузла, інакше кажучи: - головний/підлеглий; - керуючий/виконавчий; - клієнт/сервер	Головний вузол керує задачами, тобто контро­лює їх виконання і пере­дає роботу підлеглим задачам	Ö	Ö
Модель рівноправних вузлів	Всі задачі, в основному, мають однаковий ранг, і робота між ними розподіляється рівномірно		Ö
Векторна або конвеєрна (потокова) обробка	Один виконавчий вузол відповідає кожному еле­менту масиву (вектора) або кроку конвеєра	Ö	Ö
Дерево з батьківськими і дочірніми елементами	Виконавці, які динамічно генеруються у відношенні ²батько/нащадок². Цей тип архітектури корисно використовувати в наступних алгоритмах: - рекурсія; - ²розділяй і володій²; - і/або; - обробка деревоподіб­них структур	Ö	Ö

При декомпозиції програми на функції як правило використовують низ­хідний принцип, а при розділі на об’єкти – висхідний. При цьому необхідно ви­з­начити, які функції або об’єкти краще реалізувати у вигляді окремих програм або підпрограм, а які – у вигляді потоків. Підпрограми повинні виконуватися операційною системою як процеси. Окремі підпрограми, або процеси, викону­ють задачі, доручені проектувальником ПЗ.

Задачі, на які буде розділена програма, можуть виконуватися паралель­но, при чому можемо виділити наступні три способи реалізації паралелізму.

1. Виділення в програмі одної основної задачі, яка створює деяку кіль­кість підзадач.

2. Розділ програми на множину файлів, які виконуються окремо.

3. Розділ програми на декілька задач різного типу, що відповідають за створення підзадач тільки визначеного типу.

Дані способи реалізації паралелізму подано на рис. 5.

Наприклад, ці методи реалізації паралелізму можемо застосувати до про­г­рами візуалізації. Під візуалізацією будемо розуміти процес переходу від подання тривимірного об’єкту у формі записів бази даних в двовимірну тіньову графічну проекцію на поверхню відображення (дисплей).Зображення подається у вигляді тіньових багатокутників, що повторюють форму об’єкту. Етапи візуа­лізації подано на рис 6. Візуалізацію розділимо на колекцію окремих задач.

1. Встановити структуру даних для сіткових моделей багатокутників.

2. Застосувати лінійні перетворення.

3. Забракувати багатокутники, що належать поверхням, яких невидне.

4. Виконати растерізацію.

5.
Ретушувати окремі пікселі.

Перша задача полягає в поданні об’єкта у вигляді масиву багатокутни­ків, в якому кожна вершина багатокутника описується в тривимірній світовій системі координат. Друга задача – застосувати лінійні перетворення до сіткової моделі багатокутників. Ці перетворення використовуються для позиціонування об’єктів на сцені і створення точки огляду або поверхні відображення. (область, яка видима спостерігачу з його точки огляду). Третя задача – відкинути поверх­ні об’єктів, яких не видно на сцені. Це означає видалення ліній, які належать тим частинам об’єктів, які невидимі з точки зору огляду. Четверта задача – пе­ретворити модель вершин в набір координат пік селів. П’ята задача – видалити всі приховані поверхні. Якщо сцена містить взаємодіючі об’єкти, наприклад, коли одні об’єкти заступають інші, то приховані (передніми об’єктами) поверх­ні повинні бути видалені. Шоста задача – нанести на поверхні зображення тінь.

Рішення кожної задачі подається у вигляді окремого файлу, який вико­ну­ється. Перші три задачі (Task1,Task2 та Task3) виконуються послідовно, а ре­шта три (Task1,Task2 та Task3) – паралельно. Реалізація першого способу ство­рення програми візуалізації подано в лістінгу 4.

// Лістінг 4. Використання способу 1 для створення процесів

# include < spawn.h >

# include < stdlib.h >

# include < stdio.h >

# include < sys/wait.h >

# include < errno.h >

# include < unistd.h >

int main (void) {

posix_spwnattr_t Attr;

posix_spwn_file_actions_t FilrActions;

 

int main (void) {

posix_spawnattr_t Attr;

posix_spawn_file_actions_t FileActions;

char *cons argv4[ ] = {“Task4”,..., NULL};

char *cons argv5[ ] = {“Task5”,..., NULL};

char *cons argv6[ ] = {“Task6”,..., NULL};

pid_t Pid;

int stat;

//...

 

// Виконуємо перші три точки синхронно.

system (“Task1...”);

system (“Task2...”);

system (“Task3...”);

 

// Ініціюємо структури.

psix_spwnattr_init (&Attr);

psix_spwn_file_actions_init (&FileActions);

 

// Виконуємо останні три точки асинхронно.

posix_spwn (&Pid, “Task4”, &FileActions, &Attr, argv4, NULL);

posix_spwn (&Pid, “Task5”, &FileActions, &Attr, argv4, NULL);

posix_spwn (&Pid, “Task6”, &FileActions, &Attr, argv4, NULL);

 

// Очікуємо повернення до батьківського процесу.

wait (&stat);

wait (&stat);

wait (&stat);

return (0);

}

В лістінгу 4 із функції main () за допомогою функції system () виклика­ю­ться на виконання задачі Task1, Task2 та Task3. Кожна з них виконується синх­ронно з батьківським процесом. Задачі Task4, Task5 та Task6 виконуються аси­н­хронно батьківському процесу завдяки використанню функцій psix_spwn (). Три крапки використовуються для позначення файлів, які необхідні задачам. Батьківський процес викликає три функції wait (), і кожна з них очікує завер­ше­ння однієї із задач (Task4, Task5 та Task6).

Використовуючи другій спосіб, програму візуалізації можемо запустити із сценарію командної оболонки. Переваги даного сценарію полягають в тому, що він дозволяє використовувати всі команди і оператори оболонки. В нашій програмі візуалізація для управління виконанням задач використовуються мета символи & та &&.

Task1... && Task2... && Task3

Task1... & Task2... & Task3

Тут завдяки використанню метасимволів && задачі Task1, Task2 та Task3 виконуються послідовно при умові успішного виконання попередньої за­дачі. А задачі Task4, Task5 та Task6 виконуються одночасно, оскільки викорис­тано мета символ &. Наведемо деякі мета символи, що застосовуються в сере­до­вищі UNIX/LINUX, та способи виконання цих команд.

&&	Кожна наступна команда буде виконуватися тільки у випадку успішного виконання попередньої команди
½½	Кожна наступна команда буде виконуватися тільки у випадку невдалого виконання попередньої команди
;	Команди повинні виконуватися послідовно
&	Всі команди повинні виконуватися одночасно

При використанні третього способу задачі діляться за категоріями. При декомпозиції програми необхідно розібратися, чи можливо в ній виділити різні категорії задач. Наприклад, одні задачі можуть ²відповідати² за інтерфейс кори­стувача, тобто його створення, ввід даних, вивід даних та інше. Іншим задачам доручається обчислення, управління даними та інше. Такий підхід дуже корис­ний не тільки при проектуванні програми, але і при її реалізації. В нашій прог­рамі візуалізації ми можемо розділити задачі за наступними категоріями:

· задачі, які виконують лінійні перетворення:

перетворення зображення на екрані при зміні точки огляду; зміни сцени;

· задачі, які виконують растерізацію:

рисування ліній;

растерізацію багатокутників;

· задачі, які виконують видалення поверхонь:

видалення прихованих поверхонь;

видалення невидимих поверхонь;

· задачі, які виконують накладання тіней:

затінення окремих пік селів;

затінення зображення вцілому.

Розбиття задачі за категоріями дозволяє нашій програмі набути більш загального характеру. Процеси при необхідності створюють інші процеси, при­значені для виконання дій тільки визначеної категорії. Наприклад, якщо нашій програмі необхідна візуалізація лише одного об’єкту, а не всю сцену, то немає ніякої необхідності породжувати процес, який виконує видалення прихованих поверхонь; Цілком достатньо буде видалення поверхонь, які не видно (одного об’єкту). Якщо об’єкт непотрібно затінювати, то немає необхідності породжу­вати задачу, яка виконує накладання тіні; обов’язковим лишається лише лінійне перетворення при рішення задачі растерізації. Для запуску програми з викори­станням третього способу можемо використовувати батьківський процес або сценарій оболонки. Батьківський процес може визначити, який тип візуалізації необхідно, і передати відповідну інформацію кожному із спеціалізованих про­цесів, щоб вони ²знали², які процеси їм необхідно породжувати. Дана ін форма­ція може бути пере направлена кожному із спеціалізованих процесів зі сцена­рію оболонки. Реалізація третього способу подана в лістінгу 5.

// Лістінг 5. Використання способу 3 для створення процесів.

// Задачі запускаються з батьківського процесу.

# include < spawn.h >

# include < stdlib.h >

# include < stdio.h >

# include < sys/wait.h >

# include < errno.h >

# include < unistd.h >

int main (void) {

posix_spwnattr_t Attr;

posix_spwn_file_actions_t FilrActions;

pid_t;

ins stat;

 

//...

 

system (“Task1... ”);

 

// Виконується безвідносно до типу візуалізації, яка використовується

// Визначаємо, який тип візуалізації необхідно. Це можемо реалізувати, от-

// римавши від користувача або виконав спеціальний аналіз. В наступно­­му

// повідомляємо про результати іншим задачам за допомогою аргументів.

char *cons argv4[ ] = {“TaskType4”,..., NULL};

char *cons argv5[ ] = {“TaskType5”,..., NULL};

char *cons argv6[ ] = {“TaskType6”,..., NULL};

 

system (“Task2...”);

system (“Task3...”);

 

// Ініціюємо структури

posix_spwnattr_init (&Attr);

posix_spwn_file_actions_init (&FileActions);

posix_spwn (&Pid, “TaskType4”, &FileActions, &Attr, argv4, NULL);

posix_spwn (&Pid, “TaskType5”, &FileActions, &Attr, argv5, NULL);

if (Y) {

psix_spwn (&Pid, “TaskType6”, &FileActions, &Attr, argv6, NULL);

 

// Очікуємо повернення до батьківського процесу.

wait (&stat);

wait (&stat);

wait (&stat);

return (0);

}

 

// Всі TaskType-задачі повинні бути аналогічними

 

//...

int main (int argc, char *argv [ ]) {

int Rt;

//...

int (argv [1] = =

// Ініціюємо структури.

//...

posix_spwn (&Pid, “TaskType5”, &FileActions, &Attr, argv5, NULL);

}

wait (&stat);

exit (0); }

Лінії видимого контуру

Породження процесі, як подано в лістінгу 6, можливе за допомогою фу­нкцій, які викликаються із функції mane ().

// Лістінг 6. Основна гілка програми, з якої викликається функція,

// що породжує процес

int main (int argc, char *argv [ ]) {

//...

Rt = func1 (X, Y, Z);

//... }

// Визначення функції.

int func1 (char *M, char *N, char *V) {

//...

char *const args [ ] = {“TaskX”, M, N, V, NULL};

Pid = fork ();

if (Pid = = 0) {

exec ({“TaskX”, args); }

if (Pid > 0) {

//... }

wait (&stat); }

В лістінгу 6. функція func1 викликається з трьома аргументами. Ці аргу­менти передаються породженому процесу.

Процеси також можуть породжуватися із методів, які належать об’єктам. Як подано в лістінгу 7, об’єкти можна оголосити в довільному процесі.

// Лістінг 7. Оголошення об’єкту в процесі

 

//...

my_object MyObject;

//...

// Оголошення та визначення класу.

class my_object {

public:

//...

int spawnProcess (int X);

//... };

int my_object:: spawnProcess (int X) {

//...

//... posix_spawn () або system ()

//... }

Як подано в лістінгу 7, об’єкт може створювати довільну кількість про­цесів з довільного методу.

Завдання до курсової роботи