Ю.М. Руденко
2
тарный процессор, элементарная вычислительная машина, процес-
сор, вычислительный модуль, узел вычислительной системы и др. В
этой статье термины «процессор», «узел» и «вычислительный мо-
дуль» будут применять в качестве синонимов. В общем случае в свя-
зи с появлением более сложных вычислительных элементов, таких как
суперскалярные, мультитредовые [1, 2] и другие сложные структуры,
требуется учитывать дополнительные особенности создания вычисли-
тельных систем, которые в данной статье не рассматриваются.
Как было показано в [4–8], весьма удобным средством для изоб-
ражения параллельных алгоритмов является граф-схема. В работах
[9, 10] был предложен метод построения диаграмм решения парал-
лельной задачи, представленной информационной граф-схемой.
Рассмотрим планирование распределения программных модулей
по узлам вычислительной системы для случая, когда каждый вычис-
лительный модуль имеет свою локальную память. Временные диа-
граммы запуска и работы вычислительных модулей [11] являются
удобным средством для построения плана распределения операторов
по узлам вычислительной системы. Строки временной диаграммы
будем интерпретировать как нити алгоритма решаемой задачи. Для
удобства размещения операторов алгоритма на вычислительные мо-
дули системы представим ее структуру в виде матрицы дистанций
между вычислительными модулями [10], в которой указаны расстоя-
ния между узлами. Элементы
,
R i j
матрицы дистанций
R
вычис-
ляются по формуле
,
, ,
R i j
r i j
где
,
r i j
— расстояние между
i
-м и
j
-м вычислительными модуля-
ми, определяемое минимальным количеством процессоров, которые
необходимо пройти для попадания из
i
-го в
j
-й вычислительный мо-
дуль,
1 ,
2
r i j
N
(
N
— заданное количество вычислительных
модулей). Предполагается, что
N
вычислительных модулей достаточ-
но для решения поставленной задачи указанным методом.
Чтобы определить показатель близости модулей, найдем сумму
столбцов
St j
матрицы дистанций:
1
, ,
N
i
St j
r i j
(1)
где
1, ..., .
j
N
Упорядочим
St j
по возрастанию. Далее для построения диа-
граммы ранних сроков окончания выполнения операторов образуем
