Планирование распределения программных модулей по процессорам…
1
УДК 6.83.1
Планирование распределения программных модулей
по процессорам вычислительной системы
© Ю.М. Руденко
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Рассмотрены вопросы планирования распределения программных модулей по узлам
однородной вычислительной системы с разделяемой памятью. В качестве ин-
струмента планирования использованы временные диаграммы ранних сроков окон-
чания выполнения программных модулей. Это позволяет заранее распределять
модули по узлам вычислительной системы и минимизировать время решения по-
ставленной задачи и количество процессоров, используемых для ее решения. При
вычислении ранних сроков окончания выполнения программных модулей учитыва-
лось время передачи информации между нитями, составленными из программных
модулей. На основе этих диаграмм созданы нити программных модулей, каждая
из которых выполнена на своем процессоре. Между некоторыми процессорами
существует обмен информацией, требующий определенных временных затрат,
которые необходимо учесть, скорректировав соответствующим образом времен-
ные диаграммы. В ряде случаев некоторое количество процессоров может быть
использовано в качестве передающих звеньев (транзитных вычислительных эле-
ментов). Построение плана распределения программных модулей по процессорам
рассмотрено на примере структуры вычислительной системы из класса
D
n
-графов типа «Циркулянт» G(11, 1, 2, 5). Так как диаметр этой вычислительной
системы равен двум, то максимальное количество транзитных процессоров для
соответствующей передачи равно единице. Алгоритм обработки данных пред-
ставлен в виде граф-схемы, в которой цикл по счетчику циклов приведен в явном
виде, так как реализация этой части алгоритма является наиболее сложной. Вна-
чале нити распределяются по процессорам произвольно, затем осуществляется
построение межнитевых связей. Здесь важно, чтобы количество неиспользуемых
в заданные отрезки времени процессоров было достаточным для построения этих
связей. При этом в случае необходимости можно минимизировать количество
транзитных процессоров и время решаемой задачи, осуществляя различные вари-
анты размещения нитей на вычислительных модулях.
Ключевые слова:
вычислительная система, распределение модулей, программные
модули, вычислительный модуль, граф-схема, матрица следования, матрица ди-
станций, нить.
Наиболее распространенным способом решения задач на одно-
родной вычислительной системе является построение очередей из
программных модулей, которые затем в связи с возникающими ситу-
ациями случайным образом распределяются по процессорам [1, 2, 3].
В настоящее время для вычислительного элемента, находящегося в
узле вычислительной сети, используют различные термины: элемен-
