РАЗРАБОТКА АЛГОРИТМА РАЗБИЕНИЯ ЗАДАЧ НА ПОДЗАДАЧИ В СИСТЕМАХ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ ДАННЫХ
Авторы:
1.
Рязанский государственный университет имени С. А. Есенина
2.
Рязанский государственный университет имени С. А. Есенина
Тип:
Статья
Страницы:
с 31
по 38
Статус:
Опубликован
Получено:
05.10.2017
Одобрено:
25.10.2017
Опубликовано:
25.10.2017
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.383.3
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.383.3
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
распределенные вычисления, кластерные вычисления, нейрокомпьютеры, кластеризация вычислительных ресурсов, модифицированная обратная польская нотация, абстрактное синтаксическое дерево
Аннотация (русский):
В рамках исследования проблемы недостаточности вычислительных ресурсов для ряда задач рассматривается вариант реализации вычислительного кластера нейрокомпьютеров. Для реализации основного принципа распределенных вычислений представлен общий алгоритм разбиения задач, поступающих в вычислительный кластер нейрокомпьютеров, на подзадачи. Для этого программу, поступившую в кластер, предлагается представить в модифицированной постфиксной польской нотации и хранить ее в стеке команд программы. Для модификации программы в польскую нотацию включаются другие, отличные от арифметических, операторы и конструкции. Следующий шаг - получение абстрактного синтаксического дерева программы по правилам перевода модифицированной обратной польской нотации из стека команд в абстрактное синтаксическое дерево. Затем предлагается отправить данные, с учетом их разрядности, в абстрактное синтаксическое дерево программы и получить матрицу смежности графа потока управления программы, которая отобразит множество всех путей исполнения программы. Сделан вывод о том, что все операции, записанные в модифицированной обратной польской нотации и представленные в форме абстрактного синтаксического дерева, при передаче по нему данных определенной разрядности, в момент перехода к графу потока управления программы, выполняющегося за один такт, являются неделимыми операциями и могут быть представлены как подпрограммы исходной программы, поступившей на обработку в вычислительный кластер нейрокомпьютеров.
В рамках исследования проблемы недостаточности вычислительных ресурсов для ряда задач рассматривается вариант реализации вычислительного кластера нейрокомпьютеров. Для реализации основного принципа распределенных вычислений представлен общий алгоритм разбиения задач, поступающих в вычислительный кластер нейрокомпьютеров, на подзадачи. Для этого программу, поступившую в кластер, предлагается представить в модифицированной постфиксной польской нотации и хранить ее в стеке команд программы. Для модификации программы в польскую нотацию включаются другие, отличные от арифметических, операторы и конструкции. Следующий шаг - получение абстрактного синтаксического дерева программы по правилам перевода модифицированной обратной польской нотации из стека команд в абстрактное синтаксическое дерево. Затем предлагается отправить данные, с учетом их разрядности, в абстрактное синтаксическое дерево программы и получить матрицу смежности графа потока управления программы, которая отобразит множество всех путей исполнения программы. Сделан вывод о том, что все операции, записанные в модифицированной обратной польской нотации и представленные в форме абстрактного синтаксического дерева, при передаче по нему данных определенной разрядности, в момент перехода к графу потока управления программы, выполняющегося за один такт, являются неделимыми операциями и могут быть представлены как подпрограммы исходной программы, поступившей на обработку в вычислительный кластер нейрокомпьютеров.
Ключевые слова:
распределенные вычисления, кластерные вычисления, нейрокомпьютеры, кластеризация вычислительных ресурсов, модифицированная обратная польская нотация, абстрактное синтаксическое дерево
распределенные вычисления, кластерные вычисления, нейрокомпьютеры, кластеризация вычислительных ресурсов, модифицированная обратная польская нотация, абстрактное синтаксическое дерево
Введение В современной научной и производственной сферах достаточно актуально использование систем распределенной обработки данных из-за недостаточности локальных вычислительных ресурсов для решения ряда задач. Для решения этой проблемы с достаточно высокой степенью эффективности возможно применение масштабируемых параллельных высокоскоростных кластеров на базе нейрокомпьютеров [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. Бурцев В. С. Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. М.: ИВВС РАН, 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 с.
