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

Optimization of the output algorithm of the abstract syntax tree of the program from the reverse Polish record

Lukashenko Vladislav

Scientific employee of the department of ICT and MPI Ryazan State University named after S.A. Yesenin, Russia, Ryazan

Vitaly Romanchuk

Candidate of Technical Sciences, Associate Professor of the Department of ICT and MPI, Ryazan State University named after S.A. Yesenin, Russia, Ryazan

Аннотация. В работе рассматривается вариант реализации вычислительного кластера нейрокомпьютеров. Для реализации основного принципа распределенных вычислений в статье представлен алгоритм разбиения задач, поступающих на выполнение в вычислительный кластер нейрокомпьютеров, на подзадачи. Задача, которой посвящена статья – оптимизация алгоритма преобразования обратной польской записи программы в абстрактное синтаксическое дерево. Для этого в статье предлагается представить поступившую на выполнение в кластер программу в модифицированной постфиксной Польской записи и хранить ее в стеке команд программы. На следующем шаге предлагается получить абстрактное синтаксическое дерево программы, следуя оптимизованному алгоритму перевода модифицированной постфиксной Польской записи из стека команд в абстрактное синтаксическое дерево. Работа выполнена при финансировании государственного задания, проект №2.9519.2017/8.9.

Abstract. The implementation of the computational cluster of neurocomputers is considered in the article. To implement the basic principle of distributed computing, the article presents an algorithm for dividing the tasks included in the computing cluster of neurocomputers into sub-tasks. The task, which is devoted to the article, is the optimization of the algorithm for converting the inverse Polish program into an abstract syntax tree. For this, the article proposes to present the program entered into the cluster for execution in the modified post-entry Polish record, and store it in the stack of program commands. The next step is to get the abstract syntax tree of the program, following the optimized algorithm to translate the modified Polish postfix record from the command stack to an abstract syntax tree. The work was carried out with the financing of the state task, project N 2.959.2017/8.9.

Ключевые слова: распределенные вычисления; кластерные вычисления; кластеризация вычислительных ресурсов; нейровычисления; нейрокомпьютеры; кластеризация нейрокомпьютеров; оптимизация; оптимизация алгоритмов.

Keywords: distributed computing; cluster computing; clustering of computing resources; neuro computing; neurocomputers; clustering of neurocomputers; optimization; algorithm optimization.

Введение

В современной научной и производственной сфере крайне актуальна задача использования вычислительных систем параллельной обработки информации ввиду недостаточности вычислительных ресурсов. Сегодня обозначенные задачи решают с недостаточно высокой степенью эффективности масштабируемые параллельные вычслительные кластеры на базе нейрокомпьютеров [1]. В работе рассматривается существующая реализация параллельного кластера на базе нейрокомпьютеров MB77.07 ЗАО «НТЦ Модуль», технические характеристики и перспективы использования в работе которых, описаны в работе [2-4].

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

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

С теории компиляции всякая программа представляется в виде , где  - граф потока управления программы, а  - алфавит операторов.

Граф потока управления  - это ориентированный граф, в котором выделены две вершины start и stop, связанные между собой посредством множеств вершин W и дуг E.

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

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

Внутренняя форма представления программ - это результат работы синтаксического анализатора. Наиболее распространенным способом представления программ во внутренней форме является обратная польская запись [10,11].

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

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

Алгоритм перевода из Польской формы в абстрактное синтаксическое дерево

После представления программы в обратной Польской записи необходимо построить граф потока управления программы. Представление программы в расширенной обратной Польской записи хранится и передается в форме абстрактного типа данных класса стек. Такой стек называется стеком команд программы (Stack). На следующем шаге необходимо сформировать абстрактное синтаксическое дерево (АСД) программы из стека команд программы. Абстрактное синтаксическое дерево – это ориентированное дерево, где внутренние вершины являются операторами языка, на котором написана программа, а листьями — соответствующие операнды. Листья нижнего слоя – это входные параметры, а, в свою очередь, корень дерева - результат, который должна вернуть программа. Ребра АСД формируются между операторами и соответствующими операндами, требующихся для их работы. Для этого существует алгоритм перевода программы из Польской формы в абстрактное синтаксическое дерево (рисунок 1). Следует, отметить что скорость работы алгоритма перевода из обратной польской записи в абстрактное синтаксическое дерево крайне низка и требует оптимизации. В связи с этим рассмотрим оптимизованный алгоритм преобразования обратной польской записи программы в абстрактное синтаксическое дерево.

Будем хранить в R текущий считываемый из Stack элемент, до тех пор пока он не пуст.

· В случае, когда R - идентификатор или константа, его значение считывается из стека и записывается в лист АСД а также в многосвязный список ссылаясь на элемент родитель в дереве, затем переходим к считыванию следующего элемента.

· В случае, когда R является бинарным оператором, его действие осуществляется над двумя последующим элементам, которые являются операндам из стека, так формируется левое поддерево АСД. Затем переходим к считыванию следующего элемента.

· В случае, когда R является унарным оператором, его действие осуществляется над верхним последующим элементом стека, так формируется левое поддерево АСД. Затем переходим к считыванию следующего элемента.

· В противном случае R является n-арным оператором, его действие осуществляется над всеми n верхними последующими операндами, так формируется левое поддерево АСД. Затем переходим к считыванию следующего элемента.

Вывод

Таким образом, в статье рассмотрен вариант оптимизации алгоритма перевода программы, все операции которой, записаны в модифицированной обратной польской записи, в абстрактное синтаксическое дерево, который отобразит множество всех путей исполнения программы. Результатом работы данного алгоритма является алгоритмическая структура – многосвязный список, посредством которой осуществляется хранение и передача для дальнейшей обработки результатов представления программы в АСД. Работа выполнена при финансировании государственного задания, проект №2.9519.2017/8.9.