Использование техники частичных вычислений для
оптимизации
процессов обработки информации в
программных комплексах.
Евдокимов Алексей Викторович,
аспирант Ростовского Государственного Университета Путей
Сообщения.
Частичные вычисления – это техника, предназначенная для оптимизации процесса программных вычислений. Процесс программных вычислений представляет собой отображение входных данных на выходные:
,
где 
– статические данные, известные до начала вычислений;
– динамические
(исходные) данные программы;
– выходные данные.
Процесс
частичных вычислений преобразует (
в (
) вычислением всех статических данных на стадии компиляции.
Таким образом, полученная после преобразования с использованием метода
частичных вычислений программа является более эффективной, чем исходная.
Автоматическая
генерация программ.
Покажем возможность создания генераторов программ, преобразующих исходные программы с использованием метода частичных вычислений.
Метод частичных вычислений всегда порождает корректную программу:
out = [[ source]]S input
= [[int]] [source, input] = [[[[mix]] [int, source]
]] input = [[target]] input
Здесь int – интерпретатор,
mix – процедура частичных вычислений.
Таким образом, процесс автоматической генерации программ с использованием метода частичных вычислений описывается показанной далее последовательностью шагов.
1. Интерпретация исходного кода программы написанной на языке S.
2. Преобразование исходной программы с использованием методики частичных вычислений.
3. Генерация результирующей преобразованной программы на языке L.
Выражение [target] = [mix] int, source часто называется первой проекцией Футамуры и впервые описано в [1].
Приведем простейший пример использования данной техники частичных вычислений. В качестве примера рассмотрим оптимизацию процесса вычисления момента наступления следующего события в системе.
При вычислении с использованием простейшего генератора псевдослучайных величин, как правило, используется следующая формула генерации
, где 
– постоянные величины.
Случайная величина в диапазоне (0,1) получается
вычислением 
.
Далее равномерное распределение генерируется по формуле
.
Таким образом, методика частичных вычислений позволит на стадии компиляции преобразовать исходное выражение
к виду
,
где 
, позволяя обойтись без вычислительно сложной операции
деления на каждом шаге.
В программном комплексе [2], разработанном автором, закон распределения случайной величины поступления заявок в систему массового обслуживания или закон ее обслуживания при проведении имитационного эксперимента может быть задан с использованием формул, вводимых пользователем, и, как следствие, данная оптимизация может быть необходима. Рассмотрим развитие данной технологии.
Грамматика арифметического выражения, используемого в трансляторе, имеет вид:
E=F{+F|-F}
F=U{*U|/U}
U=T|-T
T=«(»E«)»|I|<число>
I=<идентификатор>|<идентификатор>”(“{E{,E}}”)”
Примем следующие обозначения.
Пусть исходные данные находятся в STR – входной строке.
Для построения алгоритма определим некоторый объект, представляющий собой лексический анализатор. Определим следующие методы объекта:
Lex.InitStr(STR) – выполняет начальную инициализацию анализатора;
Lex.Restart() – выполняет возврат анализатора на первую лексему;
Lex.GetToken(TOK, TKL) – возвращает следующую лексему по заданной входной строке и переходит на следующую лексему, TOK – следующая лексема, TKL - набор классов лексем;
Lex.NextToken(TOK, TKL) – возвращает следующую лексему по заданной входной строке и не переходит на следующую лексему, где STR – заданная входная строка.
Набор классов лексем TKL.
1. Арифметическая
операция (+,-,*,/).
2. Идентификатор.
3. Число.
4. Скобка
«(» или «)».
5. Символ
«,».
Построим формальный алгоритм разбора заданной грамматики по методу рекурсивного спуска. Далее построим алгоритм, реализующий разбор данной грамматики по методу рекурсивного спуска, использующийся в процессе работы для трансляции исходного выражения. Алгоритм использует развитие техники частичных вычислений, разработанное нами применительно к нашему транслятору.
В алгоритме также будет применяться процедура Транслировать_выражение(), относящаяся к непосредственной реализации процедуры трансляции и в данной статье не описываемая. Процедуры трансляции широко описаны в [3] и предметом нашего исследования не являются.
Также используется функция Семантическое_действие(тип действия, параметр1, параметр2). Эта функция выполняет семантические действия над аргументами, не выполняя трансляции, а генерируя результат непосредственно в выходной поток.
В алгоритме используется переменная Static, которая может принимать либо значение вычисленного выражения, либо null, если таковое не определено.
Процедура E(Static)
Определить переменную StaticAll;
Вызов F(Static);
StaticAll := Static;
Lex.NextToken(TOK, TKL);
Пока
(TKL=1) и ((TOK=’+’)
или (TOK=’-’))
Lex.GetToken(TOK, TKL);
Вызов F(Static);
Если (Static<>null)
и (StaticAll<>null)
тогда
StaticAll:=Семантическое_действие(TOK, Static, StaticAll)
иначе транслировать_ выражение(); StaticAll=null;
Конец Если
Lex.NextToken(TOK, TKL)
Конец Пока
Static := StaticAll
Конец процедуры E
Процедура F(static)
Определить переменную StaticAll
вызов U(Static)
StaticAll := Static;
Lex.NextToken(TOK, TKL);
Пока
(TKL=1) и ((TOK=’*’)
или (TOK=’/’))
Lex.GetToken(TOK, TKL);
Вызов U(Static);
Если (Static<>null) и (StaticAll<>null)
тогда StaticAll
:=
Семантическое_действие(TOK, Static,StaticAll)
иначе Транслировать_ выражение(); StaticAll = null;
Конец Если
Lex.NextToken(TOK, TKL)
Конец Пока;
Static := StaticAll;
Конец процедуры F
Процедура U(Static)
Lex.NextToken(TOK, TKL);
Если (TKL=1) и ((TOK=’-’) тогда
Lex.GetToken(TOK, TKL);
Вызов T(Static);
Если
(Static<>null) тогда
StaticAll :=Семантическое_действие(TOK, Static, null)
иначе транслировать_ выражение();
Конец Если (Static<>null)
иначе Вызов T(Static)
Конец если (TKL=1)
Конец процедуры U
Процедура T(Static)
Lex.NextToken(TOK, TKL);
Если (TKL=4) и ((TOK=’(’) тогда
Lex.GetToken(TOK,TKL);
Вызов E(static);
Lex.GetToken(TOK,TKL);
Если (TKL<>4)
или ((TOK<>’)’)
тогда
Синтаксическая_ошибка («ожидается )»)
Конец Если
иначе Если TKL=3
тогда Static := Семантические _действия (null, TOK, null);
иначе I(Static);
Конец Если;
Конец процедуры T
Процедура I(Static)
Определить переменную StaticAll;
Определить переменную Id;
Lex.GetToken(TOK, TKL)
Если (TKL<>2) тогда
Синтаксическая_ошибка(«ожидается идентификатор »)
Конец Если;
Lex.NextToken(TOK, TKL);
Если (TKL=4) тогда
Lex.GetToken(TOK, TKL);
Lex.NextToken(TOK, TKL);
Пока (TKL<>4) и (TOK<>”)”)
Lex.GetToken(TOK, TKL);
Вызов E(Static);
Если Static=null тогда
StaticAll:=null;
Конец Если;
Lex.NextToken(TOK, TKL);
Если (TKL<>4 или TOK<>”)”) и TKL<>5 тогда
Синтаксическая_ошибка(«Ожидается ) или ,»);
Конец Пока;
Lex.GetToken(TOK, TKL);
Если StaticAll<>null тогда
Static := Семантические_действия (id, StaticAll, null);
Конец Если
Иначе Static:=Семантические_действия(null, TOK, null);
Если Static=null тогда Транслировать_выражение();
Конец Если (Static=null);
Конец Если (TKL=4);
Конец процедуры I
Алгоритм помимо синтаксического разбора выражения производит преобразование выражения, производя частичные вычисления на этапе разбора. Произведение частичных вычислений элемента выражения возможно только в случае если все узлы, находящиеся ниже в дереве синтаксического разбора, также частично вычислимы.
Пример 1 (примеры приведены на языке Pascal).
Var
GlobalVariable
: integer;
function
X(A:integer):Integer;
begin
GlobalVariable:= GlobalVariable+1;
A:=A+ GlobalVariable;
Result:=A;
End;
Функция X() в примере 1 не является частично вычислимой, так как на этапе синтаксического разбора не известно значение ни переменной A ни переменной GlobalVariable.
Пример 2
Function
A(X : integer) : integer;
Begin
result:=2+X;
End;
Function
B(X:integer):integer;
Begin
result:=2*A(X)+5*A(X);
End;
Функции, приведенные в примере 2, являются частично вычислимыми и могут быть преобразованы путем последовательных преобразований синтаксического дерева.
Шаг
1
Function
AB1(X:integer);
Begin
Result:=2*(2+X)+5*(2+X)
End;
Шаг
2
Function
AB2(X:integer);
Begin
Result:=4+2*X+10+2*X
End;
Шаг
3
Function
AB3(X:integer);
Begin
Result:=14+2*X+2*X
End;
Шаг
4
Function
AB4(X:integer);
Begin
Result:=14+4*X;
End;
Описанный алгоритм преобразования использует стек для хранения дерева синтаксического разбора, а также позволяет производить оптимизацию выражений, вводимых пользователем на стадии трансляции, значительно ускоряя процесс имитационного моделирования систем и сетей массового обслуживания.
Литература.
1.
Futamura
Y. Partial evaluation of computation process – an approach to a compiler /
Systems, Computers, Controls, 2(5):45-50, 1971.
2. Ахо А.В., Сети Р., Ульман Д.Д. Компиляторы: принципы построения, технологии и инструменты. – М.: Изд. дом «Вильямс», 2003 -768 с.
3.
Евдокимов А.В.
Прикладной пакет для имитационного моделирования систем массового обслуживания.
Свид-во о гос. регистрации № 70200600585, свид-во об отраслевой регистрации
разработки № 8038, 2007.
Поступила в редакцию 11
февраля 2008 г.