Лекции по дисциплине «Теория вычислительных процессов» (стр. 10 )

Информационно-логический граф-схема алгоритма имеет вид (G(X, P,Г))

При составлении этой схемы будем руководствоваться действительной зависимостью между операторами обусловленной ветвлением или преемственностью информации. При этом могут быть критически пересмотрены связи присутствующие в исходном описании алгоритма. Так оператор 7 не обязательно должен следовать операторам 6 и 8 хотя при написании алгоритма использованы соответствующие стрелки. Однако при уточнении зависимости между указанными операторами необходимо учесть, что оператор 10 использует выходную информацию оператора 6 оператор 7 – выходную информацию операторов 3 и 4 и т. д..

Множество X-{i}={1..m} вершин графа G соответствует множеству операторов алгоритма при тех же обозначениях. Множество P={ ti } весов вершин определяет время выполнения каждого оператора соответствующего вершине. В рассматриваемом примере считаем, что ВС содержит три типа процессоров. Множество дуг Г состоит из дуг двух типов: Г= Г1 U Г2 где Г1 – множество дуг определяющих связи между операторами по управлению Г2 – мн6ожество дуг определяющих связи между операторами по информации.

Опр. 1 Будем говорить что между операторами g и d существует дуга UÎГ1 исходящая из вершины gÎX и входящая в вершину dÎX.

Опр. 2. Будем говорить что между операторами g и d существует связь по информации g à d если в графе G существует дуга UÎГ2 исходящая из вершины gÎX и входящая в вершину dÎX.

Опр. 3. Назовем все связи по управлению и по информации между операторами обусловленные исходным видом графа G задающими связями. Каждая связь по управлению одновременно является связью по информации т. к. Ею определяется строгий порядок следования операторов задаваемый выходной информацией логического оператора – значением логической переменной.

Опр. 4. Путями в графе G будем называть последовательности вершин вида К1, К2,...Кs также что для любой пары соседних вершин Кi и Ki+1 существует дуга UÎ Г1 U Г2 исходящая из вершины Кi и входящая в вершину Кi+1 .

Ограничение: Будем считать все пути в графе G допустимыми. Это означает что для каждого пути в графе G существует или могут быть получены динамически в процессе счета значения всех логических переменных при которых будут выполнены операторы образующие данный путь.

Опр. 5. Длинной пути в информационно-логическом графе со скалярными весами вершин назовем сумму весов вершин составляющих этот путь.

Опр. 6. Путь максимальной длинны Ткр в ИЛГ со скалярными весами вершин назовем критический. В одном графе может быть несколько путей равной длины являющихся критическими.

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

Одним из возможных решений в таком случае является следующее. Логический оператор вырабатывает значения примитивов синхронизации вычислительного процесса, например, семафоров. Выполнение же операторов-преемников ставится в зависимость от значения определенных примитивов синхронизации. Использование примитивов синхронизации позволяет практически снять ограничение на допустимость всех путей в графе G.

Введем в рассмотрение матрицу следования S, которой удобно представлять граф G. Поставим вершине i в соответствие i-ю строку и i-столбец матрицы. Элемент (i, j) этой матрицы отметим знаком *, силу существует связь по управлению и положим равным 1, силу существует связь по информации. Для отражения весов дополним матрицу S к столбцами - по числу типов процессоров в ВС. В каждой строке этих столбцов запишем компоненты веса соответствующей вершины, равные времени выполнения оператора процессорами соответствующего типа. Нулевые строки матрицы S назовем ее входами в силу информационной независимости соответствующих им операторов.

Опр. 7. Будем говорить, что между операторами J и d, существует связь J - ® d, если существует одна из связей JÞd.

Опр. 8. Множество связей, которые введены направленно внутри всех пар операторов, принадлежащих одному пути в графе G и не связанных задающими связями, назовем множеством транзитивных связей. Транзитивные связи полностью определяются задающими связями.

Рассмотрим, какие преобразования над матрицей S соответствуют введению множества транзитивных связей. Если существует связь a - ® b, то все связи вида Jм - ® a, где {jм} - множество операторов, образующих такие связи, должны быть отнесены и к оператору b. Это означает, что каждый новый элемент строки b должен быть сформулирован по правилу дизъюнкции, выполняемой над старым элементом и элементом, который находится в этом же столбце строки a.

1 233

2 * 368

3 * 113

4 * 218

5 * 422

6 1 588

7 1 1 111

8 1 111

9 * * 225

10 1* 322

1 2 3 4 5 6 7 8 9

Алгоритм 1.

1. Организуем просмотр сверху вниз строк матрицы S.

