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

Міністерство освіти і науки України

ДВНЗ «Криворізький національний університет»

Кафедра комп'ютерних систем та мереж

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

з дисципліни “Комп'ютерні системи ”

На тему: «MPP (massive parallel processing) - масивно-паралельна архітектура типу Red Storm»

Виконав

ст. гр. КСМ-09-2

Горевой Роман

Прийняв:

доктор технічних наук, доцент

Купін А.І.

Кривий Ріг, 2013

ВСТУП

Темою курсової роботи є «MPP (massive parallel processing) - масивно-паралельна архітектура типу Red Storm». Головна особливість архітектури МРР полягає в тому, що пам'ять фізично розділена. У цьому випадку система будується з окремих модулів, що містять процесор, локальний банк операційної пам'яті (ОП), два комунікаційних процесора (рутера) або мережевий адаптер, іноді - жорсткі диски та інші пристрої введення / виведення. Один рутер використовується для передачі команд, інший - для передачі даних. По суті, такі модулі представляють собою повнофункціональні комп'ютери.

Головною перевагою систем з роздільною пам'яттю є хороша масштабованість: на відміну від SMP-систем, в машинах з роздільною пам'яттю кожен процесор має доступ тільки до своєї локальної пам'яті, у зв'язку з чим не виникає необхідності в потактовій синхронізації процесорів. Практично всі рекорди по продуктивності в 1990-і роки встановлені на машинах саме такої архітектури, які складаються з кількох тисяч процесорів (ASCI Red, ASCI Blue Pacific). Проте відсутність спільної пам'яті помітно знижує швидкість межпроцесорного обміну, оскільки немає загального середовища для зберігання даних, призначених для обміну між процесорами. Потрібна спеціальна техніка програмування для реалізації обміну повідомленнями між процесорами.

Користувач може визначити логічний номер процесора, до якого він підключений, і організувати обмін повідомленнями з іншими процесорами. Використовуються два варіанти роботи операційної системи на машинах MPP-архітектури. В одному повноцінна операційна система працює тільки на керуючий машині (front-end), на кожному окремому модулі функціонує сильно урізаний варіант ОС, що забезпечує роботу тільки розташованої в ньому гілки паралельного додатка. У другому варіанті на кожному модулі працює повноцінна UNIX-подібна ОС, що встановлюється окремо.

Отже метою виконання курсової роботи є дослідження масивно-паралельної архітектури МРР типу Red Storm, а також розробка паралельного алгоритму та програмна реалізація обчислення особистих чисел матриці із аналізом залежності часу виконання від кількості потоків для різної величини матриць. red storm мтриця програмний

Постановка задачі

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

1. Дослідження MPP (massive parallel processing) - масивно-паралельної архітектури типу Red Storm;

2. Розробка алгоритму паралельного обчислення особистих чисел матриці та реалізація його програмно із застосуванням мови C# та Visual Studio IDE;

3. Аналіз показників продуктивності написаної програми.

1. ПРОЕКТНА ЧАСТИНА

1.1 Масивно-паралельна архітектура МРР

Один з перших у світі комп'ютерів EDSAC (1949 р.) виконував близько 100 арифметичних операцій в секунду. Продуктивність найпотужніших сучасних комп'ютерів становить кілька десятків трильйонів операцій в секунду. Безсумнівно, однією з причин є вдосконалення елементної бази. Зміна електронних ламп транзисторами, поява інтегральних схем, розробка кремнієвих чіпів - кожна з цих подій виробляло революцію в комп'ютерній техніці. Сучасні технології створення чіпів дозволяють працювати з елементами розмірів порядку десятих часток мікрона (10-6 м). Регулярне зменшення розмірів чіпів забезпечує еволюційне зростання тактової частоти роботи процесорів. Так, EDSAC мав час такту 2 мікросекунди (10-6 сек), а сучасний комп'ютер Hewlett-Packard V2600 виконує один такт за 1.8 наносекунди (10-9 сек). Тобто HP V2600 виконує одну процесорну команду в 1000 разів швидше. У той же час його продуктивність складає 77 мільярдів операцій в секунду, і це в сімсот мільйонів разів більше, ніж у EDSAC. Таке зростання продуктивності не може пояснюватися тільки лише зміною елементної бази.

