Распределённая параллельная Пролог-система



Скачать 47.64 Kb.
Дата18.01.2013
Размер47.64 Kb.
ТипДокументы




Косьмина Я.О.

http://kid.stu.cn.ua/~dart_vader

e-mail: dart@online.com.ua
Распределённая параллельная Пролог-система
Традиционно базы данных не имеют универсальных языков обработки данных [1], ограничиваясь языками запросов. С другой стороны универсальные языки обработки данных не имеют возможности работать с большими массивами информации. Также жестко стоит вопрос производительности систем обработки информации.

Различные реализации Пролога уже давно взаимодействуют с базами данных через интерфейсы [2] или драйверы доступа к системам управления базами данных (Amzi, GNU, SWI и др.). Значительный интерес представляет параллелизм и распределение в Акторном Прологе [3], при создании которого его автор, А.А. Морозов, частично решил проблему “необратимых” процессов, существующих вне Пролог-машины, но с которыми Пролог должен взаимодействовать. Ещё одной важной особенностью Акторного Пролога является то, что он позволяет сохранить текущее состояние программы на диск и затем восстановить выполнение этой программы.

Среди диалектов Пролога представляет интерес язык параллельного логического программирования KL1 [4]. При тестировании на стандартных примерах, удовлетворяющих ограничениям KL1, программа, написанная на этом языке, выполнялась в два раза быстрее в сравнении с аналогичной программой, написанной на Прологе (на компьютере с одним процессором). Все прикладные системы, написанные на KL1, работают со скоростью, почти линейно пропорциональной числу процессоров.

В данной статье рассматривается возможность создания параллельной Пролог-системы, которая базируется на универсальном языке обработки данных.

Универсальный язык обработки данных

Среди универсальных языков обработки данных высокий интерес представляют логические языки. Они имеют следующие преимущества: вывод целевого утверждения и обратимость процессов. Программа на логическом языке состоит из набора утверждений, составляющих базу знаний. Выполнение программы - это конструктивный вывод целевого утверждения из программы.

Среди логических языков наибольшую известность получил Пролог. Для Пролога существует стандарт ISO, его интерпретаторы и компиляторы поддерживаются рядом фирм на различных платформах. Эти особенности послужили главными аргументами в пользу выбора языка SWI-Пролог, среди диалектов Пролога – KL1[4] и других логических языков, например языка Рефал [5].

Типичный способ представления данных – таблица, она состоит из строк, а строки – из полей. Проводя аналогию с языком Пролог: поля – это аргументы терма, строки – это факты, а таблицы – предикаты, рис.1.
Т
поле(‘ФИО’, фамилия).

поле(‘ФИО’, имя).

поле(‘ФИО’, отчество).



аблица «ФИО»


Фамилия

имя

отчество

Торндотар

Дария

Тор

Нотар

Ив

Фёрн





‘ФИО’(‘Торндотар’, ‘Дария’, ‘Тор’).

‘ФИО’(‘Нотар’, ‘Ив’, ‘Фёрн’).


Рис.1. Представление реляционной таблицы в Прологе.
Конечно, поля таблиц придётся хранить отдельно – в специальном предикате “поле”.

Отношения между таблицам

и задаются с помощью правил, также как представления (view) и процедуры.

На Прологе легко задаются отношения реляционной алгебры, пример на рис. 2.


select *

from ФИО

where Фамилия = “Торндотар”;






а)

forall( ‘ФИО’('Торндотар', A, B) ).

б)


Рис. 2. Отношение select на SQL (а) и на Прологе (б).
Как уже упоминалось, Пролог является языком обработки данных. Поэтому, например, после выполнения запроса на рис. 2б можно сразу обработать данные. Языки запросов не дают такой возможности.

Используя в качестве хранилища предикатов файлы на внешнем носителе можно получить большие объёмы данных для Пролог-машины. Для обмена данными между диском и памятью будет использоваться кэш данных.

Производительность

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

Распределение предикатов возможно двумя путями:

а) дублирование базы предикатов для всех узлах системы обработки данных;

б) распределение информации по узлам.

Пункт (б) более предпочтителен, поскольку он позволяет сэкономить на дисковом пространстве. Алгоритм распределения ресурсов распределяет данные и процессорное время по ходу вычислений.

