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

Шуликов Александр Валериевич, Украина

Донецкий национальный технический университет, факультет вычислительной техники и информатики


В 70-е годы логическое программирование и базы данных развивались одновременно. Пролог - самый популярный язык ПРОграммирования в ЛОГике - появился как результат упрощения более общих методов доказательства теорем для достижения возможности эффективного программирования. Аналогично реляционная модель данных возникла в результате упрощения сложных иерархической и сетевой моделей для обеспечения возможности непроцедурного манипулирования множественными данными. На протяжении 70-х и в начале 80-х годов Пролог и реляционные базы данных получили широкое распространение не только в академической или научной среде, но и в деловом мире [1].

Одним из важнейших вопросов при построении вычислительных систем является увеличение их быстродействия. Но достигнуть большего быстродействия возможно лишь двумя методами: экстенсивным (лучшие архитектуры, процессоры, большая тактовая частота) или интенсивным (оптимизация, разгрузка кода, распараллеливание). Постоянно обновлять и покупать новое дорогое оборудование менее рентабельно, чем приобрести программное обеспечение, которое работает эффективнее и быстрее на любом имеющемся оборудовании. Распараллеливание в процессе трансляции даёт преимущество в работе программы, в быстродействии выполняемого кода.

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

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

Данная работа посвящена исследованию параллелизма типа «ИЛИ». Этот тип параллелизма имеет место, когда одна подцель может быть унифицирована с заглавиями нескольких клауз, и тела этих клауз вычисляются различными вычислительными модулями.

В работе транслятора можно выделить следующие основные этапы:

1) лексический анализ;

2) синтаксический анализ;

3) унификация.

Лексический анализ представляет собой первую фазу транслятора. Его основная задача заключается в разбиении исходного кода программы на токены, заполнение таблиц имен, отсечение комментариев (если они допускаются) и выдача на выходе последовательности токенов для синтаксического анализатора. При построении таблиц имен, лексический анализатор подает на выход последовательность кодов объектов в этих таблицах. Задача построения лексического анализатора значительно упрощается при использовании инструмента Flex. Он позволяет построить лексический анализатор практически указанием грамматики языка в виде регулярных выражений и действий над теми или иными классами выделяемых объектов [2].

Введем следующие обозначения:

  1. n1 – количество лексем;

  2. n2 – количество утверждений;

  3. n3 – количество символов;

  4. n4 – скорость каналов;

  5. n5 – размер таблицы имен (постоянная величина);

  6. n6 – количество узлов вычислений.

В случае последовательного варианта лексического анализатора общее время работы будет равно общему времени обработки:

при этом временная сложность данной операции может быть оценена как:

она линейно зависит от объема текста программы, количества лексем и утверждений в нем.

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

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

В связи с этим целесообразно реализовать последовательный вариант лексического анализатора при помощи инструмента Flex.

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





1. Чери С., Готлоб Г., Танка Л. Логическое программирование и базы данных – М.: Мир, 1992.

2. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 768с.

3. Шуликов А.В., Дацун Н.Н., Увеличение производительности транслятора языка пролог с использлванием механизма параллельных вычислений. // Материалы III научно-технической конференции молодых ученых и студентов - 2007. - С. 516-518

4. Волкова И., Руденко Т. Формальные грамматики и языки. Элементы теории трансляции. - М.: Издательский отдел факультета ВМиК МГУ, 1998. - 62 с.