2. В очередной строке i организуем просмотр элементов в порядке увеличения номеров столбцов.

3. Если (v, j)=q, складываем строки i и j по операции дизъюнкции.

4. Если исходная матрицы S не треугольная, просмотр строк матрицы S производится неоднократно до установления факта неизменности окончательно полученной матрицы.

Неоднократный просмотр матрицы S, если она не треугольная, обусловлен тем, что, если ненулевой элемент в i-й строке занимает позицию j>i, мы складываем с i-й строкой j-ю строку, которая следует ниже и сама еще не обработана. Следовательно, после ее уточнения необходимо уточнить и строку i. В треугольной матрице следования ненулевые элементы всегда занимают позиции j<i. При этом достаточно одного просмотра строк.

1

2 ·

3 ·

4 ·

5 · ·

6 · ·

7 · ·

8 · ·

9 · · · · ·

10 · · · · ·

1 2 3 4 5 6 7 8 9 10

С помощью транзитивных связей устанавливается факт наличия контура в информационно-логическом графе. О наличии контуров свидетельствуют ненулевые диагональные элементы.

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

Введем в рассмотрение матрицу L логической совместимости операторов. Первоначально введем задающие связи логической несовместимости операторов по следующему алгоритму:

1. Организуем последовательный просмотр столбцов j=1...m матрицы S.

2. Образуем просмотр элементов в j-м столбце. При просмотре j-го столбца находим очередной элемент (iм, j)=*.

3. Если данный элемент - первый в данном столбце, имеющие такое значение (М=1), запоминаем его и продолжаем перебор элементов столбца с шага 2.

4. Если ранее уже были зафиксированы элементы (i1, j)=(i2, j)=...=(iм-1, j)=*, полагаем, то в матрице L (iм, i1)=(iм, i2)...(iм, iм-1)=(i1, iм)=(i2, im)=...=(iм-1, iм)=1.

Продолжим просмотр элементов столбца с шага 2.

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

Опр. 11. Операторы a и b будем называть взаимно-независимыми операторами (ВНО), если в матрице независимости М(a, b)=(b, a)=0.

Опр. 12. Операторы {a} i=1...S, образуют полное множество ВНО, если для любого оператора jÏ{a} существует пара элементов матрицы независимости М (ai, j)=(J, a1)=1 iÎ{1i...S}

При решении задач распараллеливания необходимо перебирать все возможные полные множества ВНО, а также находить то, которое имеет максимальное число операторов - максимальное полное множество ВНО. Для построения алгоритма его нахождения примем во внимание следующее: если два оператора

4. Формируем множество Д=ВUi и находим по правилу дизъюнкции сумму строк Е=СV{i, 1)... (i, m)}.

5. Анализируем, содержит ли строка Е нулевые элементы во всех позиция, соответствующих операторам из Д. При данном анализе попутно устанавливаем факт наличия нулевых операторов из Д. Если в сборке Е нет нулевых элементов, соответствующих всех операторам из Д, переходим к шагу 8, в противном случае, выполняем следующий шаг.

6. Формируем новые значения В=Д, С=Е.

7. Если в строке кроме Е кроме нулевых элементов, соответствующих операторам из Д, существуют другие нулевые элементы, выполняем шаг 8. В противном случае оказывается найденным полное множество ВНОА=В. Здесь может быть произведен выход из алгоритма, если необходимо найти очередное полное множество ВНО.

8. Если i=m, присваиваем новое значение i=it и выполняем алгоритм с шага 4; в противном случае выполняем следующий шаг.

9. Анализируем, превышает ли число r элементов множества В значение d? Если превышает, полагаем А=В, d=r.

10. Сравниваем в обратном порядке элементы множества В={i1,...ir} и множества всех операторов {1...m}, т. е. выполняем сравнения ir=m, ir-1=m-1 и т. д. Есди при переборе всех элементов В отсутствует несовпадение выполнение алгоритма заканчивается, множество А является максимальным полным подмножеством ВНО.

11. Если найдено первое из несовпадений ir-р=m-p, исключаем из В операторы ir-h...ir.

12. Формируем значение С, равное сумму строк матрицы М, соответствующих операторам из множества В:

r-p-g

С=V{ig, 1)...(ig, m)}

g=1

13. Полагаем i=irp+1. Продолжаем выполнение алгоритма с шага 4.

14. Повторный вход в данный алгоритм для поиска следующего полного множества производится на шаге 10.

15. Если в результате работы данного алгоритма необходимо найти максимальное полное множество ВНО, то после шага 7 выполняется шаг 9.

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