|
минимальное время выполнения. Это подтверждает эффективность разработанной автором комбинированной аналитико-оптимизационной процедуры, рассмотренной в предыдущем параграфе. Уровень производительности, полученный Адамом (в пределах 14 % от оптимального) для планирования с наидлиннейшим путем, сравним с уровнем производительности, полученным Маначером, 15%. Почти оптимальное планирование наидлиннейшего пути или планирование с критическим путем также было одобрено Кохлером, который продемонстрировал, что производительность этих эвристик возрастает с увеличением числа ресурсов. Итак, в рамках аналитико-оптимизационной процедуры предлагается улучшить реализуемый подход к формированию распределенных процессов с помощью метода критического пути. Для некоторого графа существует путь от входного узла до выходного, называемый критическим путем, который определяет минимальное время выполнения для графа. Этот подход не требует равенства времен задач. При заданном значении времени выполнения критического пути Тср существует «интервал завершения» (определяемый самым ранним и самым поздним временем начала выполнения) для каждой задачи в графе, в течение которого эта задача должна быть завершена, и время ее выполнения не должно превысить Тср. В приближении к нижней границе количества ресурсов следует рассматривать целочисленные интервалы между 0 и Тср. Внутри каждого из этих интервалов задачи перераспределены так, чтобы дать минимальное перекрытие внутри интервала. Среднее число ресурсов, требуемых в интервале, определяет минимальное число ресурсов, необходимых для этого интервала. Если все интервалы исследованы, то максимальное среднее значение, округляемое в большую сторону к ближайшему целому, представляет минимальное количество ресурсов, необходимых для обработки графа за минимальное время. 62 |
HLFET (Highest Levels First with Estimated Times, приоритет наивысших уровней с оценкой продолжительности). Термин «уровень», используемый здесь, относится к сумме весов всех вершин в наидлиннейшем пути от задачи до заключительного узла. Так как не предполагается независимость задач, предшествующие задачи должны быть завершены до того, как инициируется задача; HLFNET (Highest Levels First with No Estimated; Times, сначала наивысшие уровни без оценки продолжительности). Фактически предполагается, что все задачи имеют равные времена; RANDOM, произвольный. Приоритеты задачам назначаются произвольно; SCFET (Smallest Co-levels First with Estimated Times, сначала наименьшие соуровни с оценкой продолжительности). Соуровень задачи определяется так же, как и уровень, за исключением того, что длина пути вычисляется от входного узла, а не от заключительного. Приоритет назначается в соответствии с соуровнями (т. е. чем меньше соуровень, тем выше приоритет); SCFNET (Smallest Co-levels First with No Estimated Times, сначала наименьшие соуровни без оценки продолжительности). SCFNET определяется как SCFET, но все задачи имеют равную длительность. Это равнозначно самому раннему разбиению по старшинству, если не принимается во внимание время выполнения. Результаты, моделирования, основанного на реальных и случайно генерируемых графах, показывают следующий порядок соответствия: HLPET, HLFNET, SCFNET, RANDOM И SCFET. Почти оптимальная производительность HLPET также подтверждает полезность планов с наидлиннейшим путем, когда показателем производительности выбирается минимальное время выполнения. Это подтверждает эффективность разработанной автором комбинированной аналитико-оптимизационной процедуры, рассмотренной в предыдущем параграфе. 67 Уровень производительности, полученный Адамом (в пределах 14 % от оптимального) для планирования с наидлиннейшим путем, сравним с уровнем производительности, полученным Маначером, 15%. Почти оптимальное планирование наидлиннейшего пути или планирование с критическим, путем: также было одобрено Кохлером, который продемонстрировал, что производительность этих эвристик возрастает с увеличением числа процессоров. Итак, в рамках аналитико-оптимизационной процедуры предлагается улучшить реализуемый подход к формированию распределенных алгоритмов с помощью метода критического пути. Для некоторого графа существует путь от входного узла до выходного, называемый критическим путем, который определяет минимальное время выполнения для графа. Этот подход не требует равенства времен задач. При заданном значении времени выполнения критического пути Тср существует «интервал завершения» (определяемый самым ранним и самым поздним временем начала выполнения) для каждой задачи: в графе, в течение которого эта задача должна быть завершена, и время ее выполнения не должно превысить Тср. В приближении к нижней границе количества процессоров следует рассматривать целочисленные интервалы между 0 и Тср. Внутри каждого из этих интервалов задачи перераспределены так, чтобы дать минимальное перекрытие внутри интервала. Среднее число процессоров, требуемых в интервале, определяет минимальное число процессоров, необходимых для этого интервала. Если все интервалы исследованы, то максимальное среднее значение, округляемое в большую сторону к ближайшему целому, представляет минимальное количество процессоров, необходимых для обработки графа за минимальное время. Похожие идеи могут быть использованы для определения минимального времени выполнения с фиксированным числом процессоров. В течение каждого интервала должно иметь место некоторое количество вычислений,, чтобы убедиться, что общее время выполнения не превышает 68 |