АЛГОРИТМЫ ПОСТРОЕНИЯ РАННИХ И ПОЗДНИХ СРОКОВ ОКОНЧАНИЯ ВЫПОЛНЕНИЯ ОПЕРАТОРОВ.

Рассмотрим алгоритм, представляемый информационным гра­фом (без связей по управлению), не имеющим контуров. Тогда оче­видно, что момент окончания выполнения любого из операторов не может быть меньше максимальной из длин всех путей, заканчива­ющихся вершиной, соответствующей этому оператору. Таким обра­зом, для каждого оператора алгоритма j = 1,..., т. можно найти ранний срок окончания его выполнения.

Если окончание выполнения алгоритма ограничено временем , то для каждого оператора можно найти и поздний срок окончания его выполнения (Т). Здесь Т_КР — максимальная ха­рактеристика пути в графе со скалярными весами, она определяет минимальное время, за которое может быть решена данная задача.

Окончание выполнения любого оператора позже этого позднего срока приводит к тому, что все последующие за ним операторы не смогут быть выполнены в заданный срок Т, поэтому без задания Т определение поздних сроков не имеет смысла. При Т = Т_кр ранние и поздние сроки выполнения операторов, входящие в критический путь, совпадают.

Алгоритм. Нахождение ранних сроков окончания выполне­ния операторов.

1.Положим где .

2.Просмотрим строки матрицы S сверху вниз, выберем первую необработанную строку матрицы и осуществим переход к следую­щему шагу. Если обработаны все строки, то конец алгоритма,

3.Пусть выбрана j-я строка, не содержащая единичных элемен­тов. Далее вычислим где — вес j-гo оператора, затем выполним переход к шагу 5.

4.Если j-я строка содержит единичные элементы, то вычислим где есть множество времен, которым соответствует единица в данной строке. Затем выполним переход на шаг 5. Если во множестве есть нулевые элементы, то вы­полним шаг 6.

5.Обработанную j-ю строку исключим из рассмотрения и осу­ществим переход к шагу 2.

6.Если найдена строка , для которой , то вычислим строку j= , и осуществим переход к шагу 3.

Конец алгоритма.

Примечание. Пункт 6 используется для нетреугольной матрицы S.

Алгоритм. Получение поздних сроков окончания выполне­ния операторов.

1. Положим где ..

2. Просмотрим столбцы матрицы S справа налево, выберем пер­вый необработанный столбец матрицы и произведем переход к сле­дующему шагу. Если обработаны все столбцы, то конец алгоритма.

3. Пусть j — номер очередного необработанного столбца. Если он не содержит единичных элементов, то вычислим (Т)= Т, где Т — время решения задачи, и перейдем к шагу 5.

4. Если столбец j содержит единичные элементы, то вычислим ,т.е. минимум определим по всем j_v еди­ничным элементам j-гo столбца. Если , то выполним шаг 6.

5. Обработанный j-й столбец исключим из рассмотрения, затем выполним шаг 2.

6. Если найден столбец j_v, для которого , то проведем поиск необработанного столбца j_v, вычислим j = j_v и выполним переход к шагу 3.

Конец алгоритма.

Примечание. Пункт 6 используется для нетреугольной матрицы 3.

Диаграммы выполнения операторов для ранних и поздних сро­ков — удобный способ наглядного представления многопроцессор­ной обработки. Всего в диаграмме имеется п строк, соответству­ющих числу процессоров в системе. Выполнение того или иного оператора отмечается прямоугольниками, имеющими длину, рав­ную весам операторов, и правую границу, соответствующую край­нему сроку окончания выполнения операторов.