Размещено на http://www.allbest.ru/

ОДЕСЬКА ДЕРЖАВНА АКАДЕМІЯ ХОЛОДУ

ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

КАФЕДРА ІНФОРМАЦІЙНО-КОМУНІКАЦІЙНИХ ТЕХНОЛОГІЙ

КУРСОВА РОБОТА

по дисципліні: "Паралельні і розподілені обчислення"

Виконав студент 3 курсу групи 532

Михайлов Сергій

Науковий керівник Бондаренко В.Г.

ОДЕСА - 2012р.

Завдання

На курсову роботу студентові Михайлову Сергію.

1. Теоретична частина.

Описати стандарти OpenMP i MPI, як основні засоби програмування для багатопроцесорних систем.

2. Практична частина.

Завдання 1. Розробити програму паралельного розрахунку означеного інтеграла для функції з кроком дискретизації 0,00002.

Завдання 2. Розробити паралельну програму множення квадратної матриці на квадратну матрицю.

Оглавление

• Введення
• 1. Теоретична частина. Варіант 3. Описати стандарти OpenMP i MPI, як основні засоби програмування для многопроцесорних систем
• 1.1 OpenMР
• 1.1.1 Директиви OpenMP
• 1.1.2 Оператори OpenMP Оператори OpenMP використовуються спільно з директивами
• 1.2 MPI
• 2. Практична частина
• 2.1 Завдання А. Варіант 7. Розробити програму паралельного розрахунку означеного інтеграла для функції з кроком дискретизації 0,00002
• 2.1.1 Метод рішення
• 2.1.2 Алгоритм і блок-схема роботи програми
• 2.1.3 Текст програми
• 2.1.4 Таблиця і графік проведених експериментів
• 2.1.5 Висновок
• 2.2 Завдання Б. Варіант 3. Розробка паралельної програми множення квадратної матриці на квадратну матрицю
• 2.2.1 Постановка завдання
• 2.2.2 Послідовний алгоритм множення двох квадратних матриць
• 2.2.3 Текст програми
• 2.2.4 Результати обчислювальних експериментів
• 2.2.5 Висновки
• Перелік посилань

Введення

Минуло мало чим більше 50 років з моменту появи перших електронних обчислювальних машин - комп'ютерів. За цей час сфера їх вживання охопила практично всі області людської діяльності. Сьогодні неможливо уявити собі ефективну організацію роботи без вживання комп'ютерів в таких областях, як планерування і управління виробництвом, проектування і розробка складних технічних пристроїв, видавнича діяльність, освіта - словом, у всіх областях, де виникає необхідність в обробці великих об'ємів інформації. Проте найбільш важливим як і раніше залишається використання їх в тому напрямі, для якого вони власне і створювалися, а саме, для вирішення великих завдань, що вимагають виконання величезних об'ємів обчислень. Такі завдання виникли в середині минулого століття у зв'язку з розвитком атомної енергетики, авіабудування, ракетно-космічних технологій і ряду інших галузей науки і техніки.

У наш час коло завдань, що вимагають для свого рішення застосування потужних обчислювальних ресурсів, ще більш розширився. Це пов'язано з тим, що сталися фундаментальні зміни в самій організації наукових досліджень. Унаслідок широкого впровадження обчислювальної техніки значно посилився напрям чисельного моделювання і чисельного експерименту. Чисельне моделювання, заповнюючи проміжок між фізичними експериментами і аналітичними підходами, дозволило вивчати явища, які є або дуже складними для дослідження аналітичними методами, або дуже дорогими або небезпечними для експериментального вивчення. При цьому чисельний експеримент дозволив значно здешевити процес наукового і технологічного пошуку. Стало можливим моделювати в реальному часі процеси інтенсивних фізико-хімічних і ядерних реакцій, глобальні атмосферні процеси, процеси економічного і промислового розвитку регіонів і так далі Вочевидь, що вирішення таких масштабних завдань вимагає значних обчислювальних ресурсів.

Обчислювальний напрям вживання комп'ютерів завжди залишався основним двигуном прогресу в комп'ютерних технологіях. Не дивно тому, що як основна характеристика комп'ютерів використовується такий показник, як продуктивність - величина, що показує, яку кількість арифметичних операцій він може виконати за одиницю часу. Саме цей показник з найбільшою очевидністю демонструє масштаби прогресу, досягнутого в комп'ютерних технологіях. Так, наприклад, продуктивність одного з найперших комп'ютерів EDSAC складала всього біля 100 операцій в секунду, тоді як пікова продуктивність найпотужнішого на сьогоднішній день суперкомп'ютера Earth Simulator оцінюється в 40 трильйонів операций/сек. Тобто сталося збільшення швидкодії в 400 мільярдів разів! Неможливо назвати іншу сферу людської діяльності, де прогрес був би настільки очевидний і так великий.

