ISSN 1991-3087
Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

НА ГЛАВНУЮ

Использование техники частичных вычислений для оптимизации
 процессов обработки информации в программных комплексах.

 

Евдокимов Алексей Викторович,

аспирант Ростовского Государственного Университета Путей Сообщения.

 

Частичные вычисления – это техника, предназначенная для оптимизации процесса программных вычислений. Процесс программных вычислений представляет собой отображение входных данных на выходные:

,

где      – статические данные, известные до начала вычислений;

 – динамические (исходные) данные программы;

 – выходные данные.

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

Автоматическая генерация программ.

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

Метод частичных вычислений всегда порождает корректную программу:

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 г.

2006-2019 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.