Введение в архитектуру компьютеров


Схема алгоритма


1. Представление исходной программы в виде графа. Этот процесс достаточно подробно изложен выше.

2. Сведение циклического графа к ациклическому. Большое количество вершин графа G приводит к большому порядку матрицы смежности C. Для уменьшения порядка матрицы произведем сжатие линейных участков программы в отдельные обобщенные операторы, т. е. выделим в исходном графе G линейные подграфы и поставим им в соответствие одну обобщенную вершину графа, не нарушая при этом ни одного из существующих ориентированных циклов. Таким образом, из исходного графа G мы получаем граф G¢. Затем в графе G¢ выделим множество сильносвязных подграфов. Каждый сильносвязный подграф заменим отдельной вершиной. После выполнения указанных действий в общем случае циклический граф G превращается в сжатый ациклический граф G¢¢, представляющий собой модель исходной программы. Вершинами графа G¢¢ будут фрагменты исходной программы в виде линейных участков и сильносвязных областей.

3. Наложение информационных связей, заданных между операторами программы, на связи возможных переходов. До этого момента информационно-логические связи, заданные между операторами программы, не претерпевали существенных изменений. Преобразуем их, учитывая взаимосвязи укрупненных вершин графа G¢¢.

Если в графе G¢¢ существует переход от вершины vi

к вершине vj, то это совсем не означает, что начало выполнения оператора, соответствующего вершине vj, должно тут же следовать за окончанием оператора, соответствующего вершине vi. Однако, если результат оператора vi

является аргументом оператора vj, то в данном случае выполнение оператора vj не может начаться раньше, чем окончится выполнение оператора vi.

После анализа входов и выходов для всех компонент приведенного графа G¢¢ производится наложение информационных связей на связи возможных переходов, т. е. на связи, представленные в матрице смежности графа G¢¢. Для анализа входов и выходов всех компонент графа G¢¢ необходимо составить матрицу H информационной зависимости, элементы которой hij принимают соответственно значения 0 или 1.


Начало  Назад  Вперед



Книжный магазин