Информатика и выч. техника \ Параллельное программирование

Параллельное программирование: Учебное пособие, страница 31

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

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

2.3.6  Поиск границ допустимых перемещений процессов

Сначала рассмотрим методику поиска самых ранних сроков окончания вершинных процессов, не нарушая при этом порядка встречи вершин на множестве путей по дугам графа. Для этого удобно использовать отсортированную по новым индексам вершин таблицу 2, в которую добавлен столбец веса вершин t в относительных единицах времени, столбец для занесения ранних сроков окончания процессов и столбец для занесения поздних сроков окончания вершинных процессов.

На рисунке 2.14 приведена схема алгоритма для вычисления ранних сроков окончания каждого вершинного процесса. Ранние сроки окончания каждого вершинного процесса будут заноситься в колонку таблицы 2, представленной в алгоритме предварительно обнуленным одномерным массивом  . Индекс  перечисляет столбцы упорядоченной матрицы смежности  графа информационной зависимости (ГИЗ), а в таблице 2 (колонка отрицательных полустепеней ) – указывает на подмножество вершин, находящихся на -тых строках -го столбца матрицы . Значение элемента  равно либо 1, либо 0. Алгоритм работает до тех пор, пока на всех позициях колонки ранних сроков окончания вершинных процессов не исчезнут все предварительно записанные нулевые значения. Вычисление конкретного значения раннего срока окончания -го вершинного процесса осуществляется по формуле:

,                                                     (2.28)

где      ранние сроки окончания процессов -тых вершин, для которых одновременно выполнено условие, что на -той строке -го столбца матрицы смежности  находится единица и для -той строки колонки  таблицы 2 ранний срок окончания уже найден. К наибольшему из -тых добавляется время выполнения -го процесса.

Значения ранних сроков окончания процессов определяют минимально возможное время готовности данных для продолжения вычислений смежными процессами.

Таблица 2. – Ранние и поздние сроки окончания выполнения операторов.

Индекс

k

Исходное имя

Вес

t

Ярус

j

1

a

{b,с,е}

{Æ}

2

1

2

2

2

d

{e,g}

{Æ}

1

1

1

4

3

b

{f,s}

{a}

3

2

5

5

4

c

{f}

{a}

4

2

6

12

5

e

{h}

{a,d}

2

2

4

6

6

f

{v}

{b,c}

3

3

9

15

7

s

{h,v}

{b}

1

3

6

6

8

h

{g, w}

{e,s}

4

4

10

10

9

g

{v}

{d,h}

5

5

15

15

10

w

{v}

{h}

2

5

12

15

11

v

{Æ}

{f,g,s,w}

3

6

18

18

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

Скачать файл