Природно, що у будь-якої людини відразу ж виникає питання: за рахунок чого це виявилося можливим? Як не дивно, відповідь досить проста: зразкове 1000-кратне збільшення швидкості роботи електронних схем і максимально широке розпаралелювання обробки даних.

Ідея паралельної обробки даних як потужного резерву збільшення продуктивності обчислювальних апаратів була висловлена Чарльзом Беббіджем приблизно за сто років до появи першого електронного комп'ютера. Проте рівень розвитку технологій середини 19-го століття не дозволив йому реалізувати цю ідею. З появою перших електронних комп'ютерів ці ідеї неодноразово ставали відправною крапкою при розробці самих передових і продуктивних обчислювальних систем. Без перебільшення можна сказати, що вся історія розвитку високопродуктивних обчислювальних систем - це історія реалізації ідей паралельної обробки на тому або іншому етапі розвитку комп'ютерних технологій, природно, у поєднанні із збільшенням частоти роботи електронних схем.

Принципово важливими рішеннями в підвищенні продуктивності обчислювальних систем були: введення конвеєрної організації виконання команд; включення в систему команд векторних операцій, що дозволяють однією командою обробляти цілі масиви даних; розподіл обчислень на безліч процесорів. Поєднання цих 3-х механізмів в архітектурі суперкомп'ютера Earth Simulator, що складається з 5120 векторно-конвеєрних процесорів, і дозволило йому досягти рекордної продуктивності, яка в 20000 разів перевищує продуктивність сучасних персональних комп'ютерів. Вочевидь, що такі системи надзвичайно дороги і виготовляються в одиничних екземплярах. Ну, а що ж виробляється сьогодні в промислових масштабах? Широка різноманітність вироблюваних в світі комп'ютерів з великою мірою умовності можна розділити на чотири класи:

- персональні комп'ютери (Personal Computer - PC);

- робочі станції (WorkStation - WS);

- суперкомп'ютери (Supercomputer - SC);

- кластерні системи.

Ця умовність розподілення пов'язана в першу чергу з швидким прогресом в розвитку мікроелектронних технологій.

Персональні комп'ютери. Це комп'ютер, призначений для експлуатації одним користувачем, тобто для особистого використання. До ПК умовно можна віднести також і будь-який інший комп'ютер, використовуваний конкретною людиною в якості свого особистого комп'ютера. Персональним комп'ютером називають однопроцесорну систему, що використовує процесори Intel або AMD і що працює під управлінням операційних систем Microsoft Windows та інших.

