Паралельне виконання операцій множення матриць

E = T_пос / (T_пар * P) = 6890742,4 /  (4355674,4 * 8) ≈ 0,884

 

5. Розробка програми

5.1 Вибір середовища

Дана програма написана на мові C++. Для розробки самого паралельного алгоритму множення матриць було обрано шлях використання інтерфейсу передачі повідомлень (МРІ) між процесами, оскільки він має наступні можливості:

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

МРІ (Message Passing Interface) - програмний інтерфейс (API) для передачі інформації, який дозволяє обмінюватися повідомленнями між процесами, що виконують одну задачу. Розроблений Вільямом Гроуппом, Евін Ласко та іншими. MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для великого числа комп'ютерних платформ. Використовується при розробці програм для кластерів і суперкомп'ютерів. Основним засобом комунікації міжпроцесами в MPI є передача повідомлень один одному. Стандартизацією MPI займається MPI Forum. У стандарті MPI описаний інтерфейс передачі повідомлень, який повинен підтримуватися як на платформі, так і в додатках користувача. В даний час існує велика кількість безкоштовних і комерційних реалізацій MPI. Існують реалізації для мов Фортран 77/90, С та С++.

 

5.2 Опис використаних функційMPI

В МРІ функціях використовується поняття комунікатор. - це спеціально створений службовий об'єкт, який об'єднує групу процесів і ряд додаткових параметрів (контекст), використовуваних при виконанні операцій передачі даних.

При розробці програмного  коду були використані наступні функції  бібліотеки МРІ:

1. int MPI_Init(int *argc, char ***argv), де

argc - вказівник на кількість параметрів командного рядка;

argv - параметри командного рядка.

Використовується для  ініціалізації середовища виконання MPI-програми.

2. int MPI_Finalize(void).

Завершує виконання МРІ  програми.

3. int MPI_Comm_size(MPI_Comm comm, int *size), де

comm - комунікатор, розмір якого визначається;

size - визначена кількість процесів в комунікаторі.

Визначає кількість процесів у виконуваній паралельній програмі.

4. int MPI_Comm_Rank(MPI_Comm comm, int *rank), де

comm - комунікатор, в якому визначається ранг процесу;

rank - ранг процесу в комунікаторі.

Визначає ранг процесу.

Як правило, виклик функцій Mpi_comm_size і Mpi_comm_rank виконується відразу після Mpi_init для отримання загальної кількості процесів і рангу поточного процесу.

5. int MPI_Send(void *buf, int count, MPI_Datatype type, int dest,  int tag, MPI_Comm comm), де

buf - адреса буфера пам'яті, в якому розташовуються дані повідомлення, що відправляється;

count - кількість елементів даних в повідомленні;

type - тип елементів даних повідомлення, що пересилається;

dest - ранг процесу, якому відправляється повідомлення;

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

comm - комунікатор, в рамках якого виконується передача даних.

Викликається процесом-відправником для відправлення повідомлення іншому процесу.

6. int MPI_Recv(void *buf, int count, MPI_Datatype type, int source,int tag, MPI_Comm comm, MPI_Status *status), де

buf, count, type - буфер пам'яті для прийому повідомлення, призначення кожного окремого параметра відповідає опису в MPI_Send.

source - ранг процесу, від якого повинен бути виконаний прийом повідомлення.

tag - тег повідомлення, яке повинне бути прийняте для процесу.

comm - комунікатор, в рамках якого виконується передача даних.

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

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

7. int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype datatype, int dest, int sendtag, int source, int recvtag, MPI_Comm comm, MPI_Status *status)

buf, count, type - буфер пам'яті для прийому повідомлення, призначення кожного окремого параметра відповідає опису в MPI_Send.

dest - ранг процесу, якому відправляється повідомлення;

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

source - ранг процесу, від якого повинен бути виконаний прийом повідомлення.

recvtag - тег повідомлення, яке повинне бути прийняте для процесу.

comm - комунікатор, в рамках якого виконується передача даних.

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

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

8. int MPI_Isend(void *buf, int count, MPI_Datatype type, int dest,  int tag, MPI_Comm comm, MPI_Request *request), де

buf - адреса буфера пам'яті, в якому розташовуються дані повідомлення, що відправляється;

count - кількість елементів даних в повідомленні;

type - тип елементів даних повідомлення, що пересилається;

dest - ранг процесу, якому відправляється повідомлення;

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

comm - комунікатор, в рамках якого виконується передача даних.

request - – вказівник на ідентифікатор комунікаційної події;

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

9. int MPI_Wait (MPI_Request *request, MPI_Status *status), де

request – вказівник на ідентифікатор комунікаційної події;

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

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

10. int MPI_Waitall (int count, MPI_Request *array_of_requests, MPI_Status *array_of_statuses), де

count – кількість елементів в масиві ідентифікаторів;

array_of_requests – масив ідентифікаторів комунікаційних подій;

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

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

 

Для елементів матриць  був обраний цілий тип int, а у функціях передачі повідомлень МРІ використаний наслідуваний тип MPI_INT із мови С.

Всі вхідні матриці та вихідні  результуючі матриці паралельного та послідовного алгоритмів зберігаються у файлах (example.txt, input.txt, output.txt, test.txt відповідно) у вигляді лінійного представлення матриць із розподіленням 1 рядок матриці на 1 рядок файлу.

Код генератора вхідних матриць  присутній на початку програми до МРІ частини коду і може бути використаний для генерації нових матриць  та відповідних їм файлів.

 

5.3 Розробка загальної блок-схеми програми

Беручи за основу функціональну  схему паралельного множення двох матриць  із завантаження даних через один процесор (рис. 3.1), і виходячи із обраних програмних засобів реалізації паралельного алгоритму, було розроблено загальну блок-схему програми множення двох матриць.

 

Рис. 5.1 Загальна блок-схема програми множення двох матриць

 

Висновки

Під час виконання курсової роботи був розроблений алгоритм паралельного множення двох матриць та визначена ефективность розпаралелення. Загальний час виконання операцій при використані паралельного алгоритму рівний  4355674,4 * t_w, тоді як час виконання послідовного алгоритму - 30817782,4 * t_w, що в 7 разів більше. Враховуючи затрати часу, можна встановити, що множення і додавання – найбільш ресурсозатратні дії. Ефективність використання процесорів становить 88,4%,  що є непоганим показником.

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

 

Список використаної літератури

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
2. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.
3. Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
4. Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
5. Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
6. Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
7. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
8. С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных вычислительных систем. – СПб: БХВ-Петербург, 2002.
9. Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 1984. -264 с., ил.

10. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.

11. http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.

12. http://www.hpc.nw.ru – Високопродуктивні обчислення.