Параллельное программирование



              

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


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

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

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

Пусть ВС содержит 8 процессоров (0—7). Тогда процесс параллельной обработки цели в нашем примере можно представить табл. 1.1.

Таблица 1.1.

№ полученного фрейма№ обработанного фреймаОбрабатывающие процессыПул фреймовСчетчикСвязывание переменных
0дядя(X,Y) (ЦЕЛЬ)1X=?, Y=?
100брат(X,P), родитель(P,Y)1
211мужчина(X), родитель(Q,X), родитель(Q,P), X <> P,родитель(P,Y)5
320родитель(Q,иван), родитель(Q,P), иван <> P, родитель(P,Y)7X=иван, Y=?
422родитель(Q,василий), родитель(Q,P), василий <> P, родитель(P,Y)7X=василий, Y=?
523родитель(Q,петр), родитель(Q,P), петр <> P, родитель(P,Y)7X=петр, Y=?
624родитель(Q,федор), родитель(Q,P), федор <> P, родитель(P,Y)7X=федор, Y=?
725родитель(Q,юрий), родитель(Q,P), юрий <> P, родитель(P,Y)X=юрий, Y=?
836родитель(марья,P), иван <> P, родитель(P,Y)7X=иван, Q=марья, Y=?
37,0,1,2не проходит унификация
933родитель(петр,P), иван <> P, родитель(P,Y)7X=иван, Q=петр, Y=?
34не проходит унификация
45,7не проходит унификация
1040родитель(марья,P), василий <> P, родитель(P,Y)7X=василий, Q=марья, Y=?
41,2,4,6не проходит унификация
53,5,7,1,2,4,6не проходит унификация (у петра нет родителей)
60,1,2,3,4,5,6не проходит унификация
77,0,1,2,3,4не проходит унификация
1175родитель(федор,P), юрий <> P, родитель(P,Y)7X=юрий, Q=федор, Y=?
86не проходит унификация
87не проходит унификация
1280родитель(василий,Y)7X=иван, Q=марья, P=василий
81,2,3,4не проходит унификация
95,7,1,2не проходит унификация
1393родитель(ирина,Y)7X=иван, Q=петр, P=ирина
94,6не проходит унификация
14100родитель(иван,Y)7X=василий, Q=марья, P=иван
101,2,5,6,7,3не проходит унификация
114,1,3не проходит унификация
15115родитель(марья,Y)7X=юрий, Q=федор, P=марья
116,7,0не проходит унификация
122,5,6,7,3,1,4не проходит унификация
130,1,2,3,4,5,6не проходит унификация
140не проходит унификация
141цель исчерпана, решение:X=василий,Y=елена
142,3,4,5,6не проходит унификация
150цель исчерпана, решение:X=юрий,Y=иван
151не проходит унификация
152цель исчерпана, решение:X=юрий,Y=василий
153,4,5,6не проходит унификация

Здесь порядок загрузки процессоров обусловлен немедленной выборкой фрейма, как только он получен. Выбрать другой процессор может раньше, чем тот процессор, который его получил, т.к. ему еще надо закончить программный цикл после записи в БЗ.




Содержание  Назад  Вперед