ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
117
но расширить возможности представления решаемых задач с помо-
щью граф-схем.
Для удобства исследования и преобразования графов вводится
матрица следования – транспонированная матрица смежности из тео-
рии графов [5], которая вычисляется в блоке 4. Именно матрица сле-
дования является основой для последующего построения рассматри-
ваемой системы. По графу без контуров может быть построена тре-
угольная матрица следования с нулевыми элементами на главной
диагонали.
Для анализа матрицы следования необходимо отразить в ней не-
явные связи между операторами, называемые транзитивными, кото-
рые реально существуют и определяются задающими связями, кото-
рые между ними в графе отсутствуют. Их введение необходимо для
выявления ветвей связанных операторов, которые не могут выпол-
няться параллельно, и построения матрицы следования с транзитив-
ными связями [6], реализованного в блоке 5.
При исследовании граф-схем алгоритмов одними из их основных
характеристик являются ранние и поздние сроки окончания выпол-
нения операторов [7], используя которые, можно построить планы
решения параллельной задачи на однородных вычислительных си-
стемах произвольной конфигурации. Эти величины определяются в
блоке 6 структурной схемы системы. Диаграммы выполнения опера-
торов для ранних и поздних сроков – наглядный способ представле-
ния многопроцессорной обработки.
Для удобства размещения операторов алгоритма на вычисли-
тельных модулях системы ее структура представляется в виде матри-
цы дистанций. Она определяет подходящие вычислительные модули,
которые имеют минимальные расстояния со всеми остальными мо-
дулям, для размещения нитей решаемой задачи [7]. Построение мат-
рицы дистанций реализовано в блоке 7.
При построении алгоритмов распараллеливания часто приходит-
ся использовать матрицы следования общего не треугольного вида.
В этом случае просмотр строк матрицы производится неоднократно
до установления факта ее неизменности. В результате указанных
преобразований в блоке 8 устанавливается факт наличия контура в
графе, о котором свидетельствуют ненулевые диагональные элемен-
ты. Весь последующий предлагаемый метод должен исключать нали-
чие контуров. В работе [7] рассмотрен алгоритм определения конту-
ров в граф-схеме.
Матрица следования с транзитивными связями позволяет опре-
делить матрицу логической несовместимости и матрицу независи-
мости, за формирование которых отвечают блоки 9 и 10 соответ-
ственно. Алгоритм нахождения матрицы несовместимости, по-
дробно описанный в статье [8], предусматривает формирование