---

Разделы На главную История денег и экономики История экономических знаний Формы безналичных денег Международные финансы Экономические концепции Экономические теории Экономика в реальной жизни Экономический анализ и интеграция Макроэкономика Экономика и социальное общество Социальная экономика Социология Кризисная экономика Инфляция в экономике Экономика зарубежных стран Иностранные деньги Государственное регулирование Бюджетная система Политическая экономия Политология Законы денег Налогообложение Аудит Банкротство Теория рынка Конкуренция Международная торговля Товарная биржа Нефть и газ на бирже Логистика Банки - услуги и операции Банки в России Банковский кредит Недвижимость Ипотека в банке Инвестирование Стратегии инвестирования Инвестиционные фонды Ценные бумаги Акции Вексель Облигации Опционы Фьючерсы Биржевая торговля Биржа Forex Фондовый рынок Фондовый рынок России Волны Эллиотта Теория фракталов Торговая теория Ганна Фибоначчи на бирже Графический анализ на бирже Паттерны Биржевой анализ "Крестики-нолики" Японские свечи Технический анализ Математика на бирже Фундаментальный анализ Биржевая торговля Стратегии торговли Механические торговые системы Программирование МТС Управление торговым капиталом Управление портфелем Управление риском Страхование Профессия трейдер Практический трейдинг Технологии инфосистем Информационный рынок Безопасность информации Криптология и криптография Реклама PR - Public Relations Маркетинг Финансовая система Начало бизнеса Предпринимательство Малый бизнес Микроэкономика Торговля Ценообразование Работа в Интернете Сайты, софт, дизайн Управление качеством Управление предприятием Производство продукции Стратегический менеджмент Учебники по менеджменту Системы и организации Теория систем Планирование Статистика финансов Управление персоналом Трудовые отношения Бухгалтерия «1С:Бухгалтерия» Управленческий учет Делопроизводство и офис Автоматизация делопроизводства Рынок труда Карьера Менеджер Лидерство и бизнес карьера Лидерство и карьера Общение и переговоры Общение в бизнесе Бизнес переговоры Инновации в моделировании Экономическое моделирование Нейронные сети Нейролингвистика Логика нейросетей Программирование Пакет Excel Технологии программирования Языки программирования Практическая психология Психологические тренинги Психология в медицине Возрастная психология Ваши скрытые резервы Здоровье и долголетие Работа с эмоциями Пикап Управление временем Гипнотерапия Подсознание Трансовые техники Магия Здоровье советы Спорт для здоровья Йога Религии Эзотерика Мистицизм

---

Реализация языка логического программирования ПРОЛОГ на ВС 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)

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

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


Т.е. вновь не проходит унификация — установление совместимости варианта связывания переменных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В основе распараллеливания решения этой задачи лежит способ размножения вариантов на основе трансформации цели.


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

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

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

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

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

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


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

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

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

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

Таблица 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	не проходит унификация

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

---