о програм і даних представляє широкі можливості організації паралельного обчислювального процесу (паралельних обчислень) . Відсутні втрати реальної продуктивності на міжпроцесорний (між завданнями, процесами і т.д.) обмін даними (рис.3)
В
Рисунок 3 - Обчислювальна система з загальною пам'яттю
В
Рисунок 4 - Граф-схема паралельного алгоритму
2.1 Побудова матриці прямування ІЛГ
Основним інструментом аналізу граф-схем алгоритмів служить матриця прямування, а також різні її модифікації. Матриця прямування - це транспонована матриця суміжності. Використання матриці прямування замість матриць суміжності пояснюється зручністю розміщення та аналізу граф-схем. p> Для зручності привласнимо постійний ідентифікатор - Si i {1, 2. ..., N}. Матриця S - квадратна - кількість рядків і стовпців збігається з кількістю вершин граф-cхема. У матриця S i - ой вершині графа G ставляться у відповідність i - ті стовпець і рядок цієї матриці. Якщо існує зв'язок з управління:, то елемент матриці дорівнює (i, j) = jn, при j? i утворюється (i, j) = 1. Інші елементи матриці S рівні 0. p> Для заданої матриці Si розміру m відображення ваг вершин вводиться поняття розширеної матриці прямування SRi: додається додатково k стовпців з номерами m +1, ..., m + k, де k - розмірність вектора ваг вершин граф - схеми. p> Побудуємо розширені матриці прямування для нашої граф - схеми. (Таблиця 1 Додаток 4.1). p> Побудуємо матрицю прямування із зазначенням ваг дуг і вершин (SDR) для даної ІЛГ (Таблиця 2 Додаток 4.2).
2.2 Визначення ранніх термінів закінчення виконання операторів
При дослідженні граф-схем алгоритмів одними з основних характеристик є ранні терміни закінчення виконання операторів. Маючи ці величини, можна побудувати плани виконання операторів з урахуванням розподілу операторів по ВМ. Необхідно підкреслити, що на основі граф-схеми алгоритму, можна визначити:
) Часткову впорядкованість виконання алгоритму.
) Веса операторів pj, j = 1, ..., m (зазвичай - часи виконання процедур).
) Початком відліку часу рішення задачі є початок виконання операторів, які є входами в алгоритм.
) Тк - це шлях максимальної довжини в граф-схемі (це максимальний час, за який може бути вирішена дана задача).
Ранній термін закінчення виконання оператора - це час на осі відліку часу, рівне t1, j =, j = 1. . . M, де - час початку виконання j-ого оператора, pj - час виконання j-ого оператора, отримане при мінімальному часу рішення задачі Т = Тк. p> Кожен рядок діаграми може служити ниткою для завантаження в процесор. Таким чином, вийшло 7 ниток:
ак як розглядається НД із з...
