Оценка множества работ при решении задач распараллеливания
1
УДК 681.324.006.3
Оценка множества работ
при решении задач распараллеливания
© Н.Б. Толпинская
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
В статье содержится описание подходов к оценке множества работ, которые
выполняются в определенный момент времени на многопроцессорных вычисли-
тельных машинах, и объемов работ на заданном отрезке времени. Эти оценки
позволяют более эффективно планировать распределение работ по процессорам
при статическом решении задач распараллеливания.
Ключевые слова
:
распараллеливание, планирование, загрузка, работа, опе-
ратор.
При решении задач распараллеливания, в особенности при стати-
ческом их решении, требуется получить оптимальный или близкий к
нему план выполнения множества взаимосвязанных работ. Планиро-
вание параллельной реализации таких работ имеет целью макси-
мальное снижение разницы пиковой и реальной производительности
многопроцессорной вычислительной системы путем уменьшения
простоев решающих устройств. Особенно высокие требования к про-
изводительности вычислительных систем предъявляются при их ис-
пользовании в сложных системах управления в реальном времени. В
этом случае при планировании параллельного вычислительного про-
цесса обязательно учитываются оценки времени решения отдельных
задач и производится согласование их с циклическим режимом и ча-
стотой выдачи управляющей информации. Временные диаграммы
решения задач оцениваются во всех возможных ситуациях управле-
ния, и вычислительная система выбирается по самой напряженной
ситуации.
Для представления множества работ при решении задач распа-
раллеливания может быть использован информационный граф
G
= (
X
,
P
,
Г
) [1, 2], который отражает частичную упорядоченность
операторов с учетом их информационной и логической зависимости.
Здесь
X
— множество вершин,
P
— множество весов вершин,
Г
—
множество дуг. Вершинами графа являются подзадачи или процессы
(операторы). Дуги графа отражают наличие информационных или
логических зависимостей между операторами. Вес
t
i
каждой
i
-ой
вершины (
i
= 1, ...,
m
) определяет время выполнения соответствую-
щей подзадачи, процесса или оператора. Вес может быть скалярной
величиной, если многопроцессорная вычислительная система являет-
ся однородной или векторной, если вычислительная система неодно-
