1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 39
Текст из файла (страница 39)
Ершова «О программировании ариф- $5.2. ИСТОРИЧЕСКИЙ ОБЗОР »(етических операторов», опубликованной в Докладах Академии наук СССР (т. 118, № 3, 1958). В этой работе им было введено рассмотренное нами в главе 1 понятие ширины информационных связей в некотором сечении программы и решена (для частной постановки, обсуждавшейся в $ 3.3) задача получения упорядочивания дерева с наименьшей шириной.
Замкнутые схемы Лаврова. Принципиальный вклад в решение задачи об экономии памяти внес С. С. Лавров своей работой «Об экономии памяти в замкнутых операторных схемах», опубликованной в 1961 г. в 4-м номере «Журнала вычислительной математики и математической физики». Он ввел понятие операторной схемы, рассмотрел различные варианты распределения памяти как эквивалентные преобразования, состоящие в переобозначении величин, ввел понятие маршрута, канонического распределения памяти и графа несовместимости. В то же время в созданной им теории отсутствовали некоторые компоненты, что, в частности, не позволило ему репгить задачу экономии памяти в общем случае. В некотором смысле работу Лаврова можно рассматривать как попытку прямого обобщения алгоритма Штаркмана на максимально возможный общий случай.
Вернемся к демонстрации алгоритма, приведенной на рис. 5.4, а). Мы видим, что работа алгоритма состоит из двух частей: заполнение таблицы Т и выбор яовых обозначений величин на основе изучения таблицы. Обе этп части из конструктивных соображений объединены в один просмотр программы, но могут рассматриваться и раздельно. Преобразуем несколько таблицу Т так, чтобы ее можно было бы рассматривать отдельно от программы. Для этого достаточно номер команды вместо испольэовэния его как номера строки получившейся матрицы внести в позиции таблицы.
Таким образом таблица становится множеством пар — (команда, величина). При этом различаются состояния таблицы «до выполнения» л «после выполнения» команды. Для такого различения будем рассматривать соответственно пары (х, К) и (К, з), где К вЂ” команда, а х — величина. В результате у нас получается некоторое множество пар (рис.
5.5), которое Лавров называет множеством загрузки М. Смысл отнесения пар к множеству загрузки очевиден: (л, К)е=М означает, что значение х должно быть сохранено в момент, предшествующий выполнению К, а (К, х) означает то же для момента после выполнения К. Глядянамнон«ество аагрузки уже в нашем случае линейной программы, можно сформулировать ряд его свойств как конструктивной основы распределения памяти: 1.
Множество М строится движением по программе навстречу передачам управления: пары, содержащие величину з, начинают заноситься в М с момента появления х в качестве аргумента и перестают с момента появления х в качестве результата. г Гл. 5. ЗАключительный Анализ х гг гг гз В Х г6 гВ гя таких, что К, вырабаты- Х з г7 г6 вает х, Кю..., К„, не вырабатывают х, К„воспринимает х, а в программе любой К, окааывается В Х г77 г7У г77 преемником К,, (В = =.2,..., п). У Х г77 г67 у 5.
Маршрутные цепочки, содержащие одну и ту же величину, объединяРао. 5.5. МНОжЕСтВО ВаГРУаКВ В ПРОГРыаВЕ ются в связки ха к даа Р = хб'. ются в связки, характеризуемые (в случае линейных программ) общей начальной парой (К,х). Функция распределения памяти должна сохранять постоянное значение на всех парах относящихся к связке, которую Лавров называет областью действия. 6. Разным обла тям действия можно сопоставить одно и то же значение функции распределения памяти в том и только в том случае, если у них нет ни одной пары одинаковой ориентации с одной и той же командой. Распределение памяти, функция которого принимает разные значения уа разных областях, называется каноническим; Зафиксировав зти свойства множества загрузки, Лавров ищет класс операторных схем, позволяющий гарантировать корректность распределения памяти по указанным правилам.
Оказывается, для этого достаточно постулировать.свойство 1, которое для линейных программ выполняется автоматически, а именно, потребовать, чтобы любой оператор, от которого дости- 7 Х г6 гВ гя 2. Каждая пара в таблице Т соотносится одной из вновь назначаемых величин; другими словами, новое распределение памяти аадается как функция Ь, определенная на множестве М. 3. Множество загрузки по отношению к разным функциям распределения памяти обладает некоторой постоянной структурой, а именно: в нем можно усмотреть подмножества, на которых любая «конкретная» функция А должна сохранять х з з гу свое значение.
4. К таким подмножествам относятся прежде всего маршрутные цепоч- В Х гз гу гВ ки, последовательности пар (К,х) (х, Кз) (К„х)... ...(х,К„~) (К„„х) (х,К„), Х гя г76 г67 $5.2. нстогическии ОБ30Р жим оператор, воспринимающий л, был бы достижим от некоторого оператора, вырабатывающего х. Операторные схемы, удовлетворяющие этому свойству, Лавров называет эамкнузэмми. Маршрутная цепочка о величиной л есть не что иное, как информация, задающая начальный, транзитные и конечный операторы некоторого маршрута, реализующего информационную связь С помощью х. Уточнять, какому результату и какому аргументу сопоставлен х, Лаврову не надо, так как в его определении операторной схемы любая величина в любом операторе в качество аргумента или результата встречается не более одного раза.
Свойство 5) формулируется, естественно, в более общей форме, объявляя связанными маршрутные цепочки т и т', для которых существует последовательность цепочек т, т„..., и„, т', такая, что любые дзе соседние имеют общую либо начальную, либо конечную пары. Сравним свойство 6) с критерием несовместимости областей действия, данным в теореме 4 $2.3. Пусть в каноническом распре- делении памяти двум областям действия сопоставлены величины л и х'. Пусть Н(х), А(х) и Т(х) соответственно операторы, выра- батывающие х, воспринимающие х и транзитные для маршрутов, чьй информационные связи реализуются величиной х. Для замкнутых операторных схем критерием несовместимости по Лаврову является непустота множества (Н(х)() т(х) и А( ))() (Н(з') () т(л') () А(л')),(Н( ) () А( ') () () Н(") () А(х)). (*) В этих обозначениях критерий несовместимости для общего случая выглядит как непустота множества (Н(л) () Т(х)) () (Н( ') () т(з'));(т(х) () т( )).
Очень просто показать, что дая замкнутых схем (э*) вытекает из (~). Действительно, пусть Я вЂ” оператор принадлежащий каждому из двух маршрутов М,(х) и М,(у) в качестве транзитного или конечного операторов. Из начал этих маршрутов выберем оператор Н„ближайший к Я. Пусть он начинает маршрут Мг(х). Оператор Я является либо концом К маршрута М,(у), либо его транзитным оператором, т. е. от него достижим конец К этого маршрута. Тогда, очевидно, этот К достижим и от оператора Нд.
В силу замкнутости есть маршрут М(у), для которого Н, является либо начальным, либо транзитным оператором. Отсюда следует, что величины х и у. несовместимы. Таким образом мы установили, что . определение областей действия по Лаврову в точности соответствует определению компонент связности информационного графа, а его критерий ГЛ. 5.
ЗАКЛЮЧИТЕЛЬНЫИ АНАЛИЗ несовместимости эквивалентен общему критерию на множестве замкнутых операторных схем. Лавров не вводит инварианта, сохраняющегося при «корректных» перераспределениях памяти, постулируя вместо этого свойства «корректных» функций распределения памяти. У него две схемы окааываются эквивалентными, если существует корректное переобозначение величин, превращающее одну схему в другую. Фактически же для того, чтобы определитькорректность, Лаврову неявно нун«но потребовать неизмененности множества всех маршрутов исходной схемы. В корректных преобразованиях замкнутых операторных схем множество маршрутов не меняется, а стало быть, все перераспределения памяти окааываются обратимыми.
Заметим, что в нашем содержательном анализе задачи в $1.4 неаамкнутая схема появилась только в конце (пример 11), Конструктивным выражением теории экономии памяти у Лаврова явилась описанная на алголе процедура построения множества загрузки операторной схемы с ого разбиением на области действия. Общий случай. Первый вариант теории экономии. памяти для общего случая был изложен А.
П. Ерпювым в Докладах Академии наук СССР (т. 142, № 4, 1962) под названием «Сведение задачи распределения памяти при составлении программ к задаче раскраски вершин графов». Схема у Ершова задавалась также, как у Лаврова: множества операторов и величин, граф переходов двоичная матрица аргументов ))а,Д (а„. = 1, если 1-я величина является аргументом 1-го оператора) и аналогично устроенная матрица результатов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
