|
Похожие идеи могут быть использованы для определения минимального времени выполнения с фиксированным числом ресурсов. В течение каждого интервала должно иметь место некоторое количество вычислений, чтобы убедиться, что общее время выполнения не превышает Тср. Если количество используемых ресурсов .меньше некоторого минимума, то каждый интервал будет вносить количество времени сверх того, что могло бы быть внесено, если ограничение ио Тср выполнено. Максимальная нехватка времени, вносимая всеми интервалами, определяет минимальное количество времени свыше Тср, необходимого для обработки графа. Рассмотренная процедура позволяет разработать ряд алгоритмов для минимизации числа ресурсов, необходимых для выполнения распределенного плана за заданное время, и для минимизации времени выполнения с фиксированным числом ресурсов. Такие процедуры формирования распределенных процессов будем называть процессорнооптимальными (оптимальными по времени). Рассматриваемая среда планирования состоит из множества задач частичного упорядочивания с неравными временами исполнения и активных задач без приоритетных прерываний. Добавление данных условий в алгоритм проявляется в виде значительного увеличения времени вычислений даже на мощных компьютерных системах. Однако, альтернативный метод полный перебор все равно является гораздо менее желательным, чем субоптимальные эвристические методы (особенно, если они могут выполняться в интерактивном режиме). Трудность получения оптимального формирования распределенных процессов для общей среды планирования очевидна. 2. Сравнение приоритетных и неприоритетных планов. Методы минимизации времени выполнения для некоторых особых случаев были рассмотрены в работе [18] об оптимальных неприоритетных двухресурсных планах. Точкой опоры в них является возможность преобразования графа G с произвольными взаимно соизмеримыми весами 63 |
Уровень производительности, полученный Адамом (в пределах 14 % от оптимального) для планирования с наидлиннейшим путем, сравним с уровнем производительности, полученным Маначером, 15%. Почти оптимальное планирование наидлиннейшего пути или планирование с критическим, путем: также было одобрено Кохлером, который продемонстрировал, что производительность этих эвристик возрастает с увеличением числа процессоров. Итак, в рамках аналитико-оптимизационной процедуры предлагается улучшить реализуемый подход к формированию распределенных алгоритмов с помощью метода критического пути. Для некоторого графа существует путь от входного узла до выходного, называемый критическим путем, который определяет минимальное время выполнения для графа. Этот подход не требует равенства времен задач. При заданном значении времени выполнения критического пути Тср существует «интервал завершения» (определяемый самым ранним и самым поздним временем начала выполнения) для каждой задачи: в графе, в течение которого эта задача должна быть завершена, и время ее выполнения не должно превысить Тср. В приближении к нижней границе количества процессоров следует рассматривать целочисленные интервалы между 0 и Тср. Внутри каждого из этих интервалов задачи перераспределены так, чтобы дать минимальное перекрытие внутри интервала. Среднее число процессоров, требуемых в интервале, определяет минимальное число процессоров, необходимых для этого интервала. Если все интервалы исследованы, то максимальное среднее значение, округляемое в большую сторону к ближайшему целому, представляет минимальное количество процессоров, необходимых для обработки графа за минимальное время. Похожие идеи могут быть использованы для определения минимального времени выполнения с фиксированным числом процессоров. В течение каждого интервала должно иметь место некоторое количество вычислений,, чтобы убедиться, что общее время выполнения не превышает 68 Тср. Если количество используемых процессоров меньше некоторого минимума, то каждый интервал будет вносить количество времени сверх того, что могло бы быть внесено, если ограничение по Тср выполнено. Максимальная нехватка времени, вносимая всеми интервалами, определяет минимальное количество времени свыше Тср, необходимого для обработки графа. Рассмотренная-процедура позволяет разработать, ряд алгоритмов для минимизации числа процессоров, необходимых для выполнения распределенного плана за заданное время, и для минимизации времени выполнения с фиксированным числом процессоров. Такие процедуры формирования распределенных алгоритмов будем называть процессорнооптимальными (оптимальными по времени). Рассматриваемая среда планирования состоит из множества задач частичного упорядочивания с неравными временами исполнения и активных задач без приоритетных прерываний. Добавление данных условий в алгоритм проявляется • в виде значительного увеличения времени вычислений даже на мощных компьютерных системах. Однако, альтернативный метод полный перебор все равно является гораздо менее желательным, чем субоптимальные эвристические методы (особенно, если они могут выполняться в интерактивном режиме). Трудность получения оптимального формирования распределенных алгоритмов для общей среды планирования очевидна. 2. Сравнение приоритетных и неприоритетных планов. Методы минимизации времени выполнения, для некоторых особых случаев были рассмотрены в работе [...] об оптимальных неприоритетных двухпроцессорных планах. Точкой опоры в них является возможность преобразования графа G с произвольными взаимно соизмеримыми весами задач в граф Gw с временами выполнения, равными w. Как и раньше, w самый большой вес, кратный всем весам задач в G. 69 |