НАУКА и ОБРАЗОВАНИЕ

Брагин Алексей Владимирович,
Бебчик Антон Михайлович

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.