1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 38
Текст из файла (страница 38)
Во-вторых, нам надо было бы более детально проанализировать баланс между расходом памяти и расходом времени при экономии памяти. Для каждой задачи есть свои нижние оценки временнбй или емкостной сложности, неуменьшаемое время работы, несокращаемые объемы памяти. Однако за пределами этих абсолютных оценок можно экономить на одном за счет другого. Например, мы могли бы вовсе не формировать матрицу В (з 4.5), извлекая нужное множество начальных операторов из распределения полюсов всякий раа, когда в нем возникает потребность. При построении ка- 9 кх истогическин ОБ30Р 179 ионического распределения памяти Я 4.4) мы, наоборот, могли бы для каждой исходной величины из числа хп..., з построить заранее множество воспринимающих ее операторов, образовав из соответствующих шкал матрицу порядка т Х п, сократив время, затраченное на построение аргументных множеств, в д/т раз (по одному разу на каждую величину вместо по одному разу на каждый результат).
Подобного рода конструкторские вопросы нужно решать с учетом того реального контекста, в котором применяется алгоритм экономии памяти. Наконец, даже находясь в заданных рамках общей организации алгоритма, мы могли бы придумывать разные приемы повышения эффективности нашего алгоритма. От одного ухищрения мы не удержались, когда построили вектор аргументных полюсов а в расчете на наиболее частйй случай однократного вхождения величины в оператор в качестве аргумента. Например, мы могли бы сильно сэкономить на времени построения графа несовместимости, задавая в качестве начального значения его компонент не нули, а результат перемножения множеств В> на Вп где В; — множество начальных операторов 7-й величины канонического оператора.
Это позволяло бы нам в ряде случаев даже н не начинать проверку непустоты пересечений множеств типа В Д Т. Сам процесс попарного перемножения множеств можно было бы прерывать немедленно по обнаружении ненулевого произведения компонент. Подобного рода усовершенствования многими воспринимаются как наиболее «аппетитная» часть программирования, отражающая его изобретательный и творческий характер. На самом же деле тодько целесообразность, к тому же правильно понимаемая, может быть судьей во внутренних спорах по поводу оснащения «основного» хода вычислений специальными приемами.
В каждом случае желательно иметь оценку улучшения показателей программы при учете различных особых случаев. Истинное чувство меры в соотношении достоверной простоты и менее надежной изощренности приходит только с опытом и зрелостью, как и в каждом видо творческой деятельности. й 5.2.
Исторический обзор . Рассказывая о задаче экономии памяти, автор подчинил способ изложения дидактическим целям в попытке сочетать полноту рассмотрения с естественностью в развитии темы. И хотя в целом решение задачи является довольно элементарным, оно опирается на ряд нетривиальных идей, до которых оказалось не так просто додуматься. От первой практической постановки задачи до соадания полной теории в ее наиболее естественном выражении прошло свыше десяти лет, а процесс ее обобщения на более сложные классы операторных схем продолжается е>це и сейчас.
180 гл. ». 3«ключительиыи АнАлиз Мы заключим наше рассмотрение задачи об зкономии памяти раабором работ, приведших к ее решению и взятых в нх временнбй последовательности. Этот исторический обзор будет не полон, он ограничен работами, лишь непосредственно повлиявшими на создание теории, либо так же непосредственно использовавшими ее результаты. Алгоритм Штаркмана. Первой работой, рассматривающей экономию памяти как самостоятельный этап в процессе программирования, была статья В.
С. Штаркмана «Блок экономии рабочих ячеек в ПП-2», опубликованная в иазестном 1-и выпуске «Проблем кибернетики» (М., Физматгиз, 1958), утвердившем становление научных основ программирования в СССР. В работе, по ' существу, полностью решена задача экономии внутренних величин па линейных участках программы. Эта аадача рассматривается в контексте работы транслнтора (называвшегося в то время программирующей программой — ПП), формирующего линейные участки машинной программы для трехадресной ЭВМ при трансляции арифметических операторов исходной программы.
Идея алгоритма изложена в работе настолько ясно, что мы просто предоставим слово автору. «...Рабочими ячейками в ПП-2 называются ячейки, предназначенные для хранения промежуточных результатов. т. е. таких результатов, которые используются в данном операторе и не используются ни в каком другом операторе. Из саыого такого определения, очевидно, следует, что ячейки, являющиеся рабочими для одного оператора, могут с успехом использоваться как рабочие н в другом операторе. Совершенно очевидно, что общее число нужных в программе рабочих ячеек равно максимальному числу рабочих ячеек по всем операторам программы.
Отсюда следует, что для экономии рабочих ячеек в программе нужно экономить их для каждого оператора в отдельности. ... Назовем областью существования промежуточного результата совокупность' приказов, при выполнении которых мы не можем использовать ячейку, хранящую данный промежуточный результат, для хранения другого результата. Такая совокупность, очевидно, начинается с приказа, породившего результат, и ааканчивается приказом, выполняющимся перед последним приказом из числа тех, которые данным результатом пользуются. Очевидно, что промежуточные результаты с непересекающимися областями существования безболезненно могут помещаться в одну и ту же ячейку паыяти. ...Экономия рабочих ячеек...
осуществляется за один «просмотр» оператора следующим образом. Все приказы оператора последовательно перебираются снизу вверх, начиная с последнего и кончая первым. В процессе перебора ведется таблица (Т), где $»Л. ИСТОРИЧЕСКИЙ ОБЗОР 1З« на каждом этапе перечислены, условные числа (символические обозначения.— А. Е.) тех промежуточных результатов, для которых очередной «просматриваемьпЪ приказ принадлежит их области существования. Делается это так: если в П1 (результатном— А. Е ) адресе приказа нам попадается условное число промежуточного результата, то в Т отыскивается строка, содержащая его, и очищается, если же условное число попалось в 1 и 11 адресах н «просмотр» Т показал, что его там нет, что отыскивается самая верхняя свободная строка Т и в нее записывается выбранное условное число.
И только в том случае, когда свободных строк внутри Т не окэзыиается, к ней присоединяется еще одна строка с выбранным условным числом. При такой системе, во-первых, в каждую строку Т попадают условные числа промежуточных результатов с непересекающимися областями существования, во-вторых, условные числа результатов с пересекающимися областями попадают обязательно в разные строки и, в-третьих, количество строк в Т в процессе просмотра, увеличиваясь с нуля, в конце достигает числа нужных нам рабочих ячеек.» Главной догадкой Штаркмана является организация экономии рабочих ячеек путем обратного просмотра команд оператора.
Тем самым маршрут калсдой величины обозревается, начиная с последнего использования. Это в точности соответствуеттребованию общей теории: находясь в пределах маршрута, данная величина конкурирует с результатами всех внутренних операторов. В общем случае множество внутренних операторов Т = ЕПЬ, где Š— это прямое, а Ь вЂ” обратное транзнтивные замыкания. Очевидно, что для линейной'программы Т = Ь, что и испольэовал П1та ркман. Алгоритм Штаркмана был усовершенствован при рааработке еще одного раннего транслятора, описанного в книге А.
П. Ершова «Программирующая программа для быстродействующей электронной счетной машины» (М., Изд-во АН СССР, 1958). В этом трансляторе, хотя и не вполне осознанно, была реалиаована идея явного указания информационных связей в пределах линейного участка программы. В терминах трехадресных команд это выглядело следующим образом: если при построении команд линейного участка в Й-ю по порядку ячейку направлялась очередная команда, то третий адрес у нее оставался незаполненным. В тех же (первом или втором) адресах последующих команд, которые должны были бы испольаовать результат 1«-й команды, ставился номер й. Это позволяло осуществлять экономное распределениепамяти не как переобозначение внутренних величин, а сразу как некоторое нааначение рабочих ячеек результатам и аргументам ее команд. При таком задании информационных связей алгоритм Штаркмана выглядел следующим образом.
Таблица Т имеет вид логн- $82 Гл. а. 3АключительныЙ АнАлиз ческой шкалы, так что Т П) соответствует 1-й рабочей ячейке. При просмотре очередной команды в Т помечены единицами занятые в данный момент рабочие ячейки. При обследовании аргументного адреса А очередной команды используется результатный 3-й адрес В команды, номер которой указан в адресе А. Если он пуст, то в шкале Т ищется первый ненулевой разряд, него номер задает рабочую ячейку, которая ставится в Л и в А.
Если Л не пуст, то это значит, что ему уже назначена указанная там рабочая ячейка, которая также направляется и в А. При обследовании результат- ного адреса текущей команды стоящая в нем рабочая ячейка отмечается в шкале Т как свободная. На рис. 5А показана работа т~ ттйй Рис. 54. Пример работы алгоритма Штаркмана. а) Оригияальвая форма.
б) Модификация а ПП для БЭСМ. алгоритма Штаркмана для линейной программы ъычксления у = х" (пример 5 из 8 1.2) как в оригинальной форме, так и в его модификации (внешние величины х и у не совмещаются с рабочими ячейками). На каждом этапе просмотра очередная команда и таблица Т изображаются дважды: команда со старыми и новыми обовначениями, таблица до обследования результатного адреса и после обследования. Экономия памяти в линейных программах получила дальней- шее развитие в работе А. П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
