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

Рис.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, при других алгоритмах эффективная конфигурация сети может быть другой.

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

Заключение

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

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

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