Ю. М. Руденко
УЧЕТ ЗАВИСИМОСТЕЙ ПРОГРАММНЫХ МОДУЛЕЙ
ПО ДАННЫМ И ПОСЛЕДОВАТЕЛЬНОСТЯМ
ИХ ВЫПОЛНЕНИЯ ПРИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЯХ
Аннотация. <...> Приведен способ учета зависимостей программных модулей по
данным и последовательности выполнения при параллельных вычислениях,
основанный на анализе транзитивных связей в информационно-логических
графах с помощью построения матриц следования с транзитивными связями. <...> Ключевые слова: Программные модули, параллельные вычисления, транзитивные связи, информационные графы, информационно-логические графы, матрицы следования, вычислительная система, задающие связи, транзитивная
дизъюнкция, транзитивная конъюнкция, план параллельных вычислений. <...> При решении задачи распараллеливания в качестве модели взаимосвязи
программных модулей используются информационные графы (ИГ) с взвешенными вершинами и информационно-логические графы (ИЛГ) с взвешенными вершинами и дугами. <...> ИГ и ИЛГ – это орграфы, которые заданы парой
(V, A), где V – множество вершин графа, отображающее выполняемые программой операторы, или программные модули; А – связи между вершинами
графа. <...> Если вершина отображает логический оператор или функцию, то имеет две исходящие связи. <...> Одна связь обозначает выход «истина» и эта дуга
имеет вес «iТ», вторая обозначает выход «ложь» и эта дуга имеет вес «iF», где
i соответствует номеру рассматриваемого логического оператора. <...> Важную роль
играют не только задающие связи z A для информационно-логических и
информационных графов, но и так называемые транзитивные [1]. <...> Если
{α, β, γ} V, и α ==> β, а β ==> γ связаны задающими дугами, то существует
транзитивная связь α → γ, где символ «==>» обозначает задающую связь, а
символ «→» – транзитивную. <...> Выполнение программных модулей или операторов, связанных задающими или транзитивными связями, нецелесообразно
планировать на одном и том же процессоре, т.к. при этом обеспечивается более легкий доступ к данным, полученным на более <...>