Составление плана выполнения комплекса программ в многопроцессорных вычислительных системах (МВС). Механизмы адаптивного поведения муравьиной колонии. Роевой алгоритм планирования работы МВС. Распределение программных заявок на обслуживание процессором.
Аннотация к работе
Роевой алгоритм планирования работы многопроцессорных вычислительных системВ работе рассматривается задача составления плана выполнения комплекса программ, в многопроцессорных вычислительных системах (МВС). На вход МВС поступает множество независимых потоков заявок (программ), которые необходимо распределить между процессорами. Решение задачи планирования представляется как задание распределения заявок по процессорам, и определение очереди заявок на обслуживание процессором.Таким образом, требуется наилучшим по быстродействию или равномерности загрузки образом спланировать выполнение комплекса программ на заданном множестве процессоров, а в случае наличия связи между программами, также определить последовательность их исполнения на каждом процессоре. Среди существующих известных и эффективных точных методов решения РЗ наибольшее распространение получили алгоритмы, построенные по схеме метода ветвей и границ (МВГ) [3]. Если время rj непрерывного использования процессора для выполнения каждой программы wj, одинаково для всех процессоров, то множеству W сопоставляется множество Таким образом, загрузка Rli заявками процессора ei с учетом времени переключения между соседними заявками в очереди Pli, а также времени rij непрерывного использования процессора ei для выполнения каждой программы wj I Wli определится как: Rli =Tli rik , где k|WKI Wli (5) Вторая составляющая графа поиска решений связана с необходимостью упорядочивания заявок, т.е. фактически введения приоритета для заявок каждой группы потоков, обслуживаемых одним прибором.Несмотря на достаточно большое число разработанных моделей, и алгоритмов оптимизации планирования и диспетчеризации многопроцессорных вычислительных систем, исследователи часто сталкиваются с рядом проблем, к числу которых относятся трудность в обосновании качества результатов анализа, учитывающего специфику задачи. В работе рассматриваются новые принципы решения задачи планирования работы МВС на основе моделей адаптивного поведения муравьиной колонии. Разработаны модифицированные механизмы поведения муравьев и структура пространства решений, в рамках которого организован поисковый процесс, базирующийся на моделировании адаптивного поведения роя муравьев.