1.3 Аналіз поставленої задачі на доцільність розпаралелювання

Темою курсової роботи є паралельні методи розв’язання систем лінійних рівнянь. Метод Якобі.

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

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

2 Розробка паралельного алгоритму

2.1 Виконання основних етапів побудови паралельного алгоритму

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

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

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

Рисунок 2.1 - Схема побудови декомпозиції та встановлення зв’язків між під задачами

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

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

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

Взаємодія потоків між собою відбувається за допомогою семофорів і використання команд sem_post та sem_wait, що надають можливість потокам працювати одночасно. Також семофори надають можливість потокам зупинитася до моменту виконання певних дій (наприклад, безпосереднє обчислення може відбутися, коли процес вводу матриці ще не завершився). Схема взаємодії потоків між собою наведена на рисунку 2.2.

Рисунок 2.2 - Схема взаємодії потоків

Бар’єр

Рисунок 2.3- Схема