DEVELOPING ALGORITHM FOR PARTITIONING TASKS INTO SUBTASKS IN THE SYSTEMS OF DISTRIBUTED DATA PROCESSING
Authors:
1.
Ryazan State University named after S. A. Yesenin
2.
Ryazan State University named after S. A. Yesenin
Type:
Article
Pages:
from 31
to 38
Status:
Published
Received:
05.10.2017
Accepted:
25.10.2017
Published:
25.10.2017
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.383.3
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.383.3
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
distributed computing, cluster computing, neurocomputers, clustering of computing resources, modified Polish notation, abstract syntactic tree
Abstract (English):
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.
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.
Keywords:
distributed computing, cluster computing, neurocomputers, clustering of computing resources, modified Polish notation, abstract syntactic tree
distributed computing, cluster computing, neurocomputers, clustering of computing resources, modified Polish notation, abstract syntactic tree
Введение В современной научной и производственной сферах достаточно актуально использование систем распределенной обработки данных из-за недостаточности локальных вычислительных ресурсов для решения ряда задач. Для решения этой проблемы с достаточно высокой степенью эффективности возможно применение масштабируемых параллельных высокоскоростных кластеров на базе нейрокомпьютеров [1]. Нами рассматривается конкретная реализация вычислительного кластера на базе нейрокомпьютеров MB 77.07 ЗАО «НТЦ «Модуль», технические характеристики, преимущества и перспективность которых описаны в [2-4]. При выборе нестандартной архитектуры вычислительных машин кластера необходимо построить модель вычислений, которая служит связующим звеном между архитектурой вычислительной системы и моделью программирования и в распределенных системах отражает взаимодействие процессов. Под моделью вычислений будем понимать определение множества допустимых операций, используемых при вычислениях, а также относительных издержек их применения, которые характеризуют необходимые вычислительные ресурсы - время выполнения, объём памяти, а также ограничения алгоритмов или вычислительной системы. Проблема разработки модели вычислений рассматривается в [5]. Авторами [5] определен ряд алгоритмов, разработка которых необходима для реализации модели вычислений кластера нейрокомпьютеров. Одним из таких алгоритмов является алгоритм разбиения задач на подзадачи, необходимый для декомпозиции задач, поступающих в вычислительный кластер, что позволит реализовать основной принцип теории распределенных вычислений. Разработка такого алгоритма и явилась целью нашего исследования. Этапы выполнения алгоритма разбиения задачи на подзадачи в системах распределенной обработки данных Для успешного разбиения задачи на более мелкие, атомарные подзадачи необходимо рассматривать ее с позиции алгоритма. Каждая задача, поступающая в распределенный вычислительный кластер, есть алгоритм , реализованный в виде программы на языке, понятном вычислительной системе, и необходимый набор данных. Программа , реализующая алгоритм , представляет собой последовательность машинных операций. Однако для целей нашего исследования программу можно представить в виде графа потока управления: , где - граф потока управления программы, а - алфавит операторов. Отметим, что на любом уровне детализации операторы считаются атомарными. Граф потока управления - это ориентированный граф, в котором выделены две вершины - start и stop, связанные между собой посредством множеств вершин W и дуг E соответственно. Граф удовлетворяет следующим требованиям: - в start не входит ни одна дуга; - из stop не выходит ни одна дуга; - любая вершина достижима из start; - из любой вершины достижима вершина stop. Вершинами такого графа являются отдельные операции над операндами, выполняющиеся независимо друг от друга, а дугами - абстрактные направления данных, необходимых для выполнения операций. Для описания программы, исполняющейся на вычислительных машинах традиционной архитектуры, этого достаточно. В свою очередь, для вычислительных машин рассматриваемого кластера нейрокомпьютеров очень важен параметр разрядности данных, поскольку за один процессорный такт на одном физическом вычислительном ядре нейрокомпьютера может выполниться до 64 операций, что существенно влияет на процесс распараллеливания вычислений в кластере и что, в свою очередь, меняет процесс обхода графа потока управления. В связи с этим граф потока управления программы будет представлен следующим образом:, где BitVal - множество значений разрядности результатов на каждом шаге выполнения программы при обходе графа потока управления. Для разбиения программы на подпрограммы необходимо рассмотреть программу во внутренней форме представления программ. Внутренняя форма представления программ является результатом работы синтаксического анализатора. Различают следующие виды внутренних форм представления программ: постфиксная польская нотация, префиксная польская нотация, синтаксическое дерево, тетрады. Наиболее распространенным способом представления программ во внутренней форме является постфиксная польская нотация [6-8]. В нашем исследовании в качестве внутренней формы представления программ принята постфиксная польская нотация, которая традиционно применяется для записи математических и логических выражений. Однако в нашем случае для представления всей программы в польской нотации необходимо применить модифицированный алгоритм перевода. Модифицированный алгоритм фактически не отличается от традиционного алгоритма перевода. Однако для представления полной программы в состав операций требуется включить операции управления, назначив им соответствующие приоритеты (см., например, [8]). Такое представление будем называть модифицированной обратной польской нотацией. Модифицированная обратная польская нотация Рассмотрим включение в польскую нотацию других, отличных от арифметических, операторов и конструкций: Безусловные переходы. Безусловный переход - это унарный оператор, который в польской нотации имеет следующий синтаксис: <адрес перехода>$UT, где $UT - знак операции, а операндом является адрес перехода. Условные переходы. Операция условного перехода является бинарной и в польской нотации может быть представлена следующим образом: - <операнд 1>< адрес перехода>$CBZ|$CBlZ|$CBaZ|$CBleZ|$CBaeZ. - <операнд 1> - значение арифметического выражения; - <адрес перехода> - адрес перехода в таблице символов; - $CBZ - код оператора перехода по значению 0; - $CBlZ - код оператора перехода по значению меньше 0; - $CBaZ - код оператора перехода по значению больше 0; - $CBleZ - код оператора перехода по значению меньше или равно 0; - $CBaeZ - код оператора перехода по значению больше или равно 0. Описание массива. Описание массива - это n-арный оператор со следующим синтаксисом в польской нотации: <элемент массива 1>…<элемент массива i><адрес> $ARRAY, где <элемент массива i> - адрес очередного элемента массива;<адрес>- в таблице символов хранит размерность массива;$ARRAY- код оператора. Обращение к элементу массива. Обращение к элементу массива тоже является n-арным оператором, который в польской нотации может быть представлен таким образом: <выражение 1> ... <выражение i><адрес> $SUBS, где оператор $SUBS, используя <адрес> из таблицы символов и индексные выражения, вычисляет адрес элемента массива. Вызов подпрограммы с аргументами. Вызов подпрограммы - это n-арный оператор со следующим синтаксисом в польской нотации: <аргумент 1>…<аргумент i><имя функции> $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 операций. Это существенно влияет на процесс распараллеливания вычислений в кластере, что меняет процесс обхода графа потока управления. Таким образом, если при обходе АСД и его преобразовании в граф потока управления программы на очередном шаге на процессор передаются данные разрядности, причем , то нерационально выделять этот шаг как отдельный в графе потока управления программы. Следует также отметить, что в процессе работы с данными может возникать ситуация, когда разрядность результата превышает разрядность входных данных - переполнение. В случае переполнения нейропроцессор сигнализирует об этом значением флага переполнения, присваивая ему 1. Этот механизм необходимо учитывать при участии результата вычислений в дальнейшей работе. С учетом этих утверждений алгоритм перехода от АСД к графу потока управления нейропрограммы примет вид, показанный на рис. 2. Рис. 2. Блок-схема алгоритма преобразования АСД в граф потока управления программы Пусть на вход АСД подаются данные разрядностью , где n, …, k ˂ 64 - разрядность данных, а - значение флага переполнения. Считываем очередное левое поддерево АСД из многосвязного списка, состоящее из крайнего нижнего левого и правого листа (если они есть) и их корня, т. е. считываем крайние операнды нижнего слоя и их оператор. Если это бинарный арифметический оператор, бинарный оператор задания массива, бинарный оператор обращения к элементу массива, если при этом разрядность входных данных меньше 64, т. е. 64 - n -…- k ˃ 0, то осуществляется переход к считыванию следующего правого листа АСД (если он есть) и его корня, переход же на следующий процессорный модуль не осуществляется. Если , то происходит выполнение операции с данными всех операторов, кроме последнего, за один такт. Если возникает переполнение, то у одного или нескольких результатов значение, следовательно, разрядность результата увеличивается на единицу. Последний оператор со своими операциями переходит на следующий процессорный модуль, на него же осуществляется считывание следующего правого листа АСД (если он есть) и его корня. Листья и их корень, соединенные дугами, заносятся в матрицу смежности, которой представляется граф потока управления программы. Если это унарный оператор безусловного перехода, бинарный оператор условного перехода, то строится дуга от оператора до адресата безусловного перехода в АСД и осуществляется считывание следующего правого от адресата листа (если он есть) и его корня. Лист и корень, соединенные дугами, заносятся в матрицу смежности, которой представляется, граф потока управления программы. На рис. 2 указаны следующие программные функции, посредством которых реализована работа алгоритма: - isEmpty() - функция, которая проверяет наличие элементов в многосвязном списке AST, т. е. наличие элементов дерева АСД; - LUnderTree() - функция, считывающая крайнее левое поддерево AST; - operMath() - функция, определяющая, является ли считанное поддерево бинарным арифметическим оператором; - operBinary() - функция, определяющая, является ли считанное поддерево неклассифицированным бинарным оператором; - operArray() - функция, определяющая, является ли считанное поддерево бинарным оператором задания массива; - operSubs() - функция, определяющая, является ли считанное поддерево бинарным оператором обращения к элементу массива; - operUT() - функция, определяющая, является ли считанное поддерево унарным оператором безусловного перехода; - operBRZ() - функция, определяющая, является ли считанное поддерево унарным оператором условного перехода; - bitDepthData() - функция, осуществляющая запись в матрицу смежности, которой представляется граф потока управления программы; - AdjacencyMatrix - матрица смежности, которой представляется граф потока управления программы. Выводы Таким образом, все операции, записанные в модифицированной обратной польской нотации, представленной в форме АСД, при передаче на них данных определенной разрядности (n, …, k ˂ 64)в момент перехода к графу потока управления программы, выполняющегося за один такт, являются атомарными неделимыми операциями и могут быть представлены как подпрограммы исходной программы, поступившей в вычислительный кластер нейрокомпьютеров. Общий алгоритм разбиения задач, поступивших в вычислительный кластер нейрокомпьютеров, на подзадачи можно представить следующим образом. Шаг 1. Представить программу, поступившую в кластер, в модифицированной обратной польской нотации. Сохранить ее в стеке команд программы. Шаг 2. Следуя правилам перевода модифицированной обратной польской нотации из стека команд в АСД, получить АСД-программы. Шаг 3. Подать на АСД-программы данные с учетом их разрядности. Шаг 4. Операции с учетом разрядности необходимых для них данных, выполняющиеся на нейропроцессоре за один такт, сформировать в отдельные подпрограммы и поместить их в очередь. Шаг 5. Получить матрицу смежности графа потока управления программы. Таким образом, совокупная работа рассмотренных алгоритмов дает возможность разбить исходную программу на атомарные подпрограммы, а также получить матрицу смежности графа потока управления программы для дальнейшей работы.
1. Burcev V. S. Parallelizm vychislitel'nyh processov i razvitie arhitektury superEVM. M.: IVVS RAN, 1997. 152 s.
2. Voevodin V. V., Voevodin Vl. V. Parallel'nye vychisleniya. SPb.: BHV-Peterburg, 2002. 608 s.
3. Galushkin A. I. Neyronnye seti: osnovy teorii. M.: Goryachaya liniya - Telekom, 2010. 496 s.
4. Toporkov V. V. Modeli raspredelennyh vychisleniy. M.: Fizmatlit, 2004. 320 s.
5. Ruchkin V. N., Romanchuk V. A., Lukashenko V. V. Obobschennaya model' vychisleniy klastera neyrokomp'yuterov // Vestn. Ryazan. gos. un-ta im. S. A. Esenina. 2015. № 2 (47). S. 146-150.
6. Konovalov N., Kryukov V. Parallel'nye programmy dlya vychislitel'nyh klasterov i setey // Otkrytye sistemy. SUBD. 2002. № 3. S. 12-18.
7. Koryachko V. P. Algoritm planirovaniya vychislitel'nogo processa v mul'tiprocessornoy vychislitel'noy sisteme real'nogo vremeni // Avtomatika i vychislitel'naya tehnika. 1985. № 3. S. 16-18.
8. Gris D. Konstruirovanie kompilyatorov dlya cifrovyh vychislitel'nyh mashin. M.: Mir, 1975. 544 s.
9. Sedzhvik R. Algoritmy na C++. Fundamental'nye algoritmy i struktury dannyh. M.: Vil'yams, 2011. 1056 s.
10. Virt N. Algoritmy i struktury dannyh. M.: DMK Press, 2010. 272 s.
