Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
2005 г.

Анализ и оптимизация циклов с помощью производящих функций

Довгалюк П.М.

Труды Института Системного Программирования РАН, 2004 г.

Аннотация

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

Введение

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

В данной статье рассматривается метод оптимизации циклов следующего вида с помощью производящих функций:

для ∀ v ∈ V | v = v → C
While (P)

для ∀ v ∈ V | v = T(v, C)

где:

V – множество переменных, используемых в цикле, N – мощность этого множества

C – множество констант

V → C – множество начальных значений переменных, используемых в цикле

P – предикат, сигнализирующий об окончании цикла, представляющий собой результат применения логических и алгебраических операций к переменным из множества V и константам из множества C

T(V, C) – множество функций преобразования элементов множества V, используемых в цикле

Описание метода

Производящая функция последовательности {an}, n>=0 – формальный степенной ряд:

img01

Переход от последовательностей к их производящим функциям позволяет заменить операции над последовательностями операциями над их производящими функциями. 

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

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


где i – номер итерации

t – функция преобразования переменной v, принадлежащая множеству T

Vi-1 – значения переменных, полученные на предыдущей итерации

Vi – значения переменных, полученные на текущей итерации

Производящие функции (или выражения для vi) достаточно просто можно получить для присваиваний вида:

img03

В этом случае для получения выражения для vi достаточно подставить выражения для всех остальных переменных в правую часть или найти производящую функцию для f.

Пользуясь методикой из [2] каждый оператор присваивания вида img04 можно записать в виде алгебраического тождества, включающего производящие функции для переменных из множества V:

img05
где Fv(z) – производящая функция для переменной v

FV – множество производящих функций для переменных, принадлежащих множеству V

G – некоторая алгебраическая функция

Найти алгебраическое выражение (возможно содержащее в себе другие производящие функции) для производящей функции для f можно пользуясь линейностью производящих функций: производящая функция суммы равняется сумме производящих функций.

Для каждого из слагаемых существует следующий выбор:

  1. Производящую функцию можно определить непосредственно (например, если слагаемое представляет собой константу, умноженную на переменную) по таблице прозводящих функций из [2]
  2. Производящую функцию нельзя получить непосредственно. Например, ai - bi. В этом случае, необходимо подставить выражения для всех переменных (ai и bi), а затем найти производящую функцию для последовательности, которую генерирует это выражение при изменении i от 0 до бесконечности.
  3. Производящую функцию нельзя получить непосредственно (как в случае 2), но выражения для ai и bi (см. случай 2) невозможно получить без знания выражения для vi+1. В этом случае предлагаемый метод не работает.

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

Рассмотрим несколько примеров

1. Переменная, которая в каждой итерации умножается на константу и к результату прибавляется другая константа

img07
Найдем производящую функцию для данной последовательности

Отсюда можно получить алгебраическое выражение для v в зависимости от номера итерации:

для c1 = 1: img09 (*)
для c1 <> 1: img10

2. Линейная комбинация переменных

img11
где k – номер переменной (переменные с номерами меньше k изменились в текущей итерации, с номером большим k – будут изменены позднее)

Применяя манипуляции, подобные использованным в предыдущем пункте, можно получить следующий результат:

img12

Отсюда можно получить выражение для Vk(z), а из него – выражение для vki.

3. Многочлен от переменных, выражения для которых имеют вид (*)

img13

Метод, применяемый в предыдущих примерах здесь не сработает, поэтому необходимо выполнить подстановку выражений для vji в данную формулу, что приведет к появлению многочлена от i:

img14

Производящая функция для in не существует в простой форме, однако ее можно выразить через производящие функции для числа сочетаний:

Отсюда можно получить производящие функции для in:

i1:

i2: img17

и так далее.

Таким образом, производящая функция для vki будет иметь вид:

img18
где ri – коэффициент при in в R(i), а Ii(z) – производящая функция для in.

Выводы

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

1. Данный метод выполняет задачу, обратную описанной в [3, разд. 14.1.1] – т.е. заменяет инкрементальные вычисления вычислениями по формуле. Кроме того, в процессе анализа цикла с помощью данного метода можно найти все его индуктивные переменные.

2. Компилятор, проделав все вышеприведенные вычисления, может либо заменить результат вычислений на константу (если все параметры являются постоянными), либо использовать вместо цикла соответствующую формулу.

3. Если цикл, подобный вышеприведенному, является вложенным в какой-либо другой, то производящие функции для переменных из V можно использовать описанным выше способом при оптимизации главного цикла.

4. Данный метод, как и многие другие методы алгебраической оптимизации, может быть использован только для целых чисел из-за возможной потери точности или переполнения чисел с плавающей точкой.

5. Полученные выражения для переменных могут быть использованы при анализе зависимостей между переменными, определении псевдонимов, устранении общих подвыражений (в том числе и полученных при выполнении аналогичных действий в различных циклах), при устранении незначимых вычислений, при определении индуктивных переменных.

6. Аналогичный подход может быть применен при оптимизации некоторых видов рекурсивных вычислений.

Литература

  1. А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001

  2. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основание информатики: Пер. с англ. – М.: Мир, 1998

  3. S. Muchnick. Advanced compiler design and implementation, 1997

Новости мира IT:

Архив новостей

Последние комментарии:

Группа ЕСН купила РБК (1)
Monday 19.06, 11:46
Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...