Реализация языка логического программирования ПРОЛОГ на ВС SPMD-архитектуры

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

Задан фрагмент БЗ, содержащий факты и правила.

База знаний

Процедура "мужчина":
  мужчина (иван):-
  мужчина (василий):-
  мужчина (петр):-
  мужчина (федор):-
  мужчина (юрий):-
  
Процедура "женщина":
  женщина (марья):-
  женщина (ирина):-
  женщина (ольга):-
  женщина (елена):-
  
Процедура "родитель":
  родитель (марья, иван):-  (Читать: "Марья — родитель Ивана")
  родитель (иван, елена):-
  родитель (марья, василий):-
  родитель (федор, марья):-
  родитель (петр, ирина):-
  родитель (петр, иван):-
  родитель (федор, юрий):-
  
Процедура "мать":  
  мать (X, Y):-женщина (X), родитель (X,Y)
  
Процедура "отец":  
  отец (X, Y):-мужчина (X), родитель (X,Y)
  
Процедура "брат":  
  брат (X, Y):-мужчина (X), родитель (P,X), родитель(P,Y), X <> Y  
  
Процедура "сестра":  
  сестра (X, Y):-женщина (X), родитель (P,X), родитель(P,Y), X <> Y  
  
Процедура "дядя":
  дядя(X,Y):-брат(X,P), родитель(P,Y)

Пусть задана некоторая сложная (т.е. опирающаяся не на факт, а требующая вывода) цель, с которой мы обратились в эту БЗ, например

дядя (X, Y) (запись цели образует фрейм

решение которой (вывод) заключается в нахождении всех пар переменных (имен объектов) X и Y, для которых справедливо утверждение

"X является дядей Y".

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

Т.е. для решения данной задачи необходимо действовать следующим образом.

Находим первый (и единственный) предикат цели дядя (X, Y). Находим в БЗ процедуру с этим именем и заменяем найденный предикат правой частью этой процедуры. Получим трансформируемую цель — фрейм

брат (X, P), родитель (P, Y).

К первому предикату этого фрейма применяем аналогичные действия, получаем фрейм

мужчина (X), родитель (Q, X), родитель (Q, P), X <> P, родитель (P,Y)

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

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

родитель (Q, иван), родитель (Q, P), иван <> P, родитель(P,Y)

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

родитель (марья, Р), иван <> P, родитель (P, Y).

Вновь входим в процедуру "родитель" (третий уровень ветвления), находим клоз shape родитель (марья, иван). Трансформируем цель — получаем новый фрейм:

иван <> иван, родитель (иван, Y).

Имеем противоречие, т.е. не проходит унификация.

Ищем на данном шаге ветвления другой вариант связывания, находим следующий клоз

родитель (марья, василий)

Трансформируем цель:

иван <> василий, родитель (василий, Y) ->  родитель (василий, Y).

Вновь входим в процедуру "родитель", но не находим там клоза, в котором василий указан как чей-либо родитель. Т.е. вновь не проходит унификация — установление совместимости варианта связывания переменных.

Возвращаемся на шаг ветвления назад. (Реализуем стратегию поиска с ветвлением и возвращением назад — backtraking ) На втором уровне ветвления пробуем клоз, в котором иван указан как сын: родитель (петр, иван). Цель трансформируется в следующий фрейм

родитель (петр, Р), иван <> P, родитель (P, Y).

Вновь (на третьем уровне ветвления) обращаемся к процедуре "родитель" и выбираем первый клоз, в котором петр указан как отец — родитель (петр, ирина). Цель трансформируется:

иван <> ирина, родитель (ирина, Y)  ->  родитель (ирина, Y)

Входим в процедуру "родитель", но не находим там клоза, в котором ирина указана как родитель. (Не проходит унификация.)

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

родитель (Q, василий), родитель (Q, P), василий <> Р, родитель (P, Y).

Теперь на втором уровне ветвления находим первый (и единственный) клоз, в котором василий указан как сын. Цель трансформируется в соответствии с новым связыванием переменных, обусловленным найденным клозом родитель (марья, василий):

родитель (марья, Р), василий <> P, родитель (P, Y).

На третьем уровне ветвления находим первый клоз, где марья — родитель: родитель (марья, иван). Связываем тем самым переменные, цель трансформируется

василий -> иван, родитель (иван, Y) ->  родитель (иван, Y).

Находим в процедуре "родитель" первый клоз, в котором иван указан как родитель - родитель (иван, елена). Цель выродилась, значит

дядя (X, Y) = дядя (василий, елена) — одно из решений задачи.

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

В основе распараллеливания решения этой задачи лежит способ размножения вариантов на основе трансформации цели. Способ обеспечивает: отсутствие "backtracing'а" (ветвление есть, а возврата назад нет); простоту самой процедуры вывода; возможность неограниченного использования ИЛИ-параллелизма (одновременной независимой обработки многих вариантов связывания переменных); конвейерную реализацию И-параллелизма (распараллеливания обработки одного варианта связывания переменных на конвейере, т.к. каждый раз обрабатывается лишь первый предикат каждого фрейма). Поясним это подробнее.

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

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

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

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

Ясно, что таким образом легко и естественно реализуется так называемый ИЛИ-параллелизм на основе размножения и одновременной обработки вариантов трансформации цели. При этом явная реализация "backtraking'а" не нужна: она сдерживала бы возможности распараллеливания. В то же время обработка каждого фрейма одним процессором заключается в преобразовании единственного — первого предиката. Таким образом, в целом каждый фрейм подвергается конвейерной обработке — реализуется конвейерный способ И-параллелизма.

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

Таким образом, возможен динамический возврат памяти в систему.