Задание второго графа в файле F17_2.dat

Задание первого графа в файле F17_1.dat

Второй граф:

Задание второго графа в файле F17_2.dat

Предварительная подготовка:

Tmax = T1 + T2 = 480

Tmin = max(Tmin1,Tmin2) = 232

Этапы выполнения:

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

Определить наиболее оптимальную стратегию или стратегии для каждого графа с точки зрения минимального времени решения.

Определить суммарное время выполнения двух задач в однозадачном режиме:

Задача №1:

Задача №2:

Для первой задачи наименьшее число процессоров, при котором достигается минимальное время решения(232 МТ), равно 3. При данном количестве процессоров достижение минимального времени происходит на двух стратегиях: с минимальным временем выполнения, с максимальным количеством последователей. Следовательно, эти стратегии наиболее эффективны с точки зрения минимального времени выполнения.

Для второй задачи наименьшее число процессоров, при котором достигается минимальное время решения(18 МТ), равно 3. При данном количестве процессоров достижение минимального времени происходит на двух стратегиях: с максимальным временем выполнения, с максимальным количеством последователей. Следовательно, эти стратегии наиболее эффективны с точки зрения минимального времени выполнения.

Суммарное время выполнения двух задач в однозадачном режиме:

Tсум = Tmin1+Tmin2 = 232+18 = 250 МТ.

2)В многозадачном режиме промоделировать выполнение набора из двух задач с равными приоритетами в МВС на том же количестве процессоров и с теми де стратегиями назначения, что и в п1. Определить время выполнения набора задач, ускорение и коэффициенты загрузки процессоров.

Результаты моделирования для различных стратегий свести в таблицу (стратегия, количество процессоров, время решения задач, ускорение, коэффициент средней загрузки процессоров).

Определить наиболее оптимальную стратегию или стратегии для набора задач с точки зрения минимального времени решения.

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

3) Сравнить графически однозадачный и многозадачный режимы функционирования МВС по результатам выполнения п1. и п2. (по времени выполнения, по достигаемому ускорению и загрузке процессоров).Проанализировать и объяснить полученные результаты.

Для стратегии выбора с максимальным временем выполнения:

Время выполнения:

Достигаемое ускорение:

Коэффициент загрузки процессоров:

Для стратегии выбора с минимальным временем выполнения:

Время выполнения:

Достигаемое ускорение:

Коэффициент загрузки процессоров:

Для стратегии выбора с максимальным количеством последователей:

Время выполнения:

Достигаемое ускорение:

Коэффициент загрузки процессоров:

Время выполнения в многозадачном режиме на нескольких процессорах, очевидно, практически не превосходит сумму времен задач 1 и 2 для однозадачного режима. Это происходит в силу того, что при выполнении задачи 1 в многозадачном режиме загрузка процессоров при p>1 никогда не достигает 100% и в промежутки простоя МВС обсчитывает подзадачи задачи 2. И дополнительного времени на выполнение второй задачи не требуется. Ибо она вся умещается в промежутки простоя выполнения 1 задачи.

Величина ускорения никогда не превосходит ускорение первой или второй задачи при неограниченных ресурсах (p>=4), потому как суммарное время выполнения обоих задач все-равно выше времени выполнения любой из них в отдельности.

Коэффициент загрузки процессоров для многозадачного режима при двух процессорах всегда выше коэффициентов для отдельно взятых задач. Потому как при двух процессорах на любой стратегии вычисления ведутся с минимумом простоев. Т.е. p=2 – количество процессоров, при котором вычисления будут вестись максимально выгодно с точки зрения использования аппаратных ресурсов.

4) На основании результатов п.2. выбрать наилучшую стратегию назначения и для этой одно стратегии выполнить набор задач в многозадачном режиме для различных вариантов задания приоритетов. Выбрать наилучшее соотношение приоритетов выполняемых задач.

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

Наилучшее соотношение приоритетов достигается, если при выборе задач предпочтение отдается первой.

5)Определить характеристики МВС, обеспечивающие достижение заданного времени выполнения набора задач при минимальных аппаратных затратах(числе процессоров p), Тзад = Тmin+4.

Проанализировать различные варианты изменения характеристик МВС при достижении Тзад также в зависимости от приоритета задач.

Исследовать зависимости коэффициента загрузки процессоров от количества процессоров при различных стратегиях назначения готовых узлов и различных приоритетах задач.

Проанализировать полученные результаты, выбрать наилучший способ организации вычислительного процесса для Тзад.

Тзад = 232+4 = 236

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

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

При смене стратегий достижение Тзад не сохраняется.

В данном случае выполнение задачи за Тзад твердо завязано на условиях эксперимента. И выполняется в единственном случае(описано выше).

Коэффициент ускорения при решении задач с равным приоритетом является максимальным при стратегии с макс. числом последователей.

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

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

К сожалению, наилучший способ организации вычислений для достижения Тзад является так же единственно возможным. Он описан выше.

Вывод:

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