Введение в архитектуру компьютеров

Распределение задач по процессорам


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

Пусть задано P-процессоров и множество задач Z = {Z1, Z2, ..., Zn}, которые надо решить на МВС. Каждая задача из Z может характеризоваться некоторыми параметрами, в частности объемом требуемой памяти, необходимым временем центрального процессора и т. д. Следует построить распределение S1, S2, ..., Sm

задач по процессорам МВС, учитывая параметры задач, с тем, чтобы минимизировать, скажем, общее время решения всего множества задач Z.

При распределении множества задач следует учитывать существующие связи между ними и обеспечивать экстремальное значение некоторому критерию качества при определенных ограничениях. Достижение экстремума может производиться и за счет изменения структуры ВС. Однако динамическая адаптация структуры ВС очень ограничена, и поэтому обычно считают, что состав и структура ВС не изменяются во все время ее работы.

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


Мы укажем только на некоторые случаи однократных алгоритмов построения расписания, т. е. алгоритмов, не изменяющих момент начала выполнения задач при последующем составлении расписания. Это так называемые алгоритмы диспетчирования.

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

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

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

Чаще всего в качестве критерия работы диспетчера выбирается время выполнения всего набора задач, хотя используются и другие критерии: минимальное время простоя (максимальная загрузка) различных устройств МВС; минимальное среднее время ожидания решения для всего набора задач; минимальное число используемых процессоров при заранее заданном времени окончания решения задач и т. д. Иногда используются обобщенные критерии в виде функции, устанавливающей зависимость между отдельными частными критериями. Качество диспетчера тогда – отклонение от экстремального значения обобщенного критерия. Большую сложность здесь представляет процедура обоснованного формирования функции, задающей обобщенный

критерий.


Содержание раздела