Параллельное программирование



              

Централизованное диспетчирование


В более сложном виде задача диспетчирования возникает в централизованных ВС. В чем она заключается?

Пусть некоторый супервизор, например, в системе реального времени, определил множество информационно взаимосвязанных задач (частично — упорядоченное множество задач), которые должны решаться циклически, а возможно, и единственный раз процессорами ВС. Известны временные оценки решения задач.

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

Информационный граф и расширенная матрица следования

Рис. 8.3.  Информационный граф и расширенная матрица следования

Показана соответствующая ему матрица следования S и расширенная матрица следования S*, содержащая и столбец весов.

Универсальным критерием, используемым при решении задачи диспетчирования как задачи распараллеливания, является минимум времени выполнения совокупности работ, распределяемых между процессорами.

Формально: пусть задано множество работ A = {

1 , ...,
m} и известно множество временных оценок этих работ T = {t1 , ..., tm}, а также известна частичная упорядоченность, задаваемая матрицей следования S. Пусть ВС — однородная (т.е. все процессоры обладают одинаковой производительностью) и содержит n процессоров. Пусть в результате распределения множества работ A между n процессорами каждый (i-й) процессор оказался занятым решением задач в течение времени Ti. Тогда время решения всей совокупности задач

 \begin{align*} T_{\text{реш}} = \max_{i=1, ..., n} \{T_i\} \end{align*}

Задачей диспетчера является распределение работ

1,...,
m между процессорами, обеспечивающее

 \begin{align*} T_{\text{реш}} - \frac{1}{n} \sum_{j=1}^m t_j \longrightarrow \min \end{align*}

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




Содержание  Назад  Вперед