Существует ряд алгоритмов распределения ресурсов: “распределитель-работники”, хэш-фрагментация и др. [6]. Из рассмотренных алгоритмов для реализации Пролог-системы был выбран алгоритм балансировки, зарекомендовавший себя в проекте FGCS (Fifth Generation Computer Systems) [4]. Этот алгоритм применяется для распределения базы предикатов логического языка, распараллеливания логического вывода и обладает почти линейной зависимостью производительности от числа процессоров.

Производительность сильно зависит от индексации базы предикатов, эта проблема подробно рассматривается в моей статье “Индексация предикатов в Прологе” [7].

Выводы

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

Новизна изложенного подхода состоит в объединении двух компонентов – языка программирования Пролог и базы данных с последующим получением нового качества параллельной Пролог-системы: хранимой распределенной базы предикатов на внешнем носителе.


Список литературы





  1. Хомоненко А.Д. и др., Базы данных. – Спб.: "КОРОНА принт", 2002, 672c.

  2. IF/Prolog / http://www.ifcomputer.co.jp/en/manuals5.2/home.html.

  3. А.А. Морозов, Логический анализ функциональных диаграмм в процессе интерактивного проектирования информационных систем: Диссертация на соискание учёной степени кандидата физико-математических наук, - Москва, 1998.

  4. Transforming CHIP Programs to KL1. Design and Implementation of the CHUKL Preprocessor, Konstantinos D. Varsamos; MSc Thesis, Department of Computer Science University of Bristol: September 1994.

  5. Метавычисления и их приложения (диссертация). С.Абрамов / ftp://ftp.botik.ru/pub/local/Sergei.Abramov/book.appndx/dissertation

  6. В.В. Воеводин, Вл.В. Воеводин, Параллельные вычисления. – Спб.: "БХВ-Петербург" , ISBN: 5-94157-160-7, 2004, 608 c.

  7. Я.О. Косьмина, Индексация предикатов в Прологе, 2004 / http://online.com.ua/~dart/notikoj/index_predicates.html.




Похожие:

Распределённая параллельная Пролог-система iconРаспределенная файловая система dfs osf
Распределенная файловая система dfs osf предназначена для обеспечения прозрачного доступа к любому файлу, расположенному в любом...
Распределённая параллельная Пролог-система iconЯзык Пролог Пролог (Prolog)
Пролог декларативный язык, который основывается на исчисление предикатов и при работе с которым необходимо описать ситуацию (правила...
Распределённая параллельная Пролог-система iconУдк 519. 688 Параллельная реализация генетического алгоритма оптимизации в гидрологических моделях трансформации стока
В работе для восстановления параметров классической модели трансформации речного стока по данным наблюдений применен генетический...
Распределённая параллельная Пролог-система icon3. Логическое программирование 2 Язык Пролог 2
Пролог является декларативным языком логического программирования. Он основывается на языке исчисления предикатов первого порядка...
Распределённая параллельная Пролог-система icon14. Язык Пролог. Решения задач
Программа предназначена для решения отдельной задачи. В связи с этим Пролог считается декларативным языком программирования
Распределённая параллельная Пролог-система iconМетодические рекомендации по работе с программным комплексом «Автоматизированная распределенная информационная система мониторинга образования» на уровне образовательного учреждения (ввод данных по учителям, классам, учащимся)
Для входа в систему необходимо открыть браузер (например, Internet Explorer, Mozilla Firefox, Opera)
Распределённая параллельная Пролог-система iconРаспределенная информационная система управления контингентом студентов
Это определяется сложностью структуры вуза и большим количеством бизнес-процессов, обеспечивающих его деятельность. Создание автоматизированной...
Распределённая параллельная Пролог-система iconСеминара детской театральной педагогики «Пролог Весна 2007»
Традиционный пятый фестиваль «Пролог-Весна» проходил с 10 по 13 мая 2007 года на площадке московской гимназии №45
Распределённая параллельная Пролог-система iconПараллельная реализация алгоритмов прямого и обратного вейвлет-преобразования одномерного сигнала
Рассмотрена параллельная реализация операций прямого и обратного вейвлет-преобразования одномерного сигнала, позволяющая существенно...
Распределённая параллельная Пролог-система iconМетодическое пособие по программированию в системе Пролог для вычислительных машин типа ibm pc, работающих в операционной системе ms-dos или ms windows95/NT
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org