Рекуррентные соотношения и построение экономных циклических программ

• Автор: Зима, Евгений Викторович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 134 c. : ил

ГЛАВА I Экономия арифметических операций в циклах и

системы рекуррентных соотношений

§ I Постановка задачи

§ 2 Системы рекуррентных соотношений

§ 3 Построение систем рекуррентных соотношений

§ 4 Организация цикла с помощью систем рекуррентных

соотношений

§ 5 Реорганизация циклов в программах с помощью

построения систем рекуррентных соотношении

ГЛАВА 2 Преобразование выражений,связанных с системами

рекуррентных соотношений 52 '

§ I Элементарные преобразования выражений,связанных
с системами рекуррентных соотношений
§ 2 Преобразования,использующие свойства
коммутативности и ассоциативности
§ 3 Преобразования,использующие свойство
дистрибутивности
§ 4 Эквивалентность выражений,связанных с системами
рекуррентных соотношений
§ 5 Подстановки
ГЛАВА 3 Вопросы реализации
§ I Типы данных
§ 2 Основные процедуры и функции
ЛИТЕРАТУРА

Реализация многих численных методов предполагает организацию вычислений по сложным формулам.Часто вычислительные формулы являются итерационными и для их реализации требуется цикл.Ясно, что конкретный вид этих формул существенно влияет на сложност-ные характеристики (время выполнения,объем требуемой памяти) будущей программы.Поэтому актуальной является задача приведения данных вычислительных форвяул к такому виду,который задает способ экономной организации вычислений в цикле.
Некоторые аспекты этой проблемы рассматриваются в работах по оптимизации программ £ 1 ~ 12,^ .Основными оптимизационными преобразованиями для циклов,используемыми в системах оптимизации программ,являются чистка циклов [1-3,11] и преобразование рекурсивно определяемых переменных [ 1 Д,1<Ц .Процедура чистки циклов уменьшает время выполнения цикла путем удаления из его тела арифметических выражений или их частей,не зависящих от управляющей переменной цикла.Процедура преобразования рекурсивно определяемых переменных в ряде случаев приводит к замене медленно выполняемых машинных команд более быстрыми.
^Рекурсивно определяемая переменная - это переменная,значение которой при каждом выполнении цикла увеличивается или уменьшается на постоянную величину.В циклах,содержащих выражения, использующие такие переменные.есть возможность замены операции возведения в степень умножением и умножения - сложениемД Кроме того,в системах оптимизации программ часто применяется процедура оптимизации выражений [*5,6, і2. .суть которой состоит в поиске в программе семантически эквивалентных подвыражений и размещении их таким образом,чтобы избежать дублирования вычислений. Такая процедура особенно эффективна,когда с помощью ее

применения удается избежать повторения вычислений в цикле.
В данной работе задача экономной организации вычислений в циклах ставится более широко и решается более общими методами. Именно,пусть имеется набор итерационных вычислительных формул. Естественное желание построить вычисления так,чтобы на каждом итерационном шаге по возможности полнее использовались результаты предыдущих шагов,приводит к задаче сопоставления исходным формулам систем рекуррентных соотношений,определяющих те же вычисления. Пусть Ъ и I - набор переменных и требуется вычислить значения функции ^ (£,1
целочисленные переменные^) .Если этой функции можно сопоставить рекуррентное соотношение
|(2.где
|(г,т)=уо(г) |(2,ш+Н)='0-1^*
и вычисление правой части (]}) при известных проще,чем непосредственное вычисление -|-(5г,б) для каждого I , то это рекуррентное соотношение дает нам способ более экономной, по сравнению с непосредственным вычислением,организации цикла. Простейшие примеры зависимостей вида (/.)
Итак,задача состоит в автоматическом построении по данным вычислительным формулам рекуррентных соотношений и в исследовании способов получения по возможности лучших (^с точки зрения экономии^) соотношений.В диссертации эта задача решается сначала для отдельной функции »значения которой необходимо

вычислить при (у~Ш,П1+1гп,И .Затем решение распространяется на произвольный набор формул.
В первой главе выделяется некоторый класс систем рекуррентных соотношений (^СРс) ,а затем предлагаются методы сопостав-

которым можно сопоставить смешанные системы и вместо которых эти системы можно подставлять в правые части выражений в .
Таким образом,после выполнения некоторых подстановок [Ъ-.ТЛ) преобразуется к виду
■bi
• I I
> •••' 4VЛ°.--Л ,
где WjK - переменные ИЗ { (Л [j-i}K ^ ,оставшиеся после подV ® /У’
становок в правой части оператора для Zj ; xj ± ij
(К) . б-"
J . (2,0 tj~ Л-v ^ - некоторые системы рекуррентных
Г4-*
соотношений,вообще говоря новые;. Д|. , j,Ц - выражения,оставшиеся от после построения СРС.Теперь для организации нового цикла можно воспользоваться простейшим методом реорганизации циклов с несколькими операторами присваивания в теле цикла, который описан непосредственно после соотношений (4 .Д2.) (стр. к 5).
ЗАМЕЧАНИЕ 3. Задача выяснения по выражению вида (l,20) »сопоставляется ли переменной смешанная СРС (т.е. задача распознавания сводимости СРС общего вида к смешанной системе ^ связана с некоторыми преобразованиями выражения,операндами которого служат СРС.Поэтому решение этой задачи будет рассматриваться во второй главе.
ЗАМЕЧАНИЕ 4. Если СРС,сопоставленная переменной .подставляется в (LЛЪ) в выражение для переменной Z к ,то при К (т.е. когда выполняется подстановка "вперед" ) .система подставляется в том виде,в котором она была построена.Если же К (т.е. выполняется подстановка "назад" ^,то подставляется СРС, полученная из данной сдвигом на один шаг назад ( без изменения начального значения параметра цикла -иг - в записи системы j.