Аннотация

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

Введение

Существует множество методов оптимизации циклов. Большинство методов только изменяют структуру цикла, оставляя его в программе. Среди них выделяется метод оптимизации циклов, которые не выполняют никаких действий, кроме изменения некоторых переменных. Для этого используется интерпретация циклов на этапе компиляции, если количество итераций невелико [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, используемых в цикле

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для c1 = 1:

(*)

для c1 <> 1:

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

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

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

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

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

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

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

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

i1:

i2:

и так далее.

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

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

Выводы

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

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

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

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

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

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

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

Литература

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

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

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