|
2. Удаляем т обслуженных узлов из графа. 3. Повторяем шаги 1 и 2 для оставшегося графа. Планы, полученные таким образом, являются оптимальными при объявленных ограничениях. Процедуры разметки и планирования достаточно просты в исполнении и изображены на рисунке 2.1.9. Как было показано выше, минимальное время обработки графа, размеченного в соответствии с процедурой Хью, равно я(тах). Предположим, требуется обработать граф за предписанное время t, где t = a(max)+ С и С положительное целое число. Минимальное число т ресурсов, необходимое для обработки графа за время t, вычисляется как /л -1 < [1 /(у* + С)]£р(ати + !-;')< , где p(i) обозначает количество узлов в графе с меткой а„ ay* величина константы у, которая максимизирует данное выражение. Для пояснения алгоритма генерации 2-В, рассмотрим рисунок 2.1.9. Для С = 0 величина у* имеет место, когда у = 1 или у = 2. То есть, для обработки графа за минимальное время необходимо четыре ресурса. Для С = 1, t = 8 и у*, имеющем место при у = 2 илиу=5, требуется три ресурса. Меняя С, далее мы определим, что необходимы три ресурса, когда задачи должны быть выполнены за 9 единиц, и только два ресурса необходимы для максимального времени вычисления в 10 единиц. Таким образом, далее автором предлагается использовать процедуру Хью как основу разработанной детерминированной модели формирования распределенных процессов в общем случае временного анализа и коррекции, когда алгоритм представлен последовательно-параллельным набором единичных задач. При этом ранее в рамках процедуры анализа и коррекции ограничения на ресурсы не рассматривались. Считалось, что задачи процесса выполняются в срок, независимо от наличия/отсутствия ресурсного времени. Данное ограничение, однако, является алгоритмически проверяемым, т.е. 56 |
Планы, полученные таким образом, являются оптимальными при объявленных ограничениях. Процедуры разметки и планирования достаточно просты в исполнении и изображены на рис. 2.14. Как было показано выше, минимальное время обработки графа, размеченного в соответствии с процедурой Хью, равно а(тах). Предположим, требуется обработать граф за предписанное время t, где t = a(max)+ С и С положительное целое число. Минимальное число т процессоров, необходимое для обработки графа за время t, вычисляется как w -1 < [17(Г* + C)]£Xtfmax +1 j) < т, J-i где p(i) обозначает количество узлов в графе с меткой ah ay* величина константы у, которая максимизирует данное выражение. Для пояснения алгоритма генерации 2-В, рассмотрим рис. 2.14. Для С = 0 величина у* имеет место, когда у = 1 или = 2. То есть, для обработки графа за минимальное время необходимы 4 процессора: Для С = 1, t = 8 ну*, имеющем место при у = 2 или у=5, требуются три процессора. Меняя С, далее мы определим, что необходимы три процессора, когда задачи должны быть выполнены за 9 единиц, и только два процессора необходимы для максимального времени вычисления в 10 единиц. Иллюстрация алгоритма Хью также представлена в приложении 3. Таким образом, далее автором предлагается использовать процедуру Хью как основу разработанной'детерминированной модели» формирования алгоритмов распределенной обработки иуправления в общем случае временного анализа и коррекции (разд. 2.1.), когда алгоритм представлен последовательно-параллельным набором единичных задач. При этом ранее в рамках процедуры анализа и коррекции ограничения на ресурсы процессора не рассматривались. Считалось, что задачи алгоритма выполняются в срок, независимо от наличия/отсутствия процессорного времени. Данное ограничение, однако, является алгоритмически проверяемым, т.е. процедура 62 |