|
Информационная структура программы есть совокупность
сведений о том, как отдельные элементы программы связаны между
собой.
16.2.
Графовые модели программ
Целью рассмотрения моделей для программ на последовательных
языках программирования является решение таких вопросов, как:
-
проведение реорганизации программы, с целью минимизации числа
используемых переменных,
-
оптимальное использование кэш
-
памяти,
-
минимизация числа обменов с медленной памятью и т.д.
-
проблемы, связанные с выявлением в программах скрытого
параллелизма и свойств, необходимых для эффективного его использования.
Существует
два подхода к изучению информационной структуры
программ:
164
Денотационный подход опирается на исследование состояния памяти
программ. В практических приложениях он используется редко.
Операционный подход, при котором исполнение (развитие) любой
программы представляется в виде набора выполненных действий (операций),
некоторым образом связанных между собой. Содержание действий, их
вычислительная мощность и способ связи в рамках данного подхода не
фиксируются. Они определяются в каждом конкретном случае по
-
своему в
зависимости от целей исследования. Операционный подход в практических
приложениях используется очень часто. Этот подход порождает класс
моделей программ, называемых графовыми. В этом классе каждая модель
представляет граф, в котором вершины соответствуют каким
-
то множествам
действий программы, а дуги (ребра) так или иначе связаны с отношениями
между ними. Диапазон уровней сложности графовых моделей огромен.
Отдельная вершина может представлять и программу целиком, и какие
-
то ее
большие или малые фрагменты и даже отдельные элементарные операции.
Также приходится учитывать многообразие связей.
В программе можно выделить два типа действий:
-
преобразователи, которые осуществляют переработку информации.
Например, операторы присваивания. Их левая часть определяет область
памяти программы, подвергающейся
воздействию преобразователя, а
переменные из правой части показывают на необходимые для выполнения
данного действия аргументы.
-
распознаватели,
которые
определяют
последовательность
срабатываний преобразователей в процессе работы программы. Например,
альтернативные операторы: условные, разного рода переключатели и т. п.
Основное их назначение состоит в выборе одной из нескольких возможных
альтернатив дальнейшего следования.
В целях упрощения исследования будем предполагать, что множества
операторов, соответствующих этим двум типам действий, не пересекаются.
165
Пример. Пусть решается система линейных алгебраических уравнений
Ах = b с левой двухдиагональной матрицей порядка n. Обозначим через а
1
, ...,
а
n
диагональные элементы матрицы А, через c
1
, ..., c
n
‒
ее поддиагональные
элементы, через b
1
, ..., b
n
‒
правые части, через x
1
, ..., x
n
‒
координаты
решения. Необходимо найти максимальную координату вектора
-
решения.
Запишем алгоритм 1:
y=b
1
/a
1
х
=
у
DO i=2, n
х
=(b
i
-
с
i
x/a
i
)
if (
х
<=
у
) go to 7
у =х
END DO
После выполнения программы значение переменной
у
будет равно
максимальному из чисел х
1
, ..., х
n
. Здесь операторы с метками 1, 2, 4, б
являются преобразователями, операторы с метками 3, 5, 7 ‒
распознавателями.
Между действиями программы существуют связи двух типов:
‒
связь по управлению или операционная связь определяется фактом
выполнения одного действия непосредственно за другим.
‒
информационную связь существует в случае, если одно действие
использует в качестве аргументов результатов выполнения других действий.
Каждому оператору исходной программы поставим в соответствие вершину
графа ‒
экземпляр преобразователя или распознавателя в зависимости от
типа оператора. Получим множество вершин, между которыми согласно
исходной программе определим отношение, соответствующее передаче
управления. Если текст программы допускает выполнение одного оператора
непосредственно за другим, то соответствующие вершины соединим дугой,
направленной от предшественника к последователю. Получим граф, который
обычно называется графом управления, управляющим графом, графом
166
передач управления или просто
Do'stlaringiz bilan baham: |