Робочі станції. Робоча станція, як місце фахівця, є повноцінний комп'ютер або комп'ютерний термінал (пристрої вводу/виводу, відокремлені і часто віддалені від керуючого комп'ютера), набір необхідного програмного забезпечення, по необхідності доповнюється допоміжним обладнанням. Це найчастіше комп'ютери, які містять від одного до чотирьох RISC процесорів (RISC (Restrictes instruction set computer - комп'ютер із спрощеним набором команд) - архітектура процесора, в якій швидкодія збільшується за рахунок спрощення команд, щоб їх декодування було простіше, а час використання - коротше) і розрахованими на багато користувачів ОС, що відносяться до сімейства OC UNIX.

Суперкомп'ютери. Суперкомп'ютер - обчислювальна машина, значно перевищує за своїми технічними параметрами більшість існуючих комп'ютерів. Як правило, сучасні суперкомп'ютери представляють собою велику кількість високопродуктивних серверних комп'ютерів, з'єднаних один з одним локальною високошвидкісною магістраллю, для досягнення максимальної продуктивності у рамках підходу розпаралелювання обчислювальної задачі.

Кластерні системи. З декількох процесорів і загальної для них пам'яті формується обчислювальний вузол. Якщо отриманої обчислювальної потужності не достатньо, то об'єднується декілька вузлів високошвидкісними каналами. За таким принципом побудовані CRAY, SV1, HP Exemplar, SUN, останні моделі IBM SP2. Кластерні технології стали дешевою альтернативою суперкомпютерів. Сьогодні не складає великих труднощів створити невелику кластерну систему, об'єднавши обчислювальні потужності комп'ютерів окремої лабораторії або навчального класу.

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

паралельне розподілене обчислення матриця

1. Теоретична частина. Описати стандарти OpenMP i MPI, як основні засоби програмування для многопроцесорних систем

1.1 OpenMР

OpenMP стандарт програмного інтерфейсу додатків для паралельних систем з загальною пам'яттю. Підтримує мови C, C + +, Фортран.

Модель програми в OpenMP

Рис. 1.1 Модель паралельної програми в OpenMP

Модель паралельної програми в OpenMP можна сформулювати наступним чином:

Програма складається з послідовних і паралельних секцій (рис. 1,1).

У початковий момент часу створюється головна нитка, яка виконує послідовні секції програми.

При вході в паралельну секцію виконується операція fork, що породжує сімейство ниток. Кожна нитка має свій унікальний числовий ідентифікатор (Головної нитки відповідає 0). При розпаралелювання циклів всі паралельні нитки виконують один код. У загальному випадку нитки можуть виконувати різні фрагменти коду.

При виході з паралельної секції виконується операція join. Завершується виконання всіх ниток, крім головної.

OpenMP складають наступні компоненти:

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

Змінні оточення - використовуються для управління поведінкою паралельної програми. Змінні оточення задаються для середовища виконання паралельної програми відповідними командами (наприклад, командами оболонки в операційних системах UNIX). Використання директив компілятора і підпрограм бібліотеки підпорядковується правилам, які розрізняються для різних мов програмування. Сукупність таких правил називається прив'язкою до мови.

Прив'язка до мови C

У програмах на мові С, імена функцій і змінних оточення OMP починається з omp, omp_ або OMP_. Формат директиви: # pragma omp директива [оператор_1 [, оператор_2, …]] В OpenMP-програмі використовується заголовний файл omp. h

Приклад програми на мові С з використаннямOpenMP:

#include "omp. h"

#include <stdio. h>

double f (double x)

{

return 4.0/ (1 + x * x);

}

main () {

const long N = 100000;

long i;

double h, sum, x;

sum = 0; 21

h = 1.0/N;

#pragma omp parallel shared (h)

{

#pragma omp for private (x) reduction (+: sum)

for (i = 0; i < N; i++) {

x = h * (i + 0.5);

sum = sum + f (x);

}

}

printf ("PI = %f\n", sum / N);

}

1.1.1 Директиви OpenMP

Далі наводиться перелік директив OpenMP. Описи директив OpenMP орієнтовані на специфікацію версії 2.5.

parallel

…

end parallel

private;

shared;

default;

firstprivate;

reduction;

if;

copyin;

num_threads.

sections

…

end sections

Обрамляє паралельну секцію програми. Вкладені секції програми, що задаються директивами section, розподіляються між нитками. З даною директивоюможуть використовуватися наступні оператори:

private;

firstprivate;

lastprivate;

reduction;

nowait.

single

…

end single

Обрамляє блок програми, який повинен виконуватися однією ниткою. З даною директивою можуть використовуватися наступні оператори:

private;

firstprivate;

copyprivate;

nowait.

Визначає межі паралельної секції програми. З даною директивою можуть використовуватися наступні оператори (їх опис дається далі):

workshare

…

end workshare

Ділить блок на частини, виконання яких розподіляється між нитками таким чином, що кожна частина виконується один раз. Блок може містити тільки такі конструкції:

привласнення масивів;

скалярні присвоювання;

FORALL;

WHERE;

atomic;

critical;

parallel.

parallel do

цикл do

end parallel do

Об'єднує директиви parallel і do.

parallel sections

.

end parallel sections

Об'єднує директиви parallel і sections.

parallel workshare .

end parallel workshare Об'єднує директиви parallel і workshare.

master

.

end master

Обрамляє блок програми, який повинен виконуватися тільки головною ниткою.

critical [ (блокування)]

.

end critical [ (блокування)]

Обрамляє блок програми, доступ до якого в будь-який момент часу може отримати тільки одна нитка (критична секція).

Блокування - необов'язкове ім'я критичної секції.

Квадратні дужки вказують, що ім'я не є обов'язковим і може бути опущено.

barrier Директива бар'єрної синхронізації ниток. Кожна нитка, виконання якої досягло даної точки, призупиняє своє виконання до тих пір, поки всі нитки не досягнуть даної точки.

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

x = x {+ | - | * | / |. AND. |. OR. |. EQV. |. NEQV. } скалярное_выражение_не_содержащее_x x = скалярное_выражение_не_содержащее_x {+ | - | * | / |. AND. |. OR. |. EQV. |. NEQV. } X x = {MAX | MIN | IAND | IOR | IEOR} (x, скалярное_выражение_не_содержащее_x) x = {MAX | MIN | IAND | IOR | IEOR} (Скалярное_выражение_не_со держащее_x, x) flush [ (список змінних)]

Дана директива задає точку синхронізації, в якій значення змінних, зазначених у списку і видимих з даної нитки, записуються в пам'ять. Цим забезпечується узгодження вмісту пам'яті, доступного різним ниткам.

ordered

.

end ordered

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

threadprivate (список common-блоків)

Визначає common-блоки, перераховані в списку, локальними.

1.1.2 Оператори OpenMP Оператори OpenMP використовуються спільно з директивами

private (список змінних) Оголошує змінні зі списку локальними.

firstprivate (список змінних)

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

lastprivate (список змінних)

Оголошує змінні зі списку локальними і призначає їм значення з того блоку програми, який був виконаний останнім.

copyprivate (список змінних)

Після завершення виконання блоку, заданого директивою single, значення локальних змінних зі списку розподіляються між іншими нитками.

nowait

Скасовує бар'єрну синхронізацію при завершенні виконання паралельної секції.

shared (список змінних)

Оголошує змінні зі списку загальними для всіх ниток.

default (private | shared | none)

Даний оператор дозволяє змінити правила визначення області видимості змінних, діють за умовчанням. Варіант private використовується тільки в мові Fortran. reduction (операція | вбудована функція: список змінних) Оператор приведення значень локальних змінних зі списку за допомогою зазначеної операції або вбудованої функції мови. Операція редукції застосовується до декільком значенням і повертає одне значення.

if (скалярний логічне вираз)

Умовний оператор.

num_threads (скалярний цілий вираз)

Задає кількість ниток. Альтернативний спосіб завдання кількості ниток забезпечує змінну оточення OMP_NUM_THREADS.

schedule (характер_распределения_итераций ([количество_итерацій_цикла])

Даний оператор задає спосіб розподілу ітерацій циклу між нитками:

static - кількість ітерацій циклу, переданих для виконання кожної нитки фіксоване і розподіляється між нитками за принципом кругового планування.

Якщо кількість ітерацій не зазначено, воно вважається рівним 1;

dynamic - кількість ітерацій циклу, переданих для виконання кожної нитки фіксовано. Чергова "порція" ітерацій передається звільнилася нитки;

guided - кількість ітерацій циклу, переданих для виконання кожної нитки поступово зменшується. Чергова "порція" ітерацій передається звільнилася нитки;

runtime - тип розподілу роботи визначається під час виконання програми, наприклад, за допомогою змінної оточення OMP_SCHEDULE.

copyin (список імен common-блоків). При виконанні цього оператора дані з головної нитки копіюються в локальні екземпляри common-блоку на початку кожної паралельної секції. Імена задаються міжсимволами "/".

Підпрограми OpenMP

Підпрограми, що формують середовище виконання паралельної програми Тут і далі спочатку наводиться інтерфейс підпрограм OpenMP для мови C, потім для мови Fortran.

void omp_set_num_threads (int threads);

subroutine omp_set_num_threads (threads) integer threads

Задає кількість потоків (threads) при виконанні паралельних секцій програми.

int omp_get_num_threads (void);

integer function omp_get_num_threads ()

Повертає кількість потоків, використовуваних для виконання паралельної секції.

int omp_get_max_threads (void);

integer function omp_get_max_threads ()

Повертає максимальну кількість потоків, які можна використовувати для виконання паралельних секцій програми.

int omp_get_thread_num (void);

integer function omp_get_thread_num ()

Повертає ідентифікатор нитки, з якої викликається дана функція.

int omp_get_num_procs (void);

integer function omp_get_num_procs ()

Повертає кількість процесорів, доступних в даний момент програмі.

int omp_in_parallel (void);

logical function omp_in_parallel ()

Повертає значення true при виклику з активної паралельної секції програми.

void omp_set_dynamic (int threads);

subroutine omp_set_dynamic (threads) logical threads

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

int omp_get_dynamic (void);

logical function omp_get_dynamic ()

Повертає значення true, якщо динамічне призначення кількості потоків дозволено.

void omp_set_nested (int nested);

subroutine omp_set_nested (nested) integer nested

Дозволяє або забороняє вкладений паралелізм. За замовчуванням вкладений паралелізм заборонений.

int omp_get_nested (void);

logical function omp_get_nested ()

Визначає, чи дозволений вкладений паралелізм.

Підпрограми для роботи з блокуваннями

Блокування використовуються для запобігання ефектів, що призводять до непередбачуваного (Недетермінірованного) поведінки програми. Серед таких ефектів, наприклад, гонки за даними, коли більш ніж один потік має доступ до однієї і тієї ж змінної.

void omp_init_lock (omp_lock_t * lock);

subroutine omp_init_lock (lock) integer (kind = omp_lock_kind):: lock

Ініціалізує блокування, пов'язану з ідентифікатором lock, для використання в наступних викликах підпрограм.

void omp_destroy_lock (omp_lock_t * lock);

subroutine omp_destroy_lock (lock) integer (kind = omp_lock_kind):: lock

Перекладає блокування, пов'язану з ідентифікатором lock, в стан невизначеності.

void omp_set_lock (omp_lock_t * lock);

subroutine omp_set_lock (lock) integer (kind = omp_lock_kind):: lock

Перекладає потоки зі стану виконання в стан очікування до тих пір, поки блокування, пов'язана з ідентифікатором lock, не виявиться оступною. Потік стаєвласником доступною блокування.

void omp_unset_lock (omp_lock_t * lock);

subroutine omp_unset_lock (lock) integer (kind = omp_lock_kind):: lock

Після виконання даного виклику потік перестає бути власником блокування, пов'язаної з ідентифікатором lock. Якщо потік не був власником блокування, результат виклику не визначений.

int omp_test_lock (omp_lock_t * lock);

logical function omp_test_lock (lock) integer (kind = omp_lock_kind):: lock

Повертає значення "істина", якщо блокування пов'язана з ідентифікатором lock.

void omp_init_nest_lock (omp_nest_lock_t * lock);

subroutine omp_init_nest_lock (lock) integer (kind = omp_nest_lock_kind):: lock

Ініціалізує вкладену блокування, пов'язану з ідентифікатором lock.

void omp_destroy_nest_lock (omp_nest_lock_t * lock);

subroutine omp_destroy_nest_lock (lock) integer (kind = omp_nest_lock_kind):: lock

Перекладає вкладену блокування, пов'язану з ідентифікатором lock, в стан невизначеності.

void omp_set_nest_lock (omp_nest_lock_t * lock);

subroutine omp_set_nest_lock (lock) integer (kind = omp_nest_lock_kind):: lock

Перекладає виконуються потоки в стан очікування до тих пір, поки вкладена блокування, пов'язана з ідентифікатором lock, не стане доступною. Потік стає власником блокування.

void omp_unset_nest_lock (omp_nest_lock_t * lock);

subroutine omp_unset_nest_lock (lock) integer (kind = omp_nest_lock_kind):: lock

Звільняє виконується потік від володіння вкладеної блокуванням, пов'язаної ідентифікатором lock. Якщо потік не був власником блокування, результат не визначений.

int omp_test_nest_lock (omp_nest_lock_t * lock);

integer function omp_test_nest_lock (lock) integer (kind = omp_nest_lock_kind):: lock

Функція, що дозволяє визначити, чи пов'язана вкладена блокування з ідентифікатором lock. Якщо пов'язана, повертається значення лічильника, в іншому випадку повертається значення 0.

Таймери

Для профілювання OpenMP програми можна використовувати таймери.

double omp_get_wtime (void);

double precision function omp_get_wtime ()

Повертає час у секундах, що минув з довільного моменту в минулому. Точка відліку залишається незмінною протягом усього часу виконання програми.

double omp_get_wtick (void);

double precision function omp_get_wtick ()

Повертає час у секундах, що минув між послідовними "тиками". Цей час є мірою точності таймера.

Змінні оточення OpenMP

Змінні оточення задаються наступним чином:

export ЗМІННА = значення (в середовищі UNIX)

set ЗМІННА = значення (в середовищі Microsoft Windows)

OMP_NUM_THREADS

Задає кількість ниток при виконанні паралельних секцій програми.

OMP_SCHEDULE

Задає спосіб розподілу ітерацій циклів між нитками. Можливі значення:

static;

dynamic;

guided.

Кількість ітерацій (необов'язковий параметр) вказується після одного з цих ключових слів, відділяючись від нього комою, наприклад:

Export OMP_ SCHEDULE = "static, 10"OMP_DYNAMIC

Якщо цієї змінної присвоєно значення false, динамічний розподіл ітерацій циклів між нитками заборонено, якщо true - дозволено.

OMP_NESTED

Якщо цієї змінної присвоєно значення false, вкладений паралелізм заборонений, якщо true - дозволено

1.2 MPI

MPI-програма являє собою набір незалежних процесів, кожен з яких виконує свою власну програму (неnобов'язково одну і ту ж), написану на мові C або FORTRAN. З'явилися реалізації MPI для C + +, проте розробники стандарту MPI за них відповідальності не несуть. Процеси M P I-програми взаємодіють один з одним за допомогою виклику комунікаційних процедур. Як правило, кожен процес виконується у своєму власному адресному просторі, однак допускається і режим поділу пам'яті.

MPI не специфікує модель виконання процесу - це може бути як послідовний процес, так і багатопотокових. MPI ненадає ніяких засобів для розподілу процесів по обчислювальним вузлам і для запуску їх на виконання. Ці функції покладаються або на операційну систему, або на програміста. Зокрема, на n CUBE 2 використовується стандартна команда xnc, а на кластерах - спеціальний командний файл (зкріпт) mpirun, який припускає, що виконані модулі вже якимось чином розподілені по комп'ютерах кластера. MPI не накладає жодних обмежень на те, що процеси будуть розподілені по процесорах, зокрема, можливий запуск MPI-програми з декількома процесами на звичайній однопроцесорній системі.

Для ідентифікації наборів процесів вводиться поняття групи, об'єднує всі або якусь частину процесів. Кожна група утворює область зв'язку, з якою пов'язують спеціальний об'єкт комунікатор галузі зв'язку. Процеси всередині групи нумеруються цілим числом в діапазоні 0. groupsize - 1. Всі комунікаційні операції з деяким комунікатором будуть виконуватися тільки всередині галузі зв'язку, описуваної цим комунікатором. При ініціалізації MPI створюється зумовлена область зв'язку, що містить всі процеси MPI-програми, з якою пов'язують зумовлений комунікатор MPI_COMM_WORLD. У більшості випадків на кожному процесорі запускається один окремий процес, і тоді терміни процесі процесор стають синонімами, а величина groupsize стає рівній NPROCS - числу процесорів, виділених завданню. В подальшому обговоренні ми будемо розуміти саме таку ситуацію і не будемо дуже вже строго стежити за термінологією. Отже, якщо сформулювати коротко, MPI - це бібліотека функцій, забезпечує взаємодію паралельних процесів за допомогою механізму передачі повідомлень. Це досить об'ємна і складна бібліотека, що складається приблизно з 130 функцій, у число яких входять:

функції ініціалізації та закриття MPI-процесів;

функції, що реалізують комунікаційні операції типу точка- точка;

функції, що реалізують колективні операції;

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

функції для роботи зі структурами даних;

функції формування топології процесів.

Набір функцій бібліотеки MPI далеко виходить за рамки набору функцій, мінімально необхідного для підтримки механізму передачі повідомлень, описаного в першій частині. Однак складність цієї бібліотеки не повинна лякати користувачів, оскільки, в кінцевому підсумку, все це безліч функцій призначено для полегшення розробки ефективних паралельних програм. Зрештою, користувачеві належить право самому вирішувати, які кошти з наданого арсеналу використовувати, а які ні. В принципі, будь-яка паралельна програма може бути написана з використанням всього 6 MPI-функцій, а достатньо повну і зручне середовище програмування становить набір з 24 функцій. Кожна з MPI функцій характеризується способом виконання:

1. Локальна функція - виконується всередині викликає процесу.

Її завершення не вимагає комунікацій.

2. Нелокальна функція - для її завершення потрібне виконання MPI-процедури іншим процесом.

3. Глобальна функція - процедуру повинні виконувати всі процеси групи. Недотримання цієї умови може призводити до зависання завдання.

4. Блокувальна функція - повернення управління з процедури гарантує можливість повторного використання параметрів, беруть участь у виклику. Ніяких змін в стані процесу, викликав блокуючий запит, до виходу з процедури не може відбуватися.

5. Не блокувальна функція - повернення з процедури відбувається негайно, без очікування закінчення операції і до того, як буде дозволено повторне використання параметрів, що беруть участь в запиті.

Завершення неблокирующих операцій здійснюється спеціальними функціями. Використання бібліотеки MPI має деякі відмінності у мовах C і FORTRAN. У мові C всі процедури є функціями, і більшість з них повертає код помилки. При використанні імен підпрограм і іменованих констант необхідно строго дотримувати регістр символів. Масиви індексуються з 0. Логічні змінні представляються типом int (true відповідає 1, а false - 0). Визначення всіх іменованих констант, прототипів функцій і визначення типів виконується підключенням файлу mpi. h. Введення власних типів у MPI було продиктовано тим обставиною, що стандартні типимов на різних платформах мають різне уявлення. MPI допускає можливість запуску процесів паралельної програми на комп'ютерах різних платформ, забезпечуючи при цьому автоматичне перетворення даних при пересиланнях. У таблиці наведено відповідність зумовлених в MPI типів стандартних типів мови С.

БАЗОВІ ФУНКЦІЇ MPI

Будь яка прикладна MPI-програма (додаток) повинна починатися з виклику функції ініціалізації MPI-функції MPI_Init. В результаті виконання цієї функції створюється група процесів, в яку поміщаються всі процеси додатки, створюється область зв'язку, об'єднує всі процеси-додатки. Процеси у групі впорядковані пронумеровані від 0 до groupsize 1, де groupsize одне число процесів у групі. Крім цього створюється зумовлений комунікатор MPI_COMM_SELF, що описує свою область зв'язку для кожного окремого процесу.

int MPI _ Init (int*argc, char* * * argv)

У програмах на C кожному процесу при ініціалізації передаються аргументи функції main, отримані з командного рядка.

Функція завершення MPI-програм MPI _ Finalize:

int MPI_ Finalize (void)

Функція закриває все MPI-процеси і ліквідує всі галузі зв'язку.

Функція визначення числа процесів в галузі зв'язку

MPI _ Comm _ size int MPI _ Comm _ size (MPI _ Commcomm, int * size)

Функція повертає кількість процесів у галузі зв'язку комунікатора comm. До створення явно груп і пов'язаних з ними комуністичної катори єдино можливими значеннями параметра COMM є MPI _COMM _W ORLD і MPI _COMM _SELF, які створюються автоматично при ініціалізації MPI.

Підпрограма є локальною.

Функція визначення номера процесу MPI _ C omm _ rank

int MPI _ Comm _ rank (MPI _ Commcomm, int * rank)

Функція повертає номер процесу, що викликав цю функцію. Номери процесів лежать в діапазоні 0. size - 1 (значення size може бути визначено за допомогою попередньої функції). Підпрограма є локальної. У мінімальний набір слід включити також дві функції передачі і прийому повідомлень.

Функція передачі повідомлення MPI _ S end

int MPI _ Send (void * buf, intcount, MPI _ Datatypedatatype, intdest, inttag, MPI _ Commcomm)

Функція виконує посилку count елементів типу datatype повідомлення з ідентифікатором tag процесу dest в галузі зв'язку комунікатора comm. Мінлива buf - це, як правило, масив або скалярна змінна. В останньому випадку значення count = 1.

Функція прийому повідомлення MPI _ Recv

int MPI _ Recv (void * buf, intcount, MPI _ Datatypedatatype, intsource, inttag, MPI _Cmmcomm, MPI _ Status * status)

2. Практична частина

2.1 Завдання 1. Розробити програму паралельного розрахунку означеного інтеграла для функції з кроком дискретизації 0,00002

2.1.1 Метод рішення

Рішення багатьох технічних завдань зводиться до обчислення певних інтегралів, точний вираз яких складно, вимагає тривалих обчислень і незавжди виправдане практично. Тут буває цілком достатньо їх наближеного значення. Найпростішим наближеним методом є метод прямокутників. Нехай на відрізку [a,b], a<b, задана безперервна функція f (x). Потрібно обчислити інтеграл чисельно рівний прощу відповідної криволінійної трапеції. Розіб'ємо підставу цієї трапеції, тобто відрізок [a; b], на n рівних частин (відрізків) довжини (крок розбиття) за допомогою точок х0=а, х1, х2,…хn=b. Можна записати, що хі=х0+h*i, де і=1,2,…, n. У середині кожного такого відрізка побудуємо ординату уі=f (сі) графіка функції у= f (х). Прийнявши цю ординату за висоту, будуємо прямокутник з площиною h* уі.

Тоді сума площ всіх n прямокутників дає площа ступінчатої фігури, яка була наближена до наближеного значення шуканого визначеного інтегралу:

Рис. 2.1 Метод прямокутників

Формула середніх прямокутників

Рис. 2.2 Метод лівих прямокутників

Формула метода лівих прямокутників

Рис. 2.3 Метод правих прямокутників

Формула метода правих прямокутників

При використанні бібліотеки MPI площа фігури, описуваною функцією, можна розділити між процесами, потім зібрати обчислені окремими процесами суми і отримати шукану площу.

2.1.2 Алгоритм і блок-схема роботи програми

Рис. 2.4 Блок-схема алгоритму розрахунку означеного інтегралу

Алгоритм роботи програми:

1. Початок роботи програми.

2. Оголошення змінних, присвоєння інтегралу кордон інтеграції із кроком дискретизації, завдання констант.

3. Ініціалізація MPI.

4. Визначення кількості процесів.

5. Визначення номера процесу.

6. Якщо номер процесу дорівнює 0, то починає працювати таймер, в іншому випадку, починається пункт 7.

7. циклом від першого до останнього інтервалу, який визначений номером процесу, з кроком, рівним числу процесорів і підсумуванням висоти відрізань, визначуваних заданою функцією.

8. Обчислення всіх локальних сум площі інтегралу.

9. Якщо номер процесу дорівнює 0, то зупиняємо таймер, виконуємо обчислення площі інтегралу у нульовому процесі,і передача локальної суми від поточного процесу до нульового.

10. Фіналізація MPI.

11. Кінець роботи програми.

2.1.3 Текст програми

#include "stdafx. h"

#include "math. h"

#include "mpi. h"

#include <stdlib. h>

int _tmain (int argc, char* argv [])

{

double PI=3.1415926535897932;

// крок дискретизації

double IntervalWidth = 0.00002;

// інтервал від

double a = PI;

// вивід на екран значення а

printf ("a = %.16f\n", a);

// інтервал до

double b = (PI) /2;

// вивід на екран значення b

printf ("b = %.16f\n", b);

// кількість інтервалів

int numbIntervals = (int) ( (b-a) /IntervalWidth);

// висота інтервалу

double IntervalHeight = 0.0;

// координата поточної точки на осі х

double x = 0.0;

// поточний інтервал

int Interval = 0;

// локальна сума на одному комп'ютері

double summaLocal = 0.0;

// локальна сума на всіх комп'ютерах

double summaGlobal;

// номер процесу

int ProcNumb;

// ранг процесу

int ProcRank;

// ім'я процесу

char processor_name [MPI_MAX_PROCESSOR_NAME];

// довжина імені процесу

int namelen;

// час початку і кінця розрахунку процесу

double t1, t2;

// ініціалізація MPI

MPI_Init (&argc,&argv);

// кількість комп'ютерів у кластері

MPI_Comm_size (MPI_COMM_WORLD,&ProcNumb);

// номер процесу

MPI_Comm_rank (MPI_COMM_WORLD,&ProcRank);

// ім'я процесу у кластері

MPI_Get_processor_name (processor_name,&namelen);

printf ("Process %d of %d running on %s\n", ProcRank,

ProcNumb);

if (ProcRank == 0)

{

printf ("numbIntervals = %i\n", numbIntervals);

t1 = MPI_Wtime ();

}

// цикл від першого до останнього інтервалу з кроком рівним числу процесорів

for (Interval=1+ProcRank; Interval <= numbIntervals; Interval

+=ProcNumb)

{

x = a + (IntervalWidth * ( (double) Interval-0.5));

IntervalHeight += (sin (x) +cos (x));

}

summaLocal = IntervalWidth * IntervalHeight;

printf ("summaLocal is approximately %.16f\n", summaLocal);

MPI_Reduce (&summaLocal, &summaGlobal, 1, MPI_DOUBLE,

MPI_SUM,0,MPI_COMM_WORLD);

if (ProcRank == 0)

{

t2 = MPI_Wtime ();

printf ("Integral is approximately %.16f\n", summaGlobal);

printf ("Time is %f seconds \n", t2-t1);

}

// фіналізація MPI

MPI_Finalize ();

return 0;

}

Значення інтегралу дорівнює 1.8749238809545756

2.1.4 Таблиця і графік проведених експериментів

Проведемо два експерименти розрахунку визначеного інтегралу з різним кроком дискретизації і різною кількістю процесорів у кластері. Заповнимо таблицю результатами:

Таблиця 2.1 Розрахунок визначеного інтегралу

Крок дискретизації / кількість процесів	1 процес	2 процеси	4 процеси	8 процесів
0,0002	0,004235	0,002028	0,002264	0,002635
0,00002	0,0857	0,023864	0,011583	0,013237

Рисунок 2.5 Графік залежності швидкості і часу розрахунку певного інтегралу

2.1.5 Висновок

З таблиці розрахунку визначеного інтегралу і графіку залежності швидкості від часу, ми бачимо, що при використанні паралельних обчислень, час на обробку визначеного інтегралу зменшується (відбувається прискорення обчислення за рахунок того, що кожний комп'ютер виконує менше циклів розрахунку).

Також із таблиці ми можемо побачити, що чим більше процесів ми використовуємо, тим менше часу іде на розрахунок інтегралу. Але, чим більше процесів бере участь у розрахунку інтегралу, тим менше прискорення часу відбувається (якщо ми використовуємо два процеси замість одного, ми отримуємо прискорення у 1.046 разів, а при використанні 8 процесів замість чотирьох, отримаємо прискорення у 1.004 раз). Це відбувається тому,що при збільшенні числа процесів, збільшується і час на передачу повідомлень між процесами.

2.2 Завдання 2. Розробка паралельної програми множення квадратної матриці на квадратну матрицю

2.2.1 Постановка завдання

Множення матриці A розміру mЧn і матриці B розміру nЧl наводить до здобуття матриці C розміру mЧl, кожен елемент якої визначається відповідно до вираження:

Кожен елемент результуючої матриці C є скалярний твір відповідних рядки матриці A і стовпця матриці B:

Цей алгоритм передбачає виконання m*n*l операцій множення і стільки ж операцій складання елементів вихідних матриць. При множенні квадратних матриць розміру nЧn кількість виконаних операцій має порядок O (n3).

Відомі послідовні алгоритми множення матриць, що володіють меншою обчислювальною складністю (наприклад, алгоритм Страссена (Strassen's algorithm)).

Послідовний алгоритм множення матриць представляється трьома вкладеними циклами.

2.2.2 Послідовний алгоритм множення двох квадратних матриць

double MatrixA [Size] [Size];

double MatrixB [Size] [Size];

double MatrixC [Size] [Size];

int i,j,k;

.

for (i=0; i<Size; i++) {

for (j=0; j<Size; j++) {

MatrixC [i] [j] = 0;

for (k=0; k<Size; k++) {