Друга за рахунком, але перша за значенням причина полягає у використанні нових рішень в архітектурі комп'ютера. У обчислювальній науці використовуються три терміни, пов'язані з пристроєм електронно-обчислювальної машини. Архітектура комп'ютера - це опис компонент комп'ютера та їх взаємодії. Організація комп'ютера - це опис конкретної реалізації архітектури, її втілення "в залізі". Комп'ютери CRAY, наприклад, мають подібну архітектуру. З точки зору програміста, у них однакове число внутрішніх регістрів, використовуваних для тимчасового зберігання даних, однаковий набір машинних команд, однаковий формат представлення даних. Організація ж комп'ютерів Cray різних моделей може істотно розрізнятися: у них може бути різне число процесорів, різний розмір оперативної пам'яті, різний швидкодію і т.д. Третій термін - це схема комп'ютера, детальний опис його електронних компонент, їх сполук, пристроїв живлення, охолодження та інших. Програмісту досить часто потрібне знання архітектури комп'ютера, рідше його організації і ніколи - схеми комп'ютера.

Революцію в комп'ютерних архітектурах справив принцип паралельної обробки даних, що втілює ідею одночасного (паралельного) виконання кількох дій. Паралельна обробка даних має два різновиди: конвеєрні та власне паралельність. Якщо якийсь пристрій виконує одну операцію за одиницю часу, то тисячу операцій воно виконає за тисячу одиниць. Якщо припустити, що є п'ять таких же незалежних пристроїв, здатних працювати одночасно, то ту ж тисячу операцій система з п'яти пристроїв може виконати вже не за тисячу, а за двісті одиниць часу. Аналогічно система з N пристроїв ту ж роботу виконає за 1000 / N одиниць часу. Однак це ідеальне прискорення вдається отримати лише в дуже спеціальних ситуаціях, коли підзадачі повністю незалежні (наприклад, завдання перебору, злом паролів). Щоб стало зрозуміліше, розглянемо приклад з життя. Якщо одна людина скопує один квадратний метр землі за дві хвилини, то це не означає, що дванадцять чоловік скопати його за десять секунд: вони будуть заважати один одному і робота тільки сповільниться. Що ж до обчислень, тобто такі алгоритми, які при розпаралелюванні не тільки не дають прискорення, але навіть сповільнюються.

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

Мабуть, найбільш ранній і найбільш відомою є класифікація архітектур обчислювальних систем, запропонована в 1966 році М. Флінном. Класифікація базується на понятті потоку, під яким розуміється послідовність елементів, команд або даних, обробляється процесором. На основі числа потоків команд і потоків даних Флінн виділяє чотири класи архітектур: SISD, MISD, SIMD, MIMD.

SISD (single instruction stream / single data stream) - одиночний потік команд і одиночний потік даних. До цього класу належать, насамперед, класичні послідовні машини, або інакше, машини Фон-неймановскую типу. У таких машинах є тільки один потік команд, всі команди обробляються послідовно один за одним, і кожна команда ініціює одну операцію з одним потоком даних.

SIMD (single instruction stream / multiple data stream) - одиночний потік команд і множинний потік даних. У архітектурах подібного роду зберігається один потік команд, що включає, на відміну від попереднього класу, векторні команди. Це дозволяє виконувати одну арифметичну операцію відразу над багатьма даними - елементами вектора. Спосіб виконання векторних операцій не обмовляється, тому обробка елементів вектора може проводитися або процесорної матрицею, як у ILLIAC IV, або за допомогою конвеєра, як, наприклад, в машині CRAY-1.

MISD (multiple instruction stream / single data stream) - множинний потік команд і одиночний потік даних. Визначення має на увазі наявність в архітектурі багатьох процесорів, що обробляють один і той же потік даних. Проте ні Флінн, ні інші фахівці в галузі архітектури комп'ютерів до цих пір не змогли представити переконливий приклад реально існуючої обчислювальної системи, побудованої на даному принципі. Ряд дослідників відносять конвеєрні машини до даного класу, однак це не знайшло остаточного визнання в науковому співтоваристві. Будемо вважати, що поки даний клас порожній.

MIMD (multiple instruction stream / multiple data stream) - множинний потік команд і множинний потік даних. Цей клас припускає, що в обчислювальній системі є кілька пристроїв обробки команд, об'єднаних в єдиний комплекс і працюючих кожне зі своїм потоком команд і даних. Запропонована схема класифікації аж до теперішнього часу є самою застосовуваної при початковій характеристиці того чи іншого комп'ютера. Якщо говориться, що комп'ютер належить класу SIMD або MIMD, то відразу стає зрозумілим базовий принцип його роботи, і в деяких випадках цього буває достатньо. Однак видно і явні недоліки. Зокрема, деякі заслуговують на увагу архітектури, наприклад, dataflow і векторно-конвеєрні машини, чітко не вписуються в дану класифікацію. Інший недолік - це надмірна заповненість класу MIMD. Необхідно засіб, більш вибірково систематизуюче архітектури, які за Флинном потрапляють в один клас, але зовсім різні за кількістю процесорів, природі і топології зв'язку між ними, за способом організації пам'яті і, звичайно ж, за технологією програмування.

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

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

Основні причини появи масивно-паралельних комп'ютерів - це, по-перше, необхідність побудови комп'ютерів з гігантською продуктивністю, і, по-друге, необхідність виробництва комп'ютерів у великому діапазоні як продуктивності, так і вартості. Не всі в змозі купити однопроцесорний CRAY Y-MP C90, та й не завжди такі потужності й потрібні. Для масивно-паралельного комп'ютера, в якому число процесорів може сильно змінюватися, завжди можна підібрати конфігурацію із заздалегідь заданою продуктивністю та / або вартістю.

З деякою мірою умовності, масивно-паралельні комп'ютери можна характеризувати наступними параметрами: використовувані мікропроцесори: Intel Paragon - i860, IBM SP2 - PowerPC 604e або Power2 SC, CRAY T3D - DEC ALPHA; комунікаційна мережа: Intel Paragon - двовимірна прямокутна решітка, IBM SP2 - комутатор, CRAY T3D - тривимірний тор; організація пам'яті: Intel Paragon, IBM SP2, CRAY T3D - розподілена пам'ять; наявність або відсутність host-комп'ютера: Intel Paragon, IBM SP2 - ні, CRAY T3D - є.

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

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

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

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

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

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

1.2 Архітектура Red Storm

Red Storm являє собою архітектуру суперкомп'ютера, що була розроблена в США Департаментом Національної ядерной енергетики та Администрацією безпеки розширеного моделювання та обчислювальних програм . Cray. Inc розробили її на основі контракта архітектурних специфікацій, що надаються Sandia National Laboratories . Дана архітектура пізніше серійно випускалась як Cray XT3 .

Компанії Cray і AMD представили сьогодні на своїх сайтах прес-релізи про те, що національна лабораторія Департаменту енергетики США - Sandia National Laboratories, уклала з Cray $ 90 млн. контракт на постачання суперкомп'ютера на процесорах AMD Opteron.

Новий суперкомп'ютер класу Massively Parallel Processing (MPP), названий Red Storm, надійшов у продаж в 2004 році та містить приблизно 10 тисяч процесорів Opteron і дозволяє домогтися продуктивності рівня 40 трлн. операцій в секунду (40 TFLOPS). Для порівняння: найпотужніший з нині живих суперкомп'ютерів NEC Earth Simulator, має продуктивність 35,9 TFLOPS.

Контракт на поставку суперкомп'ютера Red Storm є частиною стратегічної ініціативи Accelerated Strategic Computing (ASC) Департаменту енергетики США. Серед інших завдань, новий суперкомп'ютер може використовуватися для моделювання фізичних процесів, що відбуваються при ядерних вибухах.

За словами представників Cray, процесори Opteron обрані для побудови Red Storm завдяки гарному поєднанню параметрів ціна / продуктивність. Контракт на поставку суперкомп'ютера Red Storm також включає в себе пункт про подальше нарощуванні продуктивності системи до 60 TFLOPS. Обрана для побудови Red Storm архітектура, за словами фахівців, масштабируема до продуктивності в сотні TFLOPS.

Продуктивність системи знаходиться на рівні 101,4 терафлопс, а пікова - 124,4. Це суттєвий прогрес в порівнянні з колишнім показником Red Storm, рівним 40 терафлопс.

Настільки вражаючий приріст продуктивності викликаний модернізацією, в результаті якої був доданий ще один ряд стійок, а загальна кількість процесорних ядер перевищила 26 тисяч. Суперкомп'ютер Red Storm встановив два світових рекорди в шести категоріях за результатами виконання набору тестів High Performance Computing Challenge (HPCC). Енергоспоживання суперкомп'ютера складає 2,2 МВт. Вартість його розробки і установки оцінюється в 77,5 млн. дол

Sandia і Cray розробляли суперкомп'ютер Red Storm спільно, в рамках проекту, фінансованого Національним агентством з ядерної безпеки США (National Nuclear Security Agency). Система Red Storm стала основою для комерційно доступного суперкомп'ютера Cray XT3. За даними розробників, архітектура Cray XT3 заснована на масовому паралелізм і включає високошвидкісний внутрішній зв'язок з тороїдальної топологією, дозволяє масштабувати систему від 200 до більш ніж 30000 процесорів. Масштабований процесорний елемент системи побудований на базі x86-сумісних 64-розрядних одно-або двоядерних процесорів AMD Opteron. Курйозна деталь: у певному сенсі прабатьком Red Storm можна вважати систему Sandia ASCI Red, побудовану Intel, і, за деякими даними, вона стала першим суперкомп'ютером у світі, що подолав позначку один терафлопс.

Раніше суперкомп'ютер Red Storm посідав шосте місце у світовому рейтингу, який визначається за допомогою тесту Linpack, дещо застарілого, але все ще широко використовуваного в галузі. Тести, за результатами яких Red Storm виявився першим, оцінюють ефективність роботи з оперативною пам'яттю і обміну даними між процесорами. На початку дев'яностих років минулого сторіччя, виробники суперкомп'ютерів оцінювали їх ефективність, вказуючи «теоретичну пікову продуктивність». Ця величина показувала, наскільки швидко зможе обробляти дані багатопроцесорний комп'ютер, якщо всі процесори будуть максимально завантажені. У кращому випадку такий показник можна було прийняти за орієнтовну оцінку.

На зміну теоретичної оцінці прийшов тест Linpack, який містив серію реальних, хоча і досить простих алгоритмів. Починаючи з 1993 року, кожні шість місяців стали публікуватися результати виконання тестів Linpack, які дозволяли визначити так званий «Top 500» - список найшвидших комп'ютерів світу. З часом, обмеження тесту Linpack ставали все більш помітні. Це підштовхнуло його розробників, лабораторію Innovative Computing Laboratory (ICL), що працюють в рамках університету штату Теннесі, до створення нового набору тестів, повніше відображає можливості сучасних суперкомп'ютерів, зокрема, враховує швидкість обміну даними між процесорами. Новий набір тестів, створений у співпраці з виробниками суперкомп'ютерів, отримав назву High Performance Computing Challenge (HPCC). Саме результати виконання цих тестів дозволили Red Storm зайняти два перші місця в світі в шести категоріях.

Red Storm на рисунку 1.3 використовується американцями для обчислень, пов'язаних з дослідженнями в області ядерної зброї.

Авторами архітектури суперкомп'ютера є Джим Томкинс (Jim Tomkins) і Білл Кемп (Bill Camp). Партнер лабораторії, компанія Cray, що отримала ліцензію на використання архітектури і операційної системи, поставила 15 аналогічних машин іншим американським державним установам і університетам, а також замовникам з Канади, Англії, Швейцарії та Японії.

Висновки за розділом

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

2. ПРОГРАМНА ЧАСТИНА

2.1 Аналіз поставленої задачі

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

Вхідними даними до розроблюваної програми є двовимірну матриця, що складає масив цілих чисел розміром Q у N рядках та М стовпцях, при чому заповнення матриці має відбуватися користувачем шляхом занесення до текстового файлу matrix цілих чисел у будь-якому діапазоні. Також до текстового файлу matrix1 користувач повинен занести розмір матриці.

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

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

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

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

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

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

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

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

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

2.4 Алгоритм роботи потоків

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

Таблиця 1. Алгоритм роботи потоків

При написанні програми було використано глобальні та локальні змінні. У програмуванні, глобальна змінна це -- змінна, яка доступна в будь-якій області видимості, за винятком перекриття її іншою змінною з тим самим ім'ям. Механізм взаємодій з глобальними змінними називається механізмом глобального середовища. Парадигма глобального середовища протиставляється парадигмі місцевого середовища, згідно з якою всі змінні місцеві без використання спільної пам'яті. Локальні змінні - змінні, визначені всередині підпрограми (функції). Вони доступні тільки всередині функції, в якій вони визначені. Імена, типи та призначення глобальних та локальних змінних, що використовуються у даній програмі, наведені в таблиці 2.

Таблиця 2. Імена , типи та призначення змінних

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

Таблиця 3. Список методів та їх призначення

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

Рисунок 1. Тестування програми

У текстовому файлі matrix.txt зберігається розмірність матриці та власне сама матриця. Тестовий файл знаходиться в тому ж каталозі, що й виконуваний файл програми.

Рисунок 2. Робочий каталог програми

Рисунок 3. Текстовий файл matrix.txt

Після введення кількості потоків та натискання клавіші Enter програма виконує розрахунок особистих чисел матирці та записує їх до файлу result_Х (Х - порядковий номер створюваного файлу). В робочому вікні відображається запис про те, в який файл було збережено особисті числа матриці та за який час у мілісекундах було виконано розрахунок. Також програма запитує користувача, чи бажає він повторити розрахунок для іншої кількості потоків. Для продовження потрібно натиснути клавішу У, для виходу з програми натиснути будь-яку іншу клавішу.

Рисунок 4.- Тестування програми

Після натиснення клавіші У на рабочому вікні відображаеться інформація про зчитування матриці з файлу та пропонується задати кількість потоків.

Рисунок 5. Тестування програми

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

Рисунок 6. Робочий каталог програми

Рисунок 7. Робочий каталог програми

Висновки за розділом

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

3. АНАЛІТИЧНА ЧАСТИНА

3.1 Аналіз роботи програми

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

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

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

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

Висновки за розділом

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

Размещено на Allbest.ru