Например, цену структуры перекрытия можно определять как число загрузок сегментов, реализованных при выполнении программы, или как число реализованных при выполнении или ожидаемых вызовов модулей, принадлежащих перекрываемым сегментам. Число ожидаемых вызовов модуля т4 можно интерпретировать как уровень подчинения модуля, соответствующий числу дуг в пути графа G от основной вершины mt до вершины ти предполагая, что из двух модулей одного пути более удаленный от гпч подчиненный модуль принадлежит к внутреннему циклу программы и выполняется чаще, чем подчиняющий его модуль. Очевидно, что последний из перечисленных способов оценки структуры перекрытия самый грубый, так как он не учитывает особенностей решаемой задачи, но и самый дешевый; он позволяет оптимизировать структуру перекрытия, зная лишь логическую структуру программы, и может быть применен на первом этапе оптимизации, когда предварительное выполнение программы невозможно. В дальнейшем оптимизация программы может быть проведена с использованием более точных способов оценки, если это необходимо.

Перейдем к рассмотрению задач, которые возникают при выборе оптимальной структуры перекрытия: построение структуры перекрытия с минимальными требованиями на память и построение структуры перекрытия с заданными требованиями на память и минимальным временем выполнения.

Первая задача решается однократно с целью определения минимального объема памяти Lmln, достаточного для выполнения программы, поэтому при ее решении можно не учитывать затраты времени на загрузку сегментов. Вторая задача решается многократно для различных значений L в пределах LmlnL imas, где Lmax -длина несегментированной программы, равная сумме длин модулей.

При решении этих задач предполагается, что сегментация программы выполнена тривиально: один модуль в один сегмент.

Логическая структура сегментированной таким образом программы и отображающий ее граф G=(S, V) обладают теми же свойствами, что и модульная структура и отображающий ее граф G=(M, V) соответственно. Граф G= (S, V) получается из графа G=(M, V) путем переименования вершин т{ в s, и представляет собой, как и граф G=(M, V), ориентированный граф без контуров.

Решение рассматриваемых задач отыскивается для двух наиболее широко используемых классов структур перекрытия: «дерево ветвей» и «дерево уровней», изображенных на смотреть обзор под номером 2.