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

КОМПЬЮТЕРНОЕ ОБЕСПЕЧЕНИЕ И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

DOI: 10.24143/2072-9502-2017-4-31-38 УДК 004.383.3

В. В. Лукашенко, В. А. Романчук

РАЗРАБОТКА АЛГОРИТМА РАЗБИЕНИЯ ЗАДАЧ НА ПОДЗАДАЧИ В СИСТЕМАХ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ ДАННЫ1Х

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

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

Введение

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

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

ботки модели вычислений рассматривается в [5]. Авторами [5] определен ряд алгоритмов, разработка которых необходима для реализации модели вычислений кластера нейрокомпьютеров. Одним из таких алгоритмов является алгоритм разбиения задач на подзадачи, необходимый для декомпозиции задач, поступающих в вычислительный кластер, что позволит реализовать основной принцип теории распределенных вычислений. Разработка такого алгоритма и явилась целью нашего исследования.

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

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

Программа PR(3 ), реализующая алгоритм Al(3 -1, представляет собой последовательность машинных операций. Однако для целей нашего исследования программу можно представить

в виде графа потока управления: PR(j) = (Gpu,V), где Gpu = (W,E,start,stop) - граф потока

управления программы, а V = (vj, ... ,vk} - алфавит операторов. Отметим, что на любом уровне

детализации операторы считаются атомарными.

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

- в start не входит ни одна дуга;

- из stop не выходит ни одна дуга;

- любая вершина достижима из start;

- из любой вершины достижима вершина stop.

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

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

В связи с этим граф потока управления программы будет представлен следующим образом: Gpu = (V, E, start, stop, BitVal), где BitVal - множество значений разрядности результатов на каждом шаге выполнения программы при обходе графа потока управления.

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

Внутренняя форма представления программ является результатом работы синтаксического анализатора. Различают следующие виды внутренних форм представления программ: постфиксная польская нотация, префиксная польская нотация, синтаксическое дерево, тетрады. Наиболее распространенным способом представления программ во внутренней форме является постфиксная польская нотация [6-8].

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

Модифицированный алгоритм фактически не отличается от традиционного алгоритма перевода. Однако для представления полной программы в состав операций требуется включить операции управления, назначив им соответствующие приоритеты (см., например, [8]). Такое представление будем называть модифицированной обратной польской нотацией.

Модифицированная обратная польская нотация

Рассмотрим включение в польскую нотацию других, отличных от арифметических, операторов и конструкций:

Безусловные переходы. Безусловный переход - это унарный оператор, который в польской нотации имеет следующий синтаксис:

<адрес перехода>$ит,

где $UT- знак операции, а операндом является адрес перехода.

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

- <операнд 1>< адрес перехода>$CBZ$CBlZ\$CBaZ$CBleZ\$CBaeZ

- <операнд 1> - значение арифметического выражения;

- <адрес перехода> - адрес перехода в таблице символов;

- $CBZ - код оператора перехода по значению 0;

- $CBlZ - код оператора перехода по значению меньше 0;

- $CBaZ - код оператора перехода по значению больше 0;

- $CBleZ - код оператора перехода по значению меньше или равно 0;

- $CBaeZ - код оператора перехода по значению больше или равно 0.

Описание массива. Описание массива - это «-арный оператор со следующим синтаксисом в польской нотации:

<элемент массива 1>... <элемент массива ><адрес> $ARRAY, где <элемент массива i> - адрес очередного элемента массива;<адрес>- в таблице символов хранит размерность массива;$ARRAY- код оператора.

Обращение к элементу массива. Обращение к элементу массива тоже является «-арным оператором, который в польской нотации может быть представлен таким образом: <выражение 1> ... <выражение ><адрес> $SUBS, где оператор $SUBS, используя <адрес> из таблицы символов и индексные выражения, вычисляет адрес элемента массива.

Вызов подпрограммы с аргументами. Вызов подпрограммы - это «-арный оператор со следующим синтаксисом в польской нотации: <аргумент !>...< аргумент г><имя функции> $CALL, где <аргумент i> - аргументы функции.

Начало и конец программы. В польской нотации - безоперандные операторы со следующим синтаксисом: $BEGIN $END.

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

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

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

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

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

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

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

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

На рис. 1 указаны следующие программные функции, посредством которых реализована работа указанных выше правил:

- isEmpty() - функция, которая проверяет наличие элементов в Stack;

- Read(R) - функция, которая считывает очередной элемент из Stack;

- isConst() - функция, которая проверяет, является ли R идентификатором или константой;

- operBinary() - функция, которая проверяет, является ли R бинарным оператором;

- operUnary() - функция, которая проверяет, является ли R унарным оператором;

- operN() - функция, которая проверяет, является ли R n-арным оператором;

- AST() - подпрограмма формирования очередного поддерева или листа АСД.

Рис. 1. Блок-схема алгоритма перевода программы из польской нотации в абстрактное синтаксическое дерево

Результатом работы программы, работающей в соответствии с представленным набором правил для перевода программы из польской нотации в АСД, является АСД графа, хранящееся в памяти в виде многосвязного списка с пропусками ([9]).

Алгоритм преобразования АСД в граф потока управления программы

Следующим этапом по построению графа потока управления программы из АСД является процесс передачи по АСД данных. Для этого воспользуемся алгоритмом обратного обхода дерева [10].При обратном обходе АСД происходит рекурсивный обход левого поддерева, затем правого поддерева, затем корня, т. е. узел посещается после обхода его поддеревьев. В узлах АСД находятся бинарные и унарные операторы в модифицированной обратной польской нотации и, в зависимости от их выполнения, при передаче данных по АСД будет изменяться количество связей в поддеревьях АСД.

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

Таким образом, если при обходе АСД и его преобразовании в граф потока управления программы на очередном шаге на процессор передаются данные разрядности п, причем п < 64 , то нерационально выделять этот шаг как отдельный в графе потока управления программы. Следует также отметить, что в процессе работы с данными может возникать ситуация, когда разрядность результата превышает разрядность входных данных - переполнение. В случае переполнения нейропроцессор сигнализирует об этом значением флага переполнения, присваивая ему 1. Этот механизм необходимо учитывать при участии результата вычислений в дальнейшей работе. С учетом этих утверждений алгоритм перехода от АСД к графу потока управления нейропро-граммы примет вид, показанный на рис. 2.

Плк1егТгее.орегМа№() == 1гие ог" ип(1егТгее.орегВтагу() — 1гие ог

Рис. 2. Блок-схема алгоритма преобразования АСД в граф потока управления программы

Пусть на вход АСД подаются данные разрядностью BitVal = ({flag,n}, ... ,{flag,k}), где n, ..., k < 64 - разрядность данных, а flag = 1 u 0 - значение флага переполнения.

Считываем очередное левое поддерево АСД из многосвязного списка, состоящее из крайнего нижнего левого и правого листа (если они есть) и их корня, т. е. считываем крайние операнды нижнего слоя и их оператор.

Если это бинарный арифметический оператор, бинарный оператор задания массива, бинарный оператор обращения к элементу массива, если при этом разрядность входных данных меньше 64, т. е. 64 - n - ...- k > 0, то осуществляется переход к считыванию следующего правого листа АСД (если он есть) и его корня, переход же на следующий процессорный модуль не осуществляется. Если 64 -n - ... - k < 0, то происходит выполнение операции с данными всех операторов, кроме последнего, за один такт. Если возникает переполнение, то у одного или нескольких результатов значение flag = 1, следовательно, разрядность результата увеличивается на единицу. Последний оператор со своими операциями переходит на следующий процессорный модуль, на него же осуществляется считывание следующего правого листа АСД (если он есть) и его корня. Листья и их корень, соединенные дугами, заносятся в матрицу смежности, которой представляется граф потока управления программы.

Если это унарный оператор безусловного перехода, бинарный оператор условного перехода, то строится дуга от оператора до адресата безусловного перехода в АСД и осуществляется считывание следующего правого от адресата листа (если он есть) и его корня. Лист и корень, соединенные дугами, заносятся в матрицу смежности, которой представляется, граф потока управления программы.

На рис. 2 указаны следующие программные функции, посредством которых реализована работа алгоритма:

- isEmpty() - функция, которая проверяет наличие элементов в многосвязном списке AST, т. е. наличие элементов дерева АСД;

- LUnderTree() - функция, считывающая крайнее левое поддерево AST;

- operMath() - функция, определяющая, является ли считанное поддерево бинарным арифметическим оператором;

- operBinary() - функция, определяющая, является ли считанное поддерево неклассифицированным бинарным оператором;

- operArray() - функция, определяющая, является ли считанное поддерево бинарным оператором задания массива;

- operSubs() - функция, определяющая, является ли считанное поддерево бинарным оператором обращения к элементу массива;

- operUT() - функция, определяющая, является ли считанное поддерево унарным оператором безусловного перехода;

- operBRZ() - функция, определяющая, является ли считанное поддерево унарным оператором условного перехода;

- bitDepthData() - функция, осуществляющая запись в матрицу смежности, которой представляется граф потока управления программы;

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

Выводы

Таким образом, все операции, записанные в модифицированной обратной польской нотации, представленной в форме АСД, при передаче на них данных определенной разрядности (n, ., k < 64)в момент перехода к графу потока управления программы, выполняющегося за один такт, являются атомарными неделимыми операциями и могут быть представлены как подпрограммы исходной программы, поступившей в вычислительный кластер нейрокомпьютеров.

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

Шаг 1. Представить программу, поступившую в кластер, в модифицированной обратной польской нотации. Сохранить ее в стеке команд программы.

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

Шаг 3. Подать на АСД-программы данные с учетом их разрядности.

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

Шаг 5. Получить матрицу смежности графа потока управления программы.

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

СПИСОК ЛИТЕРА ТУРЫ

1. Бурцев В. С. Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. М.: ИВВС РАН, 1997. 152 с.

2. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.

3. Галушкин А. И. Нейронные сети: основы теории. М.: Горячая линия - Телеком, 2010. 496 с.

4. Топорков В. В. Модели распределенных вычислений. М.: Физматлит, 2004. 320 с.

5. Ручкин В. Н., Романчук В. А., Лукашенко В. В. Обобщенная модель вычислений кластера нейрокомпьютеров // Вестн. Рязан. гос. ун-та им. С. А. Есенина. 2015. № 2 (47). С. 146-150.

6. Коновалов Н., Крюков В. Параллельные программы для вычислительных кластеров и сетей // Открытые системы. СУБД. 2002. № 3. С. 12-18.

7. Корячко В. П. Алгоритм планирования вычислительного процесса в мультипроцессорной вычислительной системе реального времени // Автоматика и вычислительная техника. 1985. № 3. С. 16-18.

8. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. 544 с.

9. Седжвик Р. Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных. М.: Вильямс, 2011. 1056 с.

10. Вирт Н. Алгоритмы и структуры данных. М.: ДМК Пресс, 2010. 272 с.

Статья поступила в редакцию 30.05.2017

ИНФОРМАЦИЯ ОБ АВТОРАХ

Лукашенко Владислав Владиславович — Россия; 390035; Рязань; Рязанский государственный университет имени С. А. Есенина; научный сотрудник кафедры информатики, вычислительной техники и методики преподавания информатики; v.lukashenko@nstlabs.net.

Романчук Виталий Александрович - Россия; 390035; Рязань; Рязанский государственный университет имени С. А. Есенина; доцент кафедры информатики, вычислительной техники и методики преподавания информатики; v.romanchuk@rsu.edu.ru.

V. V. Lukashenko, V. A. Romanchuk

DEVELOPING ALGORITHM FOR PARTITIONING TASKS INTO SUBTASKS IN THE SYSTEMS OF DISTRIBUTED DATA PROCESSING

Abstract. In terms of the problem of insufficient computational resources for a number of tasks, realization of computational cluster of neurocomputers is being considered as a variant. To implement the basic principle of distributed computing, there has been presented an algorithm for splitting the tasks entering the computational cluster of neurocomputers into sub-tasks. For this purpose, the program introduced into the cluster is suggested to present for execution in the modified postfix Polish record and to store it in the program command stack. To modify

the program Polish notation should include different, non-arithmetic, operators and constructions. The next step is to get an abstract syntax tree of the program, following the rules for translating the modified postfix Polish record from the command stack into an abstract syntax tree. Then, the data should be sent to the abstract syntax tree of the program taking into account their bit depth, and to obtain the contiguity matrix of the program control flow graph that will display the set of all ways of program execution. The authors come to the conclusion that all operations recorded in the modified reverse Polish record presented in the form of an abstract syntax tree when data of a certain bit depth are transmitted to them, at the moment of transition to the program control flow graph executed in a single clock cycle are indivisible operations and can be represented as subprograms of the source program, which was submitted for processing to the computer cluster of neurocomputers.

Key words: distributed computing, cluster computing, neurocomputers, clustering of computing resources, modified Polish notation, abstract syntactic tree.

REFERENCES

1. Burtsev V. S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektury superEVM [Parallelism of computing processes and architecture developing]. Moscow, IVVS RAN, 1997. 152 p.

2. Voevodin V. V., Voevodin Vl. V. Parallel'nye vychisleniia [Parallel computations]. Saint-Petersburg, BKhV-Peterburg, 2002. 608 p.

3. Galushkin A. I. Neironnye seti: osnovy teorii [Neuron networks: Introduction into the theory]. Moscow, Goriachaia liniia - Telekom, 2010. 496 p.

4. Toporkov V. V. Modeli raspredelennykh vychislenii [Distribution computation models]. Moscow, Fizmatlit, 2004. 320 p.

5. Ruchkin V. N., Romanchuk V. A., Lukashenko V. V. Obobshchennaia model' vychislenii klastera neiro-komp'iuterov [A generalized model of neurocomputer clusters]. Vestnik Riazanskogo gosudarstvennogo universi-teta imeni S. A. Esenina, 2015, no. 2 (47), pp. 146-150.

6. Konovalov N., Kriukov V. Parallel'nye programmy dlia vychislitel'nykh klasterov i setei [Parallel programs for computational clusters and networks]. Otkrytye sistemy. SUBD, 2002, no. 3, pp. 12-18.

7. Koriachko V. P. Algoritm planirovaniia vychislitel'nogo protsessa v mul'tiprotsessornoi vychislitel'noi sisteme real'nogo vremeni [Algorithm of computational process planning in a multiprocessor computing real-time system]. Avtomatika i vychislitel'naia tekhnika, 1985, no. 3, pp. 16-18.

8. Gries D. Designing Compilers for Digital Computers. New York, Jhon Wiley, 1971.493 p. (Gris D. Konstruirovanie kompiliatorov dlia tsifrovykh vychislitel'nykh mashin. Moscow, Mir Publ., 1975. 544 p.).

9. Sedgewick R. Algorithms in C ++ (Russ. ed.: Sedzhvik R. Algoritmy na C++. Fundamental'nye algorit-my i struktury dannykh. Moscow, Vil'iams Publ., 2011. 1056 p.).

10. Wirt N. Algorithms and Data Structures (Russ. ed.: Virt N. Algoritmy i struktury dannykh. Moscow, DMK Press, 2010. 272 p.).

The article submitted to the editors 30.05.2017

INFORMATION ABOUT THE AUTHORS

Lukashenko Vladislav Vladislavovich - Russia; 390035; Ryazan; Ryazan State University named after S. A. Yesenin; Researcher of the Department of Informatics, Computer Science and Methods of Teaching Informatics; v.lukashenko@nstlabs.net.

Romanchuk Vitaly Aleksandrovich - Russia; 390035; Ryazan; Ryazan State University named after S. A. Yesenin; Assistant Professor of the Department of Informatics, Computer Science and Methods of Teaching Informatics; v.romanchuk@rsu.edu.ru.