- 3 -

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Объединение независимых алгоритмов в систему производится на основе временных зависимостей системы синхронизации реального времени. Основным отличием данной системы независимых алгоритмов от других систем алгоритмов, основанных на зависимостях по информации и управлению, является невозможность сведения её к одному объединённому алгоритму без специальных дополнительных построений.

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

Для каждого алгоритма, выполняющегося на однородной вычислительной системе (ВС), может быть построен граф

G=(X, P, Г) со скалярными весами вершин, где

X - множество вершин графа, соответствующих множеству операторов алгоритма,

Р - множество весов вершин, определяющих время выполнения каждого оператора,

Г - множество дуг, задающих связи между операторами.

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