Xreferat.com » Рефераты по информатике и программированию » Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре

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

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


4.3 Алгоритм уплотнения нитей


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

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

Найдем такой Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуречто для соседних нитей, размещаемых на интервале [0,T], после вычислений по соотношения (1) выполняется условие, что время окончания предшествующей нити должно быть меньше или равно времени начала последующей нити.

Если нити, удовлетворяющие условию (1) найдены, то соответствующие Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуреи Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре удаляются и записываются в множество Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре в виде составной к-й нити. Объединяются множества таблиц связей в виде Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структурегде I - число нитей, вошедших в составную нить.

Если Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре=0, то работа алгоритма заканчивается, иначе осуществляется переход к п.3.

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


4.4 Алгоритм распределения вершин графа решаемой задачи на узлах вычислительной сети с одинаковой степенью вершин


Предполагаем, что количество узлов вычислительной сети неограниченно и множество нитей Т получено с помощью алгоритма 4.2.

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

Если степень i-й вершины вычислительной сети есть Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре, то сравниваем Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре и Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре.

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

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

Определяем Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуреВыполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структурегде Т множество нитей.

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

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

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

Если Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре то вычисляется f: =f+1 и переход на шаг 5. Иначе полагаем Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуреи переход на шаг 5.

Вычисляем узел х, удовлетворяющий соотношению Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре, где Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре - количество свободных связей у рассматриваемых узлов. f=1,…f `, затем полагаем i: =x, T: =TTк. Если Выполнение планирования вычислений алгоритма на однородной вычислительной сети при известной структуре, то переходим к шагу 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.


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

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


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

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


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

Выводы:

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


Таблица 1. Результаты времени выполнения алгоритма на ВС при различных значениях логических операторов.

Тип ВС Размерность Значения логических операторов Полное время решения задачи в условных единицах
Обобщенный гипертор 1x3x3 23T,24T,27T 96
Обобщенный гипертор 1x3x3 23T,24T,27F 96
Обобщенный гипертор 1x3x3 23T,24F,27T 104
Обобщенный гипертор 1x3x3 23T,24F,27F 104
Обобщенный гипертор 1x3x3 23F,24T,27T 94
Обобщенный гипертор 1x3x3 23F,24T,27F 94
Обобщенный гипертор 1x3x3 23F,24F,27T 91
Обобщенный гипертор 1x3x3 23F,24F,27F 91

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

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

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

Заключение


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

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

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

Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: