Распараллеливание вычислительных алгоритмов

Введем в рассмотрение матрицу следования S, которой удобно представлять граф G. Поставим вершине (оператору) i в соответствие i-ю строку и i-й столбец матрицы.

Элемент (i, j) этой матрицы отметим знаком *, если существует связь по управлению (j=>i) и положим равным 1, если существует связь по информации (j i). Нулевые отроки матрицы S назовем ее входами в силу информационной независимости соответствующих им операторов.

Матрица следования для  граф-схемы рисунка 2 представлена на рисунке 3.

 

 

 

 

Рисунок 3 - Матрица следования S

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

Объединим связи по управлению и по информации в один вид связей между операторами, введя единое обозначение (– ) всех дуг в графе G.

Определение 8. Будем говорить, что между операторами γ и δ существует связь γ – δ, если существует одна из связей γ Þ δ или γ δ.

Переобозначим ненулевые  элементы матрицы S точками, т.е. · = *Ú1. Если существуют задающие связи b – g и g– d, но нет задающей связи b – d, то дополнение вычислительной схемы такими связями не меняет результата решения любой задачи оптимизации вычислительного процесса, так как лишь подтверждает недопустимость определенных комбинаций в порядке следования операций.

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

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

Алгоритм построение матрицы транзитивности

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

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

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

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

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

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

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

 

 

Рисунок 4 – Отражение связей между операторами в матрице S (Матрица транзитивных связей)

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

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

Связи 1Þ2, 1Þ4, 1Þ5 говорят о том, что операторы 2, 4, 5 не могут выполняться не только одновременно, но даже при одной реализации алгоритма: они логически несовместимы.

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

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

Алгоритм построения матрицы логической несовместимости операторов.

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

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

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

3 Если ранее уже  были зафиксированы элементы (i₁, j) = (i₂, j) = ... = (i_μ-1, j) =*, то полагаем, что в матрице L элементы (i_μ, i₁)=(i_μ, i₂)=…=(i_μ, i_μ-1)= (i₁, i_μ)=(i₂, i_μ)=…=(i_μ-1, i_μ)=1. Продолжим просмотр элементов столбца с шага 2.

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

На рисунке 5 показана матрица логической несовместимости операторов. Как видно, если оператор 2 логически несовместим с оператором 5, то операторы 3 и 6 также логически несовместимы, так как существуют связи 2 3 и 5 6. Эти операторы не могут выполняться при одной реализации алгоритма, т.е. при формировании плана параллельного выполнения алгоритма они не должны рассматриваться совместно.

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

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

 

 

Рисунок 5 – Матрицы  логической  несовместимости операторов

 

Таким образом, если оператор a логически несовместим с оператором β и существует связь a– g, то оператор g логически несовместим с оператором β только в том случае, если отсутствует связь β– g. Если же существуют связи a– g и  β– g, то оператор g логически несовместим с оператором d в том случае, если с ним логически несовместимы операторы a и β и если отсутствует связь d– g.

В общем случае при  решении вопроса о наличии  транзитивных связей логической несовместимости  данного оператора g необходимо выделить множество C_g = {a₁, ..., a_r} всех операторов, которые образуют связи    a_μ– γ, μ=1, …, r. Для этого предварительно необходимо ввести все транзитивные связи. Из данного множества должны быть исключены операторы-входы как не имеющие логически несовместимых операторов.

Для каждого оператора a_μ строится множество B_μ операторов, логически несовместимых с ним. Тогда формируется множество А_γ операторов, логически несовместимых с оператором g по формуле:

 

                   (2)

При этом учитываются  еще и задающие связи логической несовместимости, которые образует оператор g.

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

На рисунке 5 представлена матрица L^t логической несовместимости операторов с транзитивными связями для исследуемого алгоритма.

Матрица L логической несовместимости операторов, отражающая и транзитивные связи логической несовместимости, представляет информацию о том, могут или не могут конкретно взятые операторы выполняться при одной реализации алгоритма, т.е. при некотором наборе значений логических переменных. Матрица S, дополненная транзитивными связями, отражает ограничения на порядок выполнения операторов. Теперь поставим вопрос: можно ли для каждого оператора построить множество тех операторов (в состав которого входит и он сам), внутри которого имеет смысл решать задачу планирования одновременного независимого параллельного выполнения операторов? Для решения этого вопроса необходимо объединить информацию о логической несовместимости операторов и их информационно-логической связи.

Откажемся от свойства ориентированности  графа G, считая, что если существует связь a– b (задающая или транзитивная), то операторы a и b никогда не могут быть выполнены одновременно, параллельно. Достаточно считать, что в графе G существует неориентированная дуга, связывающая вершины a и β. В матрице следования S', соответствующей этому графу, положим (a, β) = (β, a) = 1. Иными словами, матрица S' получается из матрицы транзитивных связей S^t симметричным отображением ее элементов относительно главной диагонали или сложением матрицы S^t с ее транспонированной матрицей (с изменением обозначения ненулевых элементов).

На сформированную таким  образом матрицу S' наложим матрицу транзитивных связей логической несовместимости операторов L^t, сформировав значение каждого элемента по правилам дизъюнкции. Получим матрицу М, по нулевым элементам которой в строке каждого оператора можно указать множество тех операторов, каждый из которых при выполнении некоторых условий может быть выполнен одновременно с данным, т.е. он информационно или по управлению не зависит от данного оператора и не является с ним логически несовместимым.

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

Связь между двумя операторами a и b, отраженную в матрице независимости М, будем обозначать a ¾ b.

 

Рисунок 6 – Формирование матрицы независимости

 

2 Разработка программного  средства

 

2.1 Постановка задачи

 

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

1 Составить алгоритм ввода граф-схемы алгоритма (добавления и соединения вершин)

2 Составить алгоритм вычисления матрицы следования для введенной граф-схемы.

3 Составить алгоритм вычисления матрицы транзитивности для введенной граф-схемы.

4 Составить алгоритм вычисления матрицы транзитивных связей логической несовместимости для введенной граф-схемы.

5 Составить алгоритм вычисления матрицы независимости для введенной граф-схемы.

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

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

 

2.2 Спецификация основных процедур  и функций

 

Спецификация  основных процедур и функций представлена в таблице 1.

 

Таблица 1 – Спецификация процедур и функций

 

public int Vertex_size()	Возвращает число вершин в граф-схеме
public void DrawGraph(Graphics gr)	Функция отображения в PictureBox граф-схемы
public void AddVertex(Point P)	Добавление новой вершины в список вершин
public void FillMatrT()	Функция заполнения матрицы  транзитивности
public void FillMatrL()	Функция заполнения матрицы  логической несовместимости и дополнения ее связями транзитивной логической несовместимости
public void FillMatrN()	Функция заполнения матрицы  независимости операторов
public void GetMaxVNO()	Функция нахождения максимального  множества ВНО
public int FindFT()	Функция нахождения ранних сроков выполнения операторов
public void FindLtT(int MaxT)	Функция нахождения поздних  сроков выполнения операторов
public void Renum()	Функция перенумерования  вершин
public void MatrSwap(int x, int y)	Функция изменения матрицы  следования
public void VertexMouseClick(object sender, System.Windows.Forms.MouseEventArgs e)	Обработчик нажатия  кнопок мыши
public void VertexMouseUnclick(object sender, System.Windows.Forms.MouseEventArgs e)	Обработчик отпускания кнопок мыши
public void VertexMouseMove(object sender, System.Windows.Forms.MouseEventArgs e)	Обработчик перемещения  мыши