Реализация языка логического программирования ПРОЛОГ на ВС SPMD-архитектуры
Рассмотрим упрощенную задачу в виде ПРОЛОГ-программы, содержащую все характерные элементы решения задачи удовлетворения (сложной) цели на основе базы знаний.
Задан фрагмент БЗ, содержащий факты и правила.
(Факты-клозы (отдельные предикаты-высказывания принято называть клозами), которые не содержат правых частей, правила-клозы, которые содержат правые части; одноименные факты и правила объединяются в процедуры.) Для единообразия и в соответствии с исключением факта из цели при связывании переменных обозначим факты так же, как и правила, но с "пустыми" правыми частями.
База знаний
Процедура "мужчина": мужчина (иван):- мужчина (василий):- мужчина (петр):- мужчина (федор):- мужчина (юрий):-
Процедура "женщина": женщина (марья):- женщина (ирина):- женщина (ольга):- женщина (елена):-
Процедура "родитель": родитель (марья, иван):- (Читать: "Марья — родитель Ивана") родитель (иван, елена):- родитель (марья, василий):- родитель (федор, марья):- родитель (петр, ирина):- родитель (петр, иван):- родитель (федор, юрий):-
Процедура "мать": мать (X, Y):-женщина (X), родитель (Y)
Процедура "отец": отец (X, Y):-мужчина (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)
Вновь входим в процедуру "родитель", но не находим там клоза, в котором василий указан как чей-либо родитель.
Т.е. вновь не проходит унификация — установление совместимости варианта связывания переменных.
Возвращаемся на шаг ветвления назад. (Реализуем стратегию поиска с ветвлением и возвращением назад — backtraking) На втором уровне ветвления пробуем клоз, в котором иван указан как сын: родитель (петр, иван). Цель трансформируется в следующий фрейм
родитель (петр, Р), иван <> P, родитель (P, Y).
Вновь (на третьем уровне ветвления) обращаемся к процедуре "родитель" и выбираем первый клоз, в котором петр указан как отец — родитель (петр, ирина). Цель трансформируется:
иван <> ирина, родитель (ирина, Y)
Входим в процедуру "родитель", но не находим там клоза, в котором ирина указана как родитель. (Не проходит унификация.)
Возвращаемся на второй уровень ветвления и не находим там больше клозов, где иван указан как сын. Возвращаемся на первый уровень ветвления и в процедуре "мужчина" выбираем для последующего испытания следующий клоз мужчина (василий). Цель принимает вид (фрейм)
родитель (Q, василий), родитель (Q, P), василий <> Р, родитель (P, Y).
Теперь на втором уровне ветвления находим первый (и единственный) клоз, в котором василий указан как сын. Цель трансформируется в соответствии с новым связыванием переменных, обусловленным найденным клозом родитель (марья, василий):
родитель (марья, Р), василий <> P, родитель (P, Y).
На третьем уровне ветвления находим первый клоз, где марья — родитель: родитель (марья, иван). Связываем тем самым переменные, цель трансформируется
василий
Находим в процедуре "родитель" первый клоз, в котором иван указан как родитель - родитель (иван, елена). Цель выродилась, значит
дядя (X, Y) = дядя (василий, елена) — одно из решений задачи.
Продолжив перебор так, словно на данном шаге унификация не прошла, можно найти остальные решения : дядя (юрий, иван), дядя (юрий, василий).
В основе распараллеливания решения этой задачи лежит способ размножения вариантов на основе трансформации цели.
Способ обеспечивает: отсутствие "backtracing'а" (ветвление есть, а возврата назад нет); простоту самой процедуры вывода; возможность неограниченного использования ИЛИ-параллелизма (одновременной независимой обработки многих вариантов связывания переменных); конвейерную реализацию И-параллелизма (распараллеливания обработки одного варианта связывания переменных на конвейере, т.к. каждый раз обрабатывается лишь первый предикат каждого фрейма). Поясним это подробнее.
Пусть в общей памяти ВС размещен пул фреймов - промежуточных результатов трансформации цели, т.е. варианты связывания переменных. Отсюда уже видно, что в системе формируется не один очередной, а сразу несколько вариантов преобразования цели, а затем — и преобразования образующихся фреймов.
Первоначально этот пул образует единственный фрейм — цель. Все процессоры "смотрят" на пул фреймов, и каждый процессор выбирает для обработки тот из них, первый предикат в котором допускает замену его правой частью в процедуре с именем этого предиката.
Произведя преобразование этого предиката, процессор производит унификацию (т.е. анализ на непротиворечивость варианта связывания переменных) и при ее успешном выполнении дополняет сформированным фреймом пул фреймов, отдельно размещая соответствующий этому фрейму вариант связывания переменных.
Допустимо согласование работы процессоров, такое, при котором два процессора, выбрав один и тот же фрейм, произведут разную замену исходя из количества клозов в соответствующей процедуре. Для этого при каждом фрейме указывается информация о количестве процессоров (формируется счетчик), которые могут одновременно (условно, т.к. с участием этого счетчика начала обращений процессоров к одной процедуре образуют последовательность) приступить к обработке этого фрейма.
Ясно, что таким образом легко и естественно реализуется так называемый ИЛИ-параллелизм на основе размножения и одновременной обработки вариантов трансформации цели. При этом явная реализация "backtraking'а" не нужна: она сдерживала бы возможности распараллеливания.
В то же время обработка каждого фрейма одним процессором заключается в преобразовании единственного — первого предиката. Таким образом, в целом каждый фрейм подвергается конвейерной обработке — реализуется конвейерный способ И-параллелизма.
Процесс размножения вариантов не может привести к беспредельной загрузке памяти, т.к., во-первых, многие варианты отсекаются процедурой унификации; во-вторых, фреймы, в которых первые предикаты обработаны, могут быть исключены из пула: они породили все возможные новые фреймы; в-третьих, на основе некоторых фреймов, в частности, при их вырождении, выдается заключение о решении.
Таким образом, возможен динамический возврат памяти в систему.
Пусть ВС содержит 8 процессоров (0—7). Тогда процесс параллельной обработки цели в нашем примере можно представить табл. 1.1.
| 0 | дядя(X,Y) (ЦЕЛЬ) | 1 | X=?, Y=? | ||
| 1 | 0 | 0 | брат(X,P), родитель(P,Y) | 1 | |
| 2 | 1 | 1 | мужчина(X), родитель(Q,X), родитель(Q,P), X <> P,родитель(P,Y) | 5 | |
| 3 | 2 | 0 | родитель(Q,иван), родитель(Q,P), иван <> P, родитель(P,Y) | 7 | X=иван, Y=? |
| 4 | 2 | 2 | родитель(Q,василий), родитель(Q,P), василий <> P, родитель(P,Y) | 7 | X=василий, Y=? |
| 5 | 2 | 3 | родитель(Q,петр), родитель(Q,P), петр <> P, родитель(P,Y) | 7 | X=петр, Y=? |
| 6 | 2 | 4 | родитель(Q,федор), родитель(Q,P), федор <> P, родитель(P,Y) | 7 | X=федор, Y=? |
| 7 | 2 | 5 | родитель(Q,юрий), родитель(Q,P), юрий <> P, родитель(P,Y) | X=юрий, Y=? | |
| 8 | 3 | 6 | родитель(марья,P), иван <> P, родитель(P,Y) | 7 | X=иван, Q=марья, Y=? |
| 3 | 7,0,1,2 | не проходит унификация | |||
| 9 | 3 | 3 | родитель(петр,P), иван <> P, родитель(P,Y) | 7 | X=иван, Q=петр, Y=? |
| 3 | 4 | не проходит унификация | |||
| 4 | 5,7 | не проходит унификация | |||
| 10 | 4 | 0 | родитель(марья,P), василий <> P, родитель(P,Y) | 7 | X=василий, Q=марья, Y=? |
| 4 | 1,2,4,6 | не проходит унификация | |||
| 5 | 3,5,7,1,2,4,6 | не проходит унификация (у петра нет родителей) | |||
| 6 | 0,1,2,3,4,5,6 | не проходит унификация | |||
| 7 | 7,0,1,2,3,4 | не проходит унификация | |||
| 11 | 7 | 5 | родитель(федор,P), юрий <> P, родитель(P,Y) | 7 | X=юрий, Q=федор, Y=? |
| 8 | 6 | не проходит унификация | |||
| 8 | 7 | не проходит унификация | |||
| 12 | 8 | 0 | родитель(василий,Y) | 7 | X=иван, Q=марья, P=василий |
| 8 | 1,2,3,4 | не проходит унификация | |||
| 9 | 5,7,1,2 | не проходит унификация | |||
| 13 | 9 | 3 | родитель(ирина,Y) | 7 | X=иван, Q=петр, P=ирина |
| 9 | 4,6 | не проходит унификация | |||
| 14 | 10 | 0 | родитель(иван,Y) | 7 | X=василий, Q=марья, P=иван |
| 10 | 1,2,5,6,7,3 | не проходит унификация | |||
| 11 | 4,1,3 | не проходит унификация | |||
| 15 | 11 | 5 | родитель(марья,Y) | 7 | X=юрий, Q=федор, P=марья |
| 11 | 6,7,0 | не проходит унификация | |||
| 12 | 2,5,6,7,3,1,4 | не проходит унификация | |||
| 13 | 0,1,2,3,4,5,6 | не проходит унификация | |||
| 14 | 0 | не проходит унификация | |||
| 14 | 1 | цель исчерпана, решение: | X=василий,Y=елена | ||
| 14 | 2,3,4,5,6 | не проходит унификация | |||
| 15 | 0 | цель исчерпана, решение: | X=юрий,Y=иван | ||
| 15 | 1 | не проходит унификация | |||
| 15 | 2 | цель исчерпана, решение: | X=юрий,Y=василий | ||
| 15 | 3,4,5,6 | не проходит унификация |
