Рекуррентные соотношения и построение экономных циклических программ тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

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

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

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

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

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

§ 5 Реорганизация циклов в программах с помощью построения систем рекуррентных соотношений.

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

§ I Элементарные преобразования выражений,связанных с системами рекуррентных соотношений.

§ 2 Преобразования,использующие свойства коммутативности и ассоциативности.

§ 3 Преобразования,использующие свойство дистрибутивности.

§ 4 Эквивалентность выражений,связанных с системами рекуррентных соотношений.

§ 5 Подстановки.

ГЛАВА 3 Вопросы реализации.;.

§ I Типы данных.

§ 2 Основные процедуры и функции.

Реализация многих численных методов предполагает организацию вычислений по сложным формулам Лас то вычислительные формулы являются итерационными и для их реализации требуется цикл.Ясно, что конкретный вид этих формул существенно влияет на сложност-ные характеристики (время выполнения,объем требуемой памяти") будущей программы.Поэтому актуальной является задача приведения данных вычислительных формул к такому виду,который задает способ экономной организации вычислений в цикле.

Некоторые аспекты этой проблемы рассматриваются в работах по оптимизации программ £ 1 ~ 12,J .Основными оптимизационными преобразованиями для циклов,используемыми в системах оптимизации программ,являются чистка циклов [1-3,11] и преобразование рекурсивно определяемых переменных £ J .Процедура чистки циклов уменьшает время выполнения цикла путем удаления из его тела арифметических выражений или их частей,не зависящих от управляющей переменной цикла.Процедура преобразования рекурсивно определяемых переменных в ряде случаев приводит к замене медленно выполняемых машинных команд более быстрыми, (рекурсивно определяемая переменная - это переменная,значение которой при каждом выполнении цикла увеличивается или уменьшается на постоянную величину.В циклах,содержащих выражения, использующие такие переменные,есть возможность замены операции возведения в степень умножением и умножения - сложением.^ Кроме того,в системах оптимизации программ часто применяется процедура оптимизации выражений [" 5,6 ? 13- ,суть которой состоит в поиске в программе семантически эквивалентных подвыражений и размещении их таким образом,чтобы избежать дублирования вычислений. Такая процедура особенно эффективна,когда с помощью ее применения удается избежать повторения вычислений в цикле.

В данной работе задача экономной организации вычислений в циклах ставится более широко и решается более общими методами. Именно,пусть имеется набор итерационных вычислительных формул. Естественное желание построить вычисления так,чтобы на каждом итерационном шаге по возможности полнее использовались результаты предыдущих шагов,приводит к задаче сопоставления исходным формулам систем рекуррентных соотношений,определяющих те же вычисления. Пусть Z и L - набор переменных и требуется вычислить значения функции при -целочисленные переменные^ .Если этой Функции можно сопоставить рекуррентное соотношение f(2,lH({(?,l4.где и вычисление правой части (l^ при известных проще,чем непосредственное вычисление для каждого I , то это рекуррентное соотношение дает нам способ более экономной, по сравнению с непосредственным вычислением,организации цикла. Простейшие примеры зависимостей вида (i) : = ОС.^ ОС ? ь/»(1-i)M , Mi = (i-i>h + h.

Итак,задача состоит в автоматическом построении по данным вычислительным формулам рекуррентных соотношений и в исследовании способов получения по возможности лучших ^с точки зрения экономии^ соотношений.В диссертации эта задача решается сначала для отдельной функции .j!,значения которой необходимо вычислить при Ь~J7i?Ht+lr.,/t .Затем решение распространяется на произвольный набор формул.

В первой главе выделяется некоторый класс систем рекуррентных соотношений (^СРС) ,а затем предлагаются методы сопостав ления систем этого класса заданным формулам и,соответственно, методы построения программ по заданным формулам.

В § I определяются модели итерационных вычислений,которые будут рассматриваться в диссертации,и дается неформальная постановка задачи.В § 2 определяются типы рекуррентных соотношений, сопоставляемых тем функциям,значения которых необходимо вычислять в цикле,а также указываются некоторые полезные свойства систем рекуррентных соотношений.Наряду с СРС общего вида (JC) рассматриваются системы вида составляемые из заданных наборов функций и знаков операций Qjjm.^Gк (Gjf ^"tVMJi )«Система ввда СЯ) называется смешанной СРС,целое 1С - ее глубиной,а СРС для - подсистемой порядка J данной систеш.В классе смешанных систем выделяются подклассы простейших О -систем ^ системы вида (д^ ,в которых все Oj = О О G .

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

В § 3 описывается метод построения по арифметическому выражению с) .задающему функцию jj.(г, L),систем рекуррентных соотношений.Вначале определяются базовые операции,позволяющие при известных СРС,сопоставленных некоторым выражениям,получать новые системы,соответствующие более крупным выражениям.Построение систем рекуррентных соотношений,соответствующих данному выражению .проводится за один обход в концевом порядке бинарного дерева,задающего это выражение.Техника построения СРС иллюстрируется примерами.

В § 4 показано,как с помощью найденных для данной функции f-(^pi) систем рекуррентных соотношений можно построить оператор цикла для экономного вычисления значений этой функции.Разбираются соответствующие примеры.В § 5 показано,как методы из §§ 2-3 применяются для организации циклических программ по данным итерационным вычислительным формулам.Вначале рассматривается случай одной вычислительной формулы вида , затем случай нескольких вычислительных формул.Рассмотрен также случай, • • когда итерация проводится по нескольким параметрам I^ .

Базовые операции над СРС являются частичными,т.е. результат их применения не всегда определен.Поэтому построение по данной функции систем рекуррентных соотношений в общем случае приводит к выражению,операндами которого служат СРС.Непосредственное продолжение процесса построения новых систем для этого выражения невозможно.Можно попытаться продолжить построение СРС ^увеличив тем самым экономию вычислений^) выполнив предварительно некоторые эквивалентные преобразования выражения. Определению набора преобразований выражений,связанных с СРС,проведение которых позволяет продвинуть дальше процесс построения новых систем и получить при этом по возможности большую экономию вычислений,посвящена вторая глава диссертации.

Всевозможные эквивалентные преобразования выражений,связанных с СРС,разбиваются на две группы: f) преобразования,результат выполнения которых не зависит от конкретного вида функций if (z)r.f (?),входящих в имеющиеся системы,а зависит только от типов систем и их глубин (^т.е. преобразования,которые проводятся в предположении произвольности этих функций) ; 2) преобразования,результат выполнения которых существенно зависит от наборов таких функций,входящих во все имеющиеся системы. В §§ 1-3 обсуждаются преобразования первой группы,в § 4 -второй.

В § I дается формальная постановка задачи построения такого преобразования данного выражения,операндами которого служат -V-системы и X-системы,которое приводит к наибольшей экономии вычислений.Затем определяется набор элементарных преобразований, который по существу является набором некоторых базовых операций над СРС.В § 2 показано,как исходя из набора элементарных преобразований и преобразований,использующих свойства коммутативности- и ассоциативности сложения и умножения,построить по данному выражению преобразование,приводящее его к наиболее экономному виду.

В § 3 показано,как получить преобразование с аналогичным свойством,исходя из набора элементарных преобразований и преобразований, использующих свойство дистрибутивности умножения относительно сложения.Искомое преобразование строится поэтапно,и на каждом этапе решаются задачи,требующие перебора многих вариантов.Во всех случаях,за счет использования свойств. СРС,полного перебора удалось избежать ^ доказаны соответствующие теоремы^) . На одном, этапе построения число рассматриваемых вариантов сведено от nj (fl - количество пар скобок в данном выражении) к в худшем случае^ и доказана возможность применения бектрекинга, что, вообще говоря,позволяет сократить перебор.На остальных этапах задача построения искомого преобразования решается вообще без перебора.В конце § 3 предложенные методы построения преобразований распространены на выражения,операндами которых служат не только простейшие СРС,но и смешанные системы.

Преобразования второй группы,рассмотренные в § 4,основаны на поиске в выражении совпадающих СРС или систем с совпадающими подсистемами и на распознавании эквивалентности некоторых подвыражений (или СРС) нулю или единице.Центральное место здесь занимает выбор метода сравнения систем рекуррентных соотношений, т.к. при их сравнении возникает задача распознавания функциональной эквивалентности выражений.Предложено решение этой задачи,не выходящее за рамки рассмотренных методов построения СРС.Выделен класс выражений,в котором эта задача предложенным методом решается полностью.

В § 5 продолжено обсуждение вопросов^рассмотренных в § 5 первой главы.В частности,рассматривается задача сводимости СРС общего вида (l) к смешанной системе вида .Предлагается способ решения этой задачи,не выходящий за рамки методов построения СРС.Затем рассматривается случай нескольких вычислительных формул.Если некоторым переменным, стоящим в этих формулах в левых частях операторов присваивания,сопоставлены системы вида (i) »то можно рассматривать преобразования,состоящие в замене вхождений этих переменных в правые части присваиваний на соответствующие им СРС.После таких замен,вообще говоря,можно продолжить процесс, построения новых систем и получить дополнительную экономию вычислений.

В третьей главе обсуждаются некоторые вопросы реализации методов,рассмотренных в первых двух главах,и описывается структура реализующей эти методы Паскаль-программы.В § I обсуждаются используемые в программе типы данных.В § 2 описываются принципы построения программы и основные используемые процедуры и функции. Кроме того,приводятся результаты применения описанной программы к задаче сопоставления систем рекуррентных соотношений формулам,задающим вычисление значения определенного интеграла методом прямоугольников для различных подынтегральных функций.

Основные результаты работы представлены в [ 1Ъ и состоят в следующем.

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

Полученные результаты могут использоваться при создании систем оптимизации программ.Кроме того,их можно использовать для приведения получаемых с помощью систем аналитических преобразований ( ШОСЕ-Х ,M/\C£YMA) вычислительных формул к виду,определяющему экономный способ вычислений по этим формулам в цикле.

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

1. Поттосин И.В. Глобальная оптимизация практический подход.-В кн.: Тр. Всесоюз. симпоз. по методам реализации новых алгоритмических языков. 4.1. Новосибирск,1970,с. 1.3-I28.

2. Поттосин И.В. К задаче чистки циклов.-Цифровая вычислительная техника и программирование.М.: Сов. радио,1968 ,вып. 4, с. 18-36.

3. Поттосин И.В.,Югринова О.В. Обоснование преобразования чистка циклов.-Программирование,!980,JS 5,с. 3-16.

4. ЦШк F.F. Pliant OpiimiodlOK fimu*ol dzvUw ivi /fuiomaieol Рго^чяштц. Репчатой. P^ss. V.5., 19И, p.i-^3.

5. Архангельский Б.В. Алгоритм выделения в операторных схемах областей постоянства переменных.- Программирование,№ 4, 1979,с. 16-28.

6. Архангельский Е.В.,Никитин А.И. Об одном алгоритме реализации процедуры оптимизации выражений на уровне входного языка.» УСиМ,1976,Лз 5,с. 35-40.

7. Касьянов В.Н.,Поттосин И.В. Технологические возможности оптимизации программ.-Программирование,1980,}& 2,с. 27-30.

8. Архангельский Б.В. Некоторые оптимизацишные процедуры над оперативными схемами.-Программирование,!980,№ 3,с. 13-27.

9. Архангельский Б.В. Обзор оптимизационных процедур.- УСиМ, 1981,$ 4,с. 103-109.

10. Архангельский Б.В. Оптимизация программ на основе преобразования структуры программы и устранения избыточных вычислений.- УСиМ,1982,}$ 5,с. 35-41.

11. Архангельский Б.В.,Никитин А.И. Об одном алгоритме построения областей постоянства переменных.-Кибернетика,1976,$ 4, с. 134-137.

12. Архангельский Б.В.Никитин А.И. Системы оптимизации программ. К.: Техщка,1983.-167 с.

13. Зима Е.В. Автоматическое построение систем рекуррентных соотношений.- Журнал вычисл. матем. и матем. физ.,1984, 24,№ 12,с. 1897-1902.

14. Кнут Д. Искусство программирования для ЭВМ. т. I. М.: Мир, 1976.- 736 с.

15. Рейнгольд Э. ,Нивергельт 10. ,Део Н. Комбинаторные алгоритмы: теория и практика. М.: Мир, 1980.- 476 с.

16. Трифонов Н.П.,Пасхин Е.Н. Практикум работы на ЭВМ. М.: Наука, 1982.- 288 с.