Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре (стр. 3 из 4)

1. Просматриваем множество нитей Т, выберем к-ю нить с максимальным количеством элементов в множестве

(таблице связей к-й нити). Предположим таблица связей имеет элементов.

2. Если степень i-й вершины вычислительной сети есть

, то сравниваем и .

3. Если

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

4. Если

то образуется комплексный узел, в котором один вычислитель основной, остальные являются передающими звеньями. Полагаем f: =1 и переходим к следующему шагу.

5. Определяем

где Т множество нитей.

6. Если

, то переход на шаг 10.

7. Нить

занимает узел вычислительной сети на минимально возможном расстоянии от узла i. Все вершины из окружения нити Ti, принадлежащие множеству удаляются из узлов, соседних с узлом I, т.е.

8. В соседних узлах с узлом

размещаются элементы таблицы . Если количество узлов с минимальным расстоянием недостаточно, то организуются комплексные узлы, как пункте 4.

9. Если

то вычисляется f: =f+1 и переход на шаг 5. Иначе полагаем и переход на шаг 5.

10. Вычисляем узел х, удовлетворяющий соотношению

, где - количество свободных связей у рассматриваемых узлов. f=1,…f `, затем полагаем i: =x, T: =T\Tк. Если , то переходим к шагу 1, иначе конец алгоритма.

5. Описание интерфейса программы

Интерфейс разработанной программы состоит из одного окна, содержащих несколько вкладок:

1. Вкладка генерации информационного графа алгоритма и результатов выполнения разбиения алгоритма на нити. (рис.2).

Рис.2. Вкладка управления работой программы

На вкладке можно осуществить генерацию ИЛГ, выбрать метод преобразования ИЛГ в ИГ и задать режим визуализации (какие построения необходимо визуализировать).

2. Вкладка вывода информационного графа, заданного матрицей следования (рис.3).

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

В матрице следования в столбцах задаются все выходящие из данной вершины связи, а в строках - все входящие в заданную вершину связи. При этом задаваемое значение 1 означает, что связь между операторами есть, если связь пронумерована с буквами ‘T’ или ‘F’, то это соответствующая логическая связь. Если связи между вершинами нет, то позиция не заполняется.

Поскольку ИЛГ по заданию не должен содержать циклов, то данные можно вводить только ниже главной диагонали матрицы следования.

Рис.3 - Окно вывода информационного графа.

3. Окно вывода информационного графа, заданного матрицей следования (рис.4).

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

Рис.4 - Вкладка вывода ИЛГ.

4. Временные диаграммы распределения нитей по процессорам (рис.4).

Здесь указывается, какой нити принадлежит оператор, и в какие сроки он выполняется.

Рис.4. Временные диаграммы нитей.

5. Вкладка распределения нитей по процессорам. Содержит описание структуры ВС с указанием, какой процессор выполняет какую нить, какой является транзитным и какой свободен. (рис.5)

Рис.5. Окно вывода результатов

6. Результаты работы программы

На рисунке 6 показана сгенерированная матрица следования S.

Рис.6. Сгенерированная матрица следования S

На рисунке 7 показан построенный программой по указанной в задании матрице S ИЛГ задачи.

Рис.7. ИЛГ задачи.

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

Логические связи считаются связями по данным.

Для начала рассмотрим случай, когда логические связи в ИЛГ считаются связями по данным, то есть рассмотрим ИЛГ как ИГ, заменив логические связи на связи по данным. Получаем размещение операторов по нитям (в виде перечисления и графа алгоритма), временные диаграммы, и размещение нитей по процессорам (соответственно рис 8,9,10,11).

Рис.8. Размещение операторов по нитям при рассмотрении ИЛГ как ИГ (перечисление).

Рис.9. Размещение операторов по нитям при рассмотрении ИЛГ как ИГ (граф алгоритма).

Рис.10. Временные диаграммы при рассмотрении ИЛГ как ИГ (граф алгоритма).

Рис.11. Распределение нитей по ВС при рассмотрении ИЛГ как ИГ (граф алгоритма)

Как видно из рисунков, ВС имеет структуру гипертора 1*3*3, в которой задействовано 5 процессоров, а 4 являются транзитными. Полное время решения задачи при таком подходе составляет 93 временных единицы. Неэффективное использование процессоров в ВС (соотношение рабочих процессоров и транзитных примерно 1:

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

Задействованы логические связи 23T, 24T, 27F.

Рассмотрим преобразование ИЛГ в ИГ, когда у нас известны значения логических операторов, например, 23T, 24T, 27F. На основании этих данных можно исключить из планирования те операторы, которые не будут выполняться. После этого можно осуществлять планирование выполнения алгоритма.

Результаты приведены на рисунках 12-15.

Рис.12. Размещение операторов по нитям при ИЛГ 23T, 24T, 27F.

Рис.13. Размещение операторов по нитям при ИЛГ 23T, 24T, 27F.

Рис.14. Временные диаграммы при рассмотрении при ИЛГ 23T, 24T, 27F.

Рис.15. Распределение нитей по ВС при ИЛГ 23T, 24T, 27F.

Анализируя рис 11-15, получаем, что при преобразовании ИЛГ в ИГ часть операторов (30,31,32,33,36,37,38) была исключена из рассмотрения, что повлияло на ход выполнения планировки задания.

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

Задействованы логические связи 23F, 24F, 27F.

Рассмотрим преобразование ИЛГ в ИГ, когда у нас известны значения логических операторов, например, 23F, 24F, 27F. На основании этих данных можно исключить из планирования те операторы, которые не будут выполняться.

После этого можно осуществлять планирование выполнения алгоритма.

Результаты приведены на рисунках 16-19.

Рис.16. Размещение операторов по нитям при ИЛГ 23F, 24F, 27F.

Рис.17. Размещение операторов по нитям при ИЛГ 23F, 24F, 27F.