Введем некоторые определения.

Будем говорить, что два сегмента sa и sb совместимы, если в них нет ни одной пары модулей niissa и msb, которые могут быть одновременно активны, и несовместимы в противном случае.

Структуру перекрытия будем называть корректной, если в ней любая пара перекрывающихся сегментов совместима.

Ясно, что одновременно активными могут быть только модули, соответствующие вершинам одного пути графа G. Поэтому достаточно знать лишь логическую структуру программы, чтобы выявить все корректные варианты перекрытия элементов и решить задачу разработки корректной структуры перекрытия с любыми заданными и, в частности, с минимальными требованиями на память.

Ценой структуры перекрытия будем называть затраты времени на загрузку сегментов AT, которыми оплачивается достигнутое за счет перекрытия сегментов сокращение требований программы на память AL.

Можно построить несколько корректных структур, обеспечивающих одинаковый выигрыш в памяти AL, но из-за того, что повторная загрузка сегмента производится только, если сегмента нет в памяти в момент вызова одного из его модулей, цена этих структур может быть различной. Ясно, что лучшей из них является структура с минимальной ценой. С ростом выигрыша в памяти AL растет и плата за него AT. Эксперименты показывают, что зависимость AT=f(AL), как правило, имеет вид кривой, представленной на смотреть обзор под номером 1. На этой кривой есть критическая точка (К), до которой рост AL сопровождается медленным ростом А Г, а после AT резко возрастает. Очевидно, что при этом невыгодно стремиться к максимальному выигрышу в памяти, целесообразно, если это возможно, выбирать структуру перекрытия с параметрами AL и AT, близкими к координатам критической точки, но несколько меньшими.

Характер кривой AT = f(AL) зависит от свойств логической структуры программы и особенностей решаемой ею задачи, которые определяют последовательность и частоту выполнения модулей, и может меняться при изменении характера потока данных. Поэтому имеет смысл строить и использовать кривую АГ = = f(AL) при выборе оптимальной структуры перекрытия для конкретного применения программы, которое характеризуется определенным потоком данных. Структура перекрытия, оптимальная для некоторого круга конкретных применений, соответствует точке пересечения характеризующих их кривых. Точность решения при таком подходе к оптимизации структуры перекрытия зависит от точности получения кривых. Построение кривой AT=f(AL) с высокой точностью — очень трудоемкий и дорогостоящий процесс, требующий тщательного подбора данных или сбора статистики, многократного построения структуры перекрытия при переборе структур с одинаковыми и различными значениями AL и многократного выполнения программы с целью определения параметра AT для каждой структуры. На практике, как правило, нет необходимости получать точное решение, важнее получить его быстро. При этом целесообразно для выбора оптимальной структуры перекрытия применять быстродействующие приближенные алгоритмы, основанные на приближенных оценках затрат времени на загрузку перекрываемых сегментов.