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

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

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

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

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

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. Связность алгоритма (количество промежуточных результатов, которое необходимо хранить в процессе реализации алгоритма) – С.