Модель обчислень 1

Модель обчислень. Система FLOWer базується на моделі управління потоком даних.

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

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

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

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

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

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

Це дозволяє налаштовувати програму під конкретні вимоги користувача. Для запису шаблону ГПД була розроблена спеціальна мова DGL Dataflow Graph Language. Більш докладно про DGL можна прочитати в розділі Мова DGL. Шаблон ГПД це орієнтований граф, вершинами якого є класи процесів, а дугами канали, і набір параметрів.

Кожному класу процесу зіставлений номер. Параметри вектор змінних. Канал визначає односпрямований потік даних між процесами, він завжди спрямований від входу до виходу. Клас процесу структура даних, що складається з набору входів і виходів. Входи і виходи пронумеровані. Вхід може бути позначений як обов'язковий. Введемо систему позначень. TG TP, TC, A шаблон ГПД, де TP безліч шаблонів процесу, TC безліч шаблонів каналу, A вектор параметрів.

Ai i-й параметр ціле число. TPi i-й процес. In TPi безліч входів процесу i. In k TPi k-й вхід процесу i. Out TPi безліч виходів процесу i. Out k TPi k-й вихід процесу i. Нехай X TPi. Тоді X.ncopies ncopies A целочисленная функція від параметрів, яка задає число копій процесу X. Нехай X Out k TPi. Тоді X.ncopies ncopies p, A целочисленная функція, яка задає число копій виходу X. Тут p ціле число, А параметри.

В цьому випадку N визначається під час запуску програми.

Надалі планується ввести в мову багатовимірні масиви процесів, а так само додати умовні оператори ifthenelse і caseof.

Це дозволить описувати більш складні ГПД, зокрема, багатовимірні решітки.

Синтаксис DGL DATAFLOW PROGRAM name EXTERN name integer CONST name expression process process PROCESS name numberofinstances directive processattr EXPORT export IMPORT import directive LOCAL START TERMINATION processattr weight integer import name importattr importattr export name numberofinstances processname processindex importname exportattr exportattr numberofinstances expression processindex expression importattr ARGUMENT exportattr DATASIZE integer Г Л а В а 4 пРИКЛАД паралельної програми як приклад розглянемо задачу наближеного обчислення числа Пі з використанням правила прямокутників для обчислення певного інтеграла де Згідно з правилом прямокутників, де, а. Слід зазначити, що це процесорна програма.

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

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

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

Кожній вершині ГПД відповідає процес DGL з тим же ім'ям. Тепер намалюємо ГПД за допомогою програми Rose і запишемо його на диск у форматі DGL. DATAFLOW PROGRAM PI EXTERN NProcs 5 CONST nw MAX 1, NProcs - 2 PROCESS Summer 1 LOCAL IMPORT NumIter PartSum PROCESS Worker nw EXPORT PartSum 1 Summator 0 PartSum DATASIZE 0 Demand 1 Manager 0 DemandList DATASIZE 0 IMPORT Arg PROCESS Manager 1 LOCAL START TERMINATION EXPORT Done 1 Summator 0 DoneSignal DATASIZE 0 Worker nw Worker c Arg DATASIZE 0 IMPORT DemandList 4.3. Компіляція процесів Після того, як ГПД записаний на мові DGL, його потрібно обробити транслятором dglc. В результаті роботи транслятора на диску повинні з'явитися такі файли PI.dpr, Manager.pas, ManagerBody.pas, Worker.pas, WorkerBody.pas, Summator.pas, SummatorBody.pas. Далі, програміст записує код кожного процесу в файлах SummatorBody.pas, WorkerBody.pas, ManagerBody.pas, а потім компілює проектний файл PI.dpr. Ч А С Т Ь 2 РЕАЛІЗАЦІЯ ДЕЯКИХ АЛГОРИТМІВ ВЛА В СИСТЕМІ FLOWer У цій частині розглядається реалізація в системі програмування FLOWer деяких алгоритмів ВЛА, в число яких входять множення матриць, LU-розкладання, рішення трикутних слу, QR-розкладання, ітераційні методи рішення слу. Для кожного алгоритму наводяться теоретичні оцінки прискорення, опис паралельного алгоритму, експериментальні дані.

Для проведення експериментів використовувалася локальна мережа FastEthernet, що складається з 4-х комп'ютерів Pentium II 333MHz. Г Л А В А 1 Множення матриць Розглянемо задачу обчислення творів Ax і AB, де А і В матриці, а х вектор.

Окремо будуть розглянуті стрічкові і блочно-діагональні матриці. 1.1.