Ярусно-параллельная форма алгоритма

План

Параллельная обработка данных

1. Ярусно-параллельная форма алгоритма.

2. Автоматическое обнаружение параллелизма.

3. Степень и уровни параллелизма.

4. Виды параллелизма.

5. Модель задачи.

Параллелизм – это возможность одновременного выполнения нескольких арифметических, логических или служебных операций. Причем операции могут быть как крупноблочные, так и мелкоблочные.

В основу параллельной обработки могут быть положены различные принципы:

- пространственный параллелизм;

- временной параллелизм:

a) Конвейеризация.

b) Векторизация.

c) Матричный.

d) Систолический.

e) Организация структуры обработки потока данных.

f) Организация системы на основе структуры гиперкуб.

g) Динамическая перестройка структуры ВС.

Описание любого алгоритма является иерархическим, основанным на свойстве вложенности. При программировании выделяют уровни вложенности: задания, задачи, подзадачи (процессы), макрооперации, операции.

 

Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).

Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

На графе можно обозначить переходы, означающие передачу результатов вычисления примитивной операции из одного яруса к операции из следующего яруса. Ярусы делятся по переходам. Могут быть «пустые» переходы и «пустые» примитивные операции.

При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами:

1. Длина графа (количество ярусов) – L.

2. Ширина i-го яруса - b_i.

3. Ширина графа ярусно-параллельной формы – B=max(b_i).

4. Средняя ширина графа ЯПФ – В_ср – .

5. Коэффициент заполнения i-го яруса – k_i – .

6. Коэффициент разброса операций в графе - Q^j_i – , jÎБНО, где - количество j-го типа операций в i-м ярусе.

7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Т_min.

9. Связность алгоритма (количество промежуточных результатов, которое необходимо хранить в процессе реализации алгоритма) – С.