Cтраница 1
Граф программы - это циклический ориентированный граф G ( X, U), вершины которого х представляют различные шаги программы. Вершины связаны дугами и, представляющими разветвления и циклы в программе. Граф программы содержит одну начальную вершину Xi, предшествующую всем остальным вершинам графа и не имеющую входящих дуг, и одну конечную вершину хх, которая следует за всеми остальными вершинами и не имеет исходящих дуг. [1]
Тщательный анализ графа программ позволяет обнаружить недостатки их структуры, неиспользуемые обратные связи, недостижимые ссылки и неиспользуемые состояния. Сложность полной проверки графа пропорциональна п2, где п - число вершин графа. [2]
Симметричная структура графа программы Г3 обеспечивает равенство длины всех маршрутов, и стратегия упорядочения по длине вырождается в произвольный выбор маршрутов. [3]
Вернемся к рассмотрению графа программы по рис. а, где предполагается, что ранги работ а, и а / из фронта F могут отличаться более чем на единицу. Обозначим через a i, а / и а - ( и соответственно t i, t и t i) последовательности работ ( случайное время выполнения последовательностей работ) от а /, а / и а, до а и ас. [4]
На рис. 5.6.1 показан граф программы, на котором отмечены операторы чтения из Р и записи в Р переменных А и В. [5]
Марковская граф-модель программы представляет собой взвешенный управляющий граф программы, причем веса дуг ( а также вершин) являются фиксированными значениями некоторых параметров. Для правильно построенной программы и ее граф-модели можно из входа попасть последовательно по дугам в любую вершину, а из любой вершины - в выход. Ограничений на конфигурацию программы и множество реализаций счета граф-модель не накладывает. Для завершения построения модели нужно соединить дугой конечную ( выход) ц начальную ( вход) вершины граф-модели, так что вход становится концом этой дуги. [6]
На рис. 18 представлена часть графа программы, содержащая вершину Ав, в которой происходит объединение. Вероятность использования такой вершины равна сумме вероятностей использования всех вершин, из которых исходят заходящие в эту вершину дуги, умноженных на соответствующие вероятности перехода. [7]
Из указанных свойств получаем правило: вероятности использования всех вершин графа программы, заключенных между двумя вершинами с разветвлением программы, например Ah и Ah 1, одинаковы и равны вероятности ph использования вершины Ah. Поэтому при подсчете вероятностей использования вершин графа программы основную роль играют вероятности использования вершин с разветвлением программы и вероятности перехода, приписываемые дугам графа, исходящим из этих вершин. Это свойство позволяет заменить граф программы его конденсатом. [8]
Одним из трудных вопросов структурного контроля, также как и при решении задачи оптимизации, является организация просмотра графа программы. Просмотр всех возможных путей по графу является в ряде случаев практически нереализуемым. Это происходит, в частности, из-за многократного прохода по уже просмотренным ранее путям. Один из алгоритмов упорядоченного просмотра дерева с запоминанием уже пройденных путей, предложенный Фараджевым В. А., изложен ниже. [9]
Ло кальная оптимизация проводится в пределах оператора ( линейно го участка программы), а для глобальной оптимизации требует ся построение графа программы и организация его просмотра m тем или иным признакам, именам переменных, подвыражениям Оптимизация на линейном участке реализуется существенно про ще, однако при этом возникает задача выявления таких участ ков. Ниже приводятся некоторые из известных методов оптпми зации [9] и рассматриваются способы их реализации. [10]
Простейший ( первый) критерий для планирования тестирования программ состоит в выборе минимального множества маршрутов программы, обеспечивающих исполнение и проверку каждого оператора в программе хотя бы один раз. Граф программы должен быть покрыт минимальным набором путей, проходящих через каждый оператор. Повторная проверка операторов не оценивается и считается избыточной. При этом в процессе тестирования гарантируется выполнение всех передач управления между участками программы и каждого оператора не менее одного раза. Количество исходных тестов и соответствующих им маршрутов зависит от стратегии выбора последовательностей маршрутов. Созданы алгоритмы, позволяющие минимизировать покрытие маршрутами графов при таком критерии анализа. Однако минимальные тесты по этому критерию не обеспечивают проверку исполнения каждого оператора при различных - сочетаниях предшествующих условий и последовательностей операторов, образующих весь набор маршрутов, проходящих через данное ветвление передачи управления. [11]
Все функциональные характеристики выборочно связаны с каждой вершиной в зависимости от предполагаемого анализа. Размерность графа программы находится в прямой зависимости от размера программы. При увеличении размера программы существенно возрастает сложность анализа. Разработаны достаточно эффективные процедуры, позволяющие снижать сложность анализа. В основу таких процедур положены методы итеративной абстракции, которая имеет два аспекта: абстракция цикла и абстракция подграфа связи. Цикл является трудным элементом для эффективной проверки программ, так как он резко увеличивает число логических путей, усложняя тем самым структурную программу. Рассмотрение цикла и анализ его независимо от осталыной части графа программы делают общий процесс проверки более простым и однородным. Такая абстракция цикла приводит к значительному уменьшению размерности модели и снижению структурной сложности. Если вследствие большой размерности приведенного графа желательна дальнейшая абстракция, то может быть применена абстракция подграфа связи, когда максимально сильно связанный подграф в графе программы заменяется одной вершиной. [12]
Путь считается простым, если в нем ни одна дуга не встречается дважды, и составным - в противном случае. Как правило, пути графа программы являются составными. [13]
Из указанных свойств получаем правило: вероятности использования всех вершин графа программы, заключенных между двумя вершинами с разветвлением программы, например Ah и Ah 1, одинаковы и равны вероятности ph использования вершины Ah. Поэтому при подсчете вероятностей использования вершин графа программы основную роль играют вероятности использования вершин с разветвлением программы и вероятности перехода, приписываемые дугам графа, исходящим из этих вершин. Это свойство позволяет заменить граф программы его конденсатом. [14]
Оптимизация программ проводится по тексту на входном языке или на промежуточном языке, структура которого специально приспособлена для решения этой задачи. Из процедур, связанных с машинно-независимой оптимизацией, следует отметить процедуры построения графа программы, выделения линейных участков, выделения циклов, нахождения идентичных операторов. Машинно-зависимую оптимизацию целесообразно производить в блоках транслятора с макроязыка или его внутреннего представления, являющихся выходом транслятора с алгоритмического языка. [15]