Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408![]()
Возможности применения параллельных методов вычисления в системе программирования на языке S-FLOGOL
#4 2008
Брагин
Алексей Владимирович,
1. Введение. Язык S-FLOGOL является подмножеством языка FLOGOL, разработанного Фальком В.Н. на базе теории направленных отношений. Теория направленных отношений, разработанная Фальком В.Н., и Кутеповым В. П. [1,2], является универсальной теоретической моделью, позволяющей в естественной форме описывать и вычислять рекурсивно заданные объекты некоторой предметной области. На базе теории направленных отношений был разработан функционально-логический язык программирования высокого уровня S-FLOGOL, поддерживающий основные тенденции развития современных языков программирования и позволяющий в компактной схемной форме задавать определения конструктивных объектов в терминах направленных отношений (язык S-FLOGOL является представительным подмножеством языка FLOGOL, разработанного Фальком В.Н. [3,4]). В [5,6] описывается разработка и исследование системы функционально-логического программирования на языке S-FLOGOL, далее называемой FLIDE. Интегрированная среда программирования FLIDE реализована с использованием Borland C++ Builder версии 6.0 и включает в себя центральный модуль, текстовый редактор, графический редактор, компилятор запросов, подсистему исполнения запросов (далее – ПСИЗ). Исходный код системы написан на языке C++ с использованием принципов объектно-ориентированного программирования, и использует библиотеки Borland VCL и стандартную библиотеку шаблонов Standard Template Library (далее – STL). 2. Возможности развития. Для дальнейшего развития и улучшения системы можно выделить ряд направлений: · Улучшение графического редактора · Добавление более глубоких возможностей по отладке больших программ, с возможностью сохранения промежуточных результатов, и продолжения вычислений · Преобразование между различными представлениями программы (сетевым, текстовым, логическим) · Улучшение выразительных возможностей самого языка S-FLOGOL · Оптимизация алгоритмов вычисления для снижения времени поиска решения и объема требуемой оперативной памяти · Использование возможностей современного аппаратного обеспечения В этой статье не будут рассматриваться возможности по улучшению взаимодействия с пользователем, преобразования программ, возможностей отладки и других, не связанных с процессом вычисления действий. Рассмотрим более подробно два последних пункта, касающиеся оптимизации вычислительного алгоритма и использования современных многоядерных архитектур и кластерных систем. Сформулируем цель работы созданию параллельной реализации вычисления нормальных отношений. Выполнение функционально-логических программ требует значительных затрат вычислительных ресурсов. Для более эффективной организации решения таких задач желательно использовать их естественный параллелизм, и реализовать поддержку параллельного выполнения функционально-логических программ на современных вычислительных комплексах кластерного типа, и многоядерных процессорах (максимально возможное число ядер доступное на сегодняшний день в одной машине архитектуры x86 – восемь, в виде двухпроцессорной конфигурации четырехядерных процессоров типа Xeon). Дальнейшее развитие этой системы с точки зрения увеличения быстродействия возможно за счёт дальнейшей оптимизации вычислительных механизмов по минимизации времени и объёма необходимой для вычисления памяти, а также оптимизации самой программы, либо изменению самого механизма вычисления. Одним из таких вариантов является использования естественного параллелизма для организации вычислений на многопроцессорных машинах и системах кластерного типа. Для реализации параллельных вычислений, необходимо выделить и переработать подсистему исполнения запросов из интегрированной среды FLIDE в отдельный программный модуль, и добавить в FLIDE возможности по загрузке и просмотру результатов, полученных с помощью подсистемы исполнения запросов (в параллельной реализации). Такой программный модуль должен обладать свойством переносимости (англ. – portability), т.к. большинство кластерных систем основаны на Unix-подобных операционных системах, а построение многопоточных программ требует более серьёзных инструментов разработки, чем пакет Borland C++ Builder. 3. Особенности программной реализации. Программная реализация подсистемы исполнения запросов (далее - ПСИЗ) состоит из следующих модулей и классов на языке Си++: · CObjs, классы CRel, CDot, CLinkR, CLinkD, UniList для представления отношений, точек, связей и списков в системе. · DebugMessages для работы с отладочными сообщениями. · DualList, классы DualListNode, DualList для организации связного списка. · GNet – класс сети в графическом представлении. · GObjs, GPoint – ряд классов для представления различных элементов в графическом виде. · Net – класс, представляющий сеть, и содержащий методы вычисления. · Nets – класс для представления списков сетей, принадлежащих одной программе. · NProgram – класс «программа», основополагающий для реализации ПСИЗ. · NProgInfo, классы CalcInfo, AlignInfo, StatInfo для передачи и сохранения информации для процесса вычисления. · Классы Sort и Sorts для хранения сорта и списков сортов. При реализации этого набора классов на другой платформе разработке (в данном случае в среде Microsoft Visual Studio 2008) и при реализации ПСИЗ как отдельного программного модуля, необходимо учитывать следующее: 1. Широкое использование VCL и нестандартных классов для работы со строками (AnsiString) в среде FLIDE. 2. Использование типа Variant (универсальный тип для представления различных данных) при работе со строковыми массивами. 3. Объединенное графическое представление сети и её элементов с методами отображения этого представления. 4. Взаимодействие с интегрированной средой разработки – возможность загрузки программ, созданных в интегрированной среде FLIDE, а также возможность выгрузки результатов для последующего просмотра и анализа. Использование нестандартных классов для работы со строками были заменено на использование стандартная библиотека шаблонов STL, а использования нестандартных типов и работа с графикой были выделены с помощью директив условной компиляции. Графическое представление сети необходимо для расчётов, т.к. исходные сети в файле программы сохраняются именно в графическом виде. Для разделения методов отображения и методов хранения были применены директивы условной компиляции. В будущем возможно выделить методы отображения в отдельные классы и использовать их для дальнейшего абстрагирования от какой-либо конкретной платформы разработки.
Рисунок 1. Результаты профайлера Проведя измерение производительности работы программы с помощью встроенного инструмента Microsoft Visual Studio 2005 (см. рис. 1), было выяснено, что наибольшее время процесс проводит в методах NProgram::calcStep и Net::calculate2. Метод calcStep класса NProgram реализует один шаг вычисления, при этом из списка выбирается некоторая сеть, и для неё вызывается метод calculate2. Этот метод класса Net проводит все необходимые операции по подстановке, редукции, проверки на результат, конфликты, занесение новых сетей в список для обработки, и другие сопутствующие действия. Последний в таблице из рис. 1 метод substShell2 проводит операцию подстановки сети. Как видно, наибольшее время тратится именно на выполнение вычислений с сетью, что подтверждает планируемый прирост производительности от распараллеливания процесса вычисления абстрактной машины вычисления направленных отношений. Детально рассмотрим механизм её работы в последовательном виде для получения представления о возможностях параллельной реализации. 4. Абстрактная машина вычисления направленных отношений. Построение абстрактной машины является распространенным и естественным способом реализации моделей вычисления, опирающихся на нетрадиционные архитектуры. Разработанная в подсистеме исполнения запросов (ПСИЗ) языка S-FLOGOL абстрактная машина вычисления направленных отношений (АМНО) опирается на базовую модель вычисления направленных отношений (НО), поэтому в качестве подхода к вычислению использует порождение сетевого языка по контекстно-свободной сетевой грамматикой (КССГ) и редукцию сетей. Основными задачами при построении АМНО являются выделение базовых вычислительных операций и описание процесса вычисления в терминах этих операций. АМНО может быть реализована на различных аппаратно-программных средствах. В системе функционально-логического программирования (СФЛП) FLIDE АМНО в составе ПСИЗ СФЛП выполняется под управлением ОС Windows на IBM/PC-совместимых машинах, что обусловлено их широким распространением в нашей стране и имеет особое значение для использования СФЛП в учебных целях. Основными являются операции, реализующие применение правил к сетям, формируемым во время вычисления, а также операции, определяющие и реализующие порядок обхода дерева поиска, т.е. определяющие стратегию вычисления. Кроме этого, требуется команда для выполнения редукции сетей. Выделим базовый набор операций, необходимых АМНО: - выбор сети для подстановки (FindNet), - выбор замещаемого при подстановке элемента (FindElm), - выбор правила для подстановки (FindRule), - выполнение подстановки (Subst), - выполнение редукции (Normalize), - добавление сети к концу списка (AddNet), - вставка сети в начало списка (InsertNet), - передача сети из одного списка в другой (MoveNet), - удаление сети из списка (DelNet).
Последние четыре операции (AddNet, InsertNet, MoveNet, DelNet) используются в служебных целях для управления списками, и не рассматриваются в этой статье. Для реализации некоторых сложных вычислительных стратегий, например, эвристического поиска, необходима совместная реализация функций FindNet, FindElm и FindRule, позволяющая сравнивать комплексные оценки подстановочной тройки <исходная сеть, замещаемый элемент, тело правила>. Это делает нецелесообразным возможное распараллеливание этих операций. На каждом шаг вычисления АМНО должна произвести выбор сети (посредством операций FindNet, FindElm и FindRule), выполнить подстановку, и, затем, редукцию сети посредством операции Normalize. В формализованном виде алгоритм представлен на рис. 2.
NetSrc = FindNet(AL) Elm = FindElm(Net) SetElm(SrcNet, Elm) while Count(AL) != 0 begin Rule = FindRule(Elm) Net = CopyNet(NetSrc) Res = Subst(Net, Elm, Rule) if Res = true then begin Res = Normalize(Net) if Res = true then begin Elm = FindElm(Net) if not Exists(Elm) then begin if IsResult(Net) MoveNet(AL,RL,Net) else DelNet(AL, Net) end if end else SetElm(Net,Elm) end if end else DelNet(AL, Net) end if else DelNet(AL, Net) end if Elm = FindElm(NetSrc) if not Exists(Elm) then DelNet(NetSrc) NetSrc = FindNet(AL) Elm = FindElm(NetSrc) Wend
Рис. 2. Алгоритм работы АМНО.
Таким образом, реализованная абстрактная машина для языка S-FLOGOL позволяет производить вычисления направленных отношений для широкого класса задач. Для тех задач, вычисление которых требует выполнения большого числа операций подстановок и редукций, а также в случаях большого объема данных в процессе вычисления, данный алгоритм должен быть дополнен возможностями параллельного выполнения процесса вычисления, что является перспективным направлением в дальнейшей работе над системой функционально-логического программирования FLIDE.
СПИСОК ЛИТЕРАТУРЫ 1. Фальк В.Н. Теория направленных отношений и ее приложения // Дисс. … докт. техн. наук. М: – МЭИ. -2001. 2. Кутепов В.П., Фальк В.Н. Направленные отношения: теория и приложения // Изв. РАН. Техническая кибернетика, 1994. ╧4,5. 3. Фальк В.Н. FLOGOL – входной язык системы функционально-логического программирования // Сб. науч. статей к НТК МИРЭА (ТУ).1998 4. Фальк В.Н. Языки схем отношений //Формальные модели параллельных вычислений. Новосибирск, 1988. 5.Бебчик Ан.М. Разработка и исследование подсистемы исполнения запросов и графического редактора системы функционально-логического программирования // Дисс…. канд. техн. наук. М: – МЭИ. – 2005 6. Бебчик Ал. М. Сетевой метод компиляции программ языка функционально-логического программирования S-FLOGOL // Информационные технологии в науке, образовании и производстве: Материалы междунар. научно-техн. конф. – Орел: ОрелГТУ, 2004. – Т.5. – С. 164-168. Публикации с ключевыми словами: параллельные вычисления, оптимизация Публикации со словами: параллельные вычисления, оптимизация Смотри также:
Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||
|