Определение ранних сроков окончания выполнения операторов

При исследовании граф-схем алгоритмов одними из основных характеристик являются ранние сроки окончания выполнения операторов. Имея эти величины, можно построить планы выполнения операторов с учётом распределения операторов по ВМ. На основе граф-схемы алгоритма можно определить:

1) Частичную упорядоченность выполнения алгоритма.

2) Веса операторов pj, j = 1, …, m (обычно – времена выполнения процедур).

Началом отсчёта времени решения задачи является начало выполнения операторов, являющихся входами в алгоритм. Тк – это путь максимальной длины в граф-схеме (максимальное время, за которое может быть решена данная задача).

Ранний срок окончания выполнения оператора – это время на оси отсчёта времени, равное t1, j = , j = 1...m, где – время начала выполнения j-ого оператора, p_j – время выполнения j-ого оператора, полученное при минимальном времени решения задачи Т=Тк.

По алгоритму, приведенному в Приложении 2, определим ранние сроки окончания выполнения операторов и построим диаграмму (рисунок 4).

Каждая строка диаграммы может служить нитью для загрузки в процессор. Таким образом получим 9 нитей:

T1={2, 5, 6, 15, 26, 34, 46}

T2={1, 7, 27, 35, 45}

T3={3, 8, 16, 22, 31, 36, 47, 44}

T4={4, 9, 17, 28, 37, 48}

T5={10, 19, 29, 38, 43}

T6={11, 20, 18, 42}

T7={12, 21, 30, 24, 41}

T8={13, 23, 32, 40}

T9={14, 25, 33, 39, 49}

Tак как рассматривается ВС с общей памятью, обмена данными через каналы связи между процессорами нет, и количество нитей меньше, чем число процессоров, поэтому распределение нитей между ВМ может осуществляться, например, следующим образом: первая нить загружается в первый ВМ, вторая – во второй и т. д.

Учёт времён передачи информации осуществляется, используя следующие соотношения: для развёртки – p_,j=q_i,j+p_j, где j= – номера операторов, образующих развёртку; для свёртки – p_j= q_j,i +p_j где j= – номера операторов, образующих cвёртку. С помощью матрицы следования с указанными весами дуг и вершин модифицированные веса вершин можно вычислить следующим образом: если в i-й строке найдено одно число, то вес i-й вершины модифицируется к виду: р_i:=p_i+q_ji;если в i-й строке найдено несколько чисел, то веса вершин модифицируются к виду р_j:=p_j+q_i,j, j={ }, где j – номера столбцов, в которых найдены числа, q_i,j – множество весов дуг, принадлежащихi-й строке.

В таблице 3 приведены ранние сроки окончания выполнения операторов.

Таблица 3- Ранние сроки окончания выполнения операторов

№

T

№

Т

№

T

Рисунок 4 - Диаграмма ранних сроков окончания выполнения операторов

Паузы, возникшие по окончанию 12, 15, 20, 21, 22 единиц времени, обусловлены синхронизацией вычислений, определяемой структурой рассматриваемой граф-схемы. Общее время выполнения алгоритма составляет 26 условных единиц времени.

Этот способ графического представления плана выполнения алгоритма на ВС позволяет в максимальной степени компактно распределить параллельные операторы по узлам ВС. Это позволяет обеспечить экономию времени при выполнении задач. Как видим, при таком раскладе наиболее продолжительный по времени последовательный путь в ИЛГ незначительно выдаётся за пределы компактного распределения интервалов работы операторов основного тела ИЛГ.

При построении временных диаграмм выполнения операторов необходимо учитывать, что они строятся для информационно-логической граф-схемы, и не все операторы будут выполнены. Это можно сделать, например, с помощью динамического плана, состояние которого изменяется каждый раз, как только выполняется очередной логический оператор. То есть для каждой возможной цепи выполнения операторов предусматривается своя временная диаграмма. Для рассматриваемой граф-схемы временные диаграммы будут выглядеть так, как показано на рисунках 5-14.

Рисунок 5 - Временная диаграмма при срабатывании дуги 5.1

Рисунок 6 - Временная диаграмма при срабатывании дуги 5.2

Рисунок 7 - Временная диаграмма при срабатывании дуги 5.3

Рисунок 8 - Временная диаграмма при срабатывании дуги 5.4

Рисунок 9 - Временная диаграмма при срабатывании дуги 5.5 и 10.1

Рисунок 10 - Временная диаграмма при срабатывании дуги 5.5 и 10.2

Рисунок 11 - Временная диаграмма при срабатывании дуги 5.6

Рисунок 12 - Временная диаграмма при срабатывании дуги 5.7

Рисунок 13 - Временная диаграмма при срабатывании дуги 5.8

Рисунок 14 - Временная диаграмма при срабатывании дуги 5.9

Как видно из рисунка 14, максимальное число нитей для данного алгоритма равно 7. Полная временна диаграмма свидетельствует о наличии 9 таких нитей.

Дата добавления: 2015-11-14