1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 36
Текст из файла (страница 36)
Кстати говоря, забывание этого факта — одна ий распространенных методологических ошибок в исследованиях, лежащих на стыке между теорией и практикой. После этих общих слов вернемся к нашей задаче. Прежде всего мы подчеркнем, что то, с чем читатель поанакомился,— это еще только исследование, а не решение прикладной задачи.
Как пример полного решения, наше изложение не имеет ни начала, ни конца, хотя те этайы, через которые мы прошли в первых четырех главах, являются неотъемлемой и главной частью работы. Говоря об экономии памяти как о прикладной задаче, мы прежде всего должны были бы представить тот реальный процесс, человеческую или иную деятельность, в которой возникает рассматриваемая задача. В нашем случае это могло бы быть конструирование транслятора с некоторого алгоритмического языка, в котором мы хотели бы организовать автоматическую экономию памяти в транслируемых программах. Другим примером могла бы быть разработка конкретной библиотеки программ для бортового вычислителя са-. молета, где малый объем оперативной памяти требовал бы ее максимальной экономии.
Связь с реальными программами. Анализируя упомянутый процесс, в котором требуется решение задачи об экономии памяти, мы, во-первых, должны были бы научиться строить операторные схемы, отправляясь от того вида программ, в котором они требуют экономного распределения памяти для своих величин. В случае транслятора зто мог бы быть либо начальный вид программы, вы Гл. ». ЗАключ11твльный АКАлиз раженной на входном алгоритмическом языке, либо некоторая промежуточная форма внутреннего представления программы во время трансляции, либо, наконец, упомянутая в з 1.1 символическая форма машинной программы. Для каждой из таких форм нам надо было бы найти правила выделения операторов, их аргументов и результатов вместе с сопоставленными им величинами, а также указания всех возможных передач управления от одного оператора к другому.
Очень поверхностно мы затрагивали эти проблемы, рассматривая примеры в первой главе. На деле соответствующие правила должны быть точно определены и запрограммированы аналогично самим алгоритмам непосредственной экономии памяти. Изучение этой проблемы сразу же показало бы нам ограниченность нашей теории. Главных пробелов у нас два. Первый — это наличие в реальных программах величин с индексами, обозначающими компоненты векторов, матриц и вообще многомерных массивов. Спрашивается, что считать аргументами и результатами оператора сП, 1[: = с[1, у[ + а[1, Ь[ Х Ь[[с, 1[? (А) Один из ответов на этот вопрос, например, таков, что если мы все равно не можем проследить, каковы значения индексов, мы будем считать, что аргументами и результатами оператора такого рода являются все массивы целиком, т.
е. как будто оператор имеет вид с:=Р(с, а, Ь). (В) Не углубляясь в проблему по существу, отметим только, что задача экономии памяти кри наличии массивов заметно усложняется. Вот два каверзных вопроса: (1) Есть массив М из 30 ячеек памяти и два массива К и 1, по 10 ячеек каждый.
Массивы К и 1. не совместимы друг с другом, но совместимы каждый с М. Если экономия памяти будет делаться путем склеивания вершин графа несовместимости, то после вклеивания, скажем, К в М массив Ь станет несовместимым с массивом М. В то же время очевидна такая экономия, когда массивы К и 1, налагаются оба на разные участки массива М размерами по 10 ячеек каждый. Как учитывать такие специфические совмещения массивов разной длины, которыми, естественно, не хотелось бы пренебрегатьг (2) Присваивание величине х, т.
е. обнаружение ее в качестве результата оператора, имеет в схеме программы двойное назначение: оно обязательно прерывает некоторый маршрут, так как х в результате присваивания, как говорят в американских статьях, «получает новую жизнь» и, возможно, начинает новый маршрут этой величины. Это свойство присваивания играет фундаментальную роль для всей теории. Если мы буквально применим это толкование присваивания к оператору (В), который в схеме был бы В КЬ СВЯЗЬ С ТЕОРИЕЙ И ПРАКТИКОЙ ' образом оператора (А), ваятого, скажем, из программы перемножения матриц, то мы совершим грубую ошибку.
Действительно, присваивание некоторой компоненте с[1, П массива с хотя и означает, что массив с стал «другим», однако он все же стал ие настолько другим, чтобы прервать информационные связи от других выработанных ранее компонент этого же массива к их более поадним исследованиям. Второй пробел — это учет существования подпрограмм, работающих при равных вызовах с разными величинами.
В примере 11 з 1.4 мы вывернулись, используя в обращениях к процедуре вещ проц У(г) два вызова с одним и тем же фактическим параметром Р(х). Попробовав начать сразу с общего случая, мы столкнулись бы с немалыми трудностями. Укрупнение операторов. Другой источник альтернатив в правилах выделения операторов, аргументов и результатов возникает при рассмотрении нап1его исследования с другого конца — фактической реализации найденных алгоритмов зкономии.
Элементарный анализ составленной программы показывает, что экономия памяти характеризуется большим объемом вычислений. Вычисление матрицы смея1ности 0[1: 1, 1: П графа несовместимости по ааданным матрицафначальных В[1: 1, 1: и) и транзитных Т[1: 1, 1: п! операторов (3 4.5) требует Рх и действий, где 1 — число областей действия, а п — число операторов. Нахождение канонического распределения памяти н транзитных операторов требует вычисления д + 21 транзитивных замыканий.
В то же время, если считать в машинных командах, число алементарных операторов в символических программах исчисляется многими сотнями, а стало быть, общий объем вычислений будет выражаться десятками и сотнями миллйонов машинных операций. Поэтому желательно переход от команд программы к операторам схемы сделать не таким буквальным: по возможности укрупнить операторы и сократить число величии, подлежащих акономии по общему алгоритму. Опять-таки, не входя в детали, рассмотрим возможные пути укрупнения операторов.
Если рассматривать хорошо организованные и, так сказать, реальные программы, то в них всегда можно ааметнть такие участки, гдевычисления идутеподрядэ,не прерываясь передачами управления. Эти участки так и называют линейными участками программы. При абстрактном рассмотрении программ в1виде графа переходов соответствующиецепочки вершин называются линейными компонентами графа. Более точно, линейной компонентой называется такая цепочка вершин графа, которая не содержится целиком ни в какой другой цепочке.
Возьмем любую такую компоненту и разделим все относящиеся к ней полюсы на три категории. Мы назовем аргументами линейной компоненты 1 такие аргументы а, для которых существуют маршруты информа ционных пар вида (г1, а), содержащие хотя бы один оператор, не- Гл. 5. 3Аключитильньгй АнАлиз г т Рис. 5.1. Редукция линейных компонент графа певеходов. а) До редукции: 35 операторов, 26 областей действия. б) После ред) 14 операторов, 10 областей действия. Ь ЬЛ.
СВЯЗЬ С ТЕОРИЕЙ И ПРАКТИКОЙ 173 принадлежащий (. Аналогично, результатами компокенты ( называются такие результаты г, для которых существуют маршруты информационных пар вида (г, ат), содержащие хотя бы один оператор, не принадлежащий (. Все остальные полюсы характерны тем, что маршрутыих информационных пар целиком содержатся внутри 1. Такие информационные пары естественно назвать внутренними, а сопоставленные им величины тоже внутренними, или локальными. Совершенно очевидно, что заняться совмещением локальных величин друг с другом в пределах линейной компоненты можно с помощью гораздо более простых правил, рассмотренных в З 1.2.
Осуществив такую внутреннюю экономию локальных величин каждой компоненты, мы можем потом для всех зтих величин отвеети один участок памяти, по длине равный максимальной ширине информационных связей внутренних величин, найденной среди компонент. После этого операторная схема подвергается редукции, состоящей в замене каждой линейной компоненты 1 одним оператором, аргументами и результатами которого являются только что определенные нами аргументы и результаты компоненты (. Кстествонно,чтопритакомподходе существенно сокращается число как операторов, так и полюсов, формирующих операторную схему.
На рис. 5Л показан пример редукции линейных компонент исходной операторьой схемы в укрупненные операторы. Факторизация. Непосредственным обобщением етого подхода является факторизация операторной схемы на так называемые гамаки. Гамаком называется такой подграф д графа С (в данном случае графа переходов), для которого существуют две принадлежащие ему вершины, а (вход) и г (выход), обладающие следующими свойствами: — все дуги из а ведут в гамак; — любой путь, ведущий в гамак извне, проходит через а; — все дуги в з идут из гамака; — любой путь, идущий из гамака вовне, проходит через з.
Гамак интересен тем, что его можно «стянуть» в одну вершину, Йе нарушая отношений смежности между остальными вершинами графа. Можно, далее, определить минимальный гамак, как гамак, ие содержащий в себе никакого другого гамака. Для гамаков, так же как для линейных компонент, можно определить их аргументы, результаты и внутренние величины. Выделение гамаков и линейных компонент позволяет рааложить (факторизовать) глобальную зкономию памяти в пределах всей операторной схемы иа следующие этапы. Сначала в схеме вьщеляются линейные компоненты, в пределах которых производится зкономия локальных величин по упрощенным правилам. После этого в схеме выделяются минимальные гамаки (по отношению к которым только что обработанные линейные компоненты уже ГЛ.
5. ЗАКЛЮЧИТЕЛЬНЫИ АНАЛИЗ 174 редуцированы в элементарные по отношению к гамакам вершины) Для каждого гамака задача экономии памяти решается отдельно в отношении его локальных величин, после чего эти гамаки 1-го ранга редуцируются в вершины — элементарные операторы по отношению к остальной схеме. В полученной схеме снова выделяются линейные компоненты и, стало быть, только что описанный двухчастиый этап повторяется снова. Этот процесс повторяется до тех пор, пока после очередной редукции схема не превратится в одну или несколько иаолированных вершин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
