Нахождение последнего элемента списка
Одним из наиболее часто используемых способов организации информации в памяти ЭВМ является ее представление в виде списков, которые позволяют оперировать не с самими величинами, а с их адресами, что облегчает программирование, экономит память и сокращает затраты на пересылку информации. С помощью списков удобно отображать данные самой разнообразной структуры: множества, деревья, графы, строки и т.д.
Основными операциями над списками являются: получение доступа к произвольному элементу списка; включение нового элемента в заданное место списка и исключение его оттуда; сортировка элементов списка; поиск элемента с заданными свойствами и другие. Простота их реализации является одним из наиболее привлекательных свойств списковой организации данных. Однако традиционное представление списков на основе ссылок предполагает последовательную обработку их элементов. Все известные алгоритмы, реализующие операции над списками, являются последовательными и ориентированы на однопроцессорные ЭВМ фон-неймановской архитектуры.
Эффективная реализация операций над списками для параллельных вычислительных систем представляет непростую (а для некоторых архитектур — например, векторно-конвейерной — и неразрешимую) задачу. Особый интерес представляла бы разработка таких алгоритмов для ВС с большим числом процессорных элементов.
Под списком L будем понимать совокупность объектов вида In =(V, C), где V — ссылка на данные, C — ссылка на некоторый (следующий) элемент этого же списка. Последний элемент списка имеет своим значением nil, т.е. пустую ссылку.
Пусть элементы каждой двойки (V, C) расположены в памяти так, что их адреса определяются сложением фиксированного смещения с некоторым базовым адресом. Тогда совокупность всех двоек можно рассматривать как массив R — образ списка, в котором места расположения каждого элемента могут быть рассчитаны.
Интуиция подсказывает, что параллельная обработка списка невозможна, поскольку в общем случае необходимо вычислить адреса k предыдущих элементов списка, прежде чем станет доступен (k+1)-й элемент.
Однако, она становится возможной, если использовать образ списка.
Модифицируем представление каждого элемента массива R, введя дополнительное поле D, в которое заносится ссылка на соответствующее поле того элемента списка, ссылка на который содержится в поле C. Строить образ списка целесообразно одновременно с формированием и изменением самого списка. Таким образом, элемент образа списка превращается в тройку (F, C, D). На рис. 1.1
структура элемента образа списка представлена в графической форме.
Рис. 1.1. Элемент образа списка
На рис. 1.2,а изображен список, соответствующий записи L = (A B E F G H Г) (для простоты считаем, что он не содержит подсписков).
Рис. 1.2. Пошаговое нахождение последнего элемента списка (последовательное расположение элементов в памяти)
Пусть над всеми его элементами последовательно, начиная с головы, производится следующее действие: поле D текущего элемента принимает значение того поля D, на которое указывает содержащаяся в нем ссылка (если в поле D содержится ссылка на пустой элемент, то его значение не изменяется). В результате список L примет вид, показанный на рис. 1.2,б. Вид списка L после второго прохода показан на рис. 1.2,в. И, наконец, после третьего прохода поле D головы списка будет содержать ссылку на последний элемент списка L, на чем выполнение алгоритма заканчивается (рис. 1.2,г).
Предположим теперь ситуацию, когда элементы списка расположены в памяти в произвольном порядке, например, так, как показано на рис. 1.3,а.
Рис. 1.3. Пошаговое нахождение последнего элемента списка (произвольное расположение элементов в памяти)
Важно, что преобразования не изменяют структуру списка, поскольку действия производятся над "избыточной" информацией; при этом на правильность выполнения алгоритма не влияет порядок расположения элементов в памяти.
Заметим теперь, что все операции над образом списка R, производимые во время одного прохода, могут быть выполнены параллельно и независимо друг от друга, то есть, при наличии достаточного вычислительного ресурса, за один временной шаг.
Таким образом, мы получаем доступ к последнему элементу списка за log2N шагов. Аналогичные алгоритмы, также использующие информационную избыточность, могут быть построены и для других операций над списками.
Реализация операций над списками для локально-асинхронной ВС, каковой является ВС SPMD-архитектуры, допускает использование принципа монопрограммирования, т.е. составления единственной программы, запускаемой на всех процессорах одновременно. Здесь мы приведем монопрограмму нахождения последнего элемента списка и проследим процесс ее выполнения. Она выбрана потому, что нахождение последнего элемента является частью многих операций над списками. Например, для объединения списков L1 и L2 достаточно найти последний элемент списка L1 и заменить в его поле C пустую ссылку ссылкой на первый элемент списка L2.
Как говорилось выше, для организации параллельной обработки целесообразно использовать образ R списка — массив информации об элементах списка, содержащий сведения о его структуре и преемственности элементов. Отметим, что упорядоченность элементов массива R в памяти в общем случае может не совпадать с логической упорядоченностью элементов списка, задаваемой ссылками. Это позволяет достаточно просто интерпретировать выполнение операций над списками. Например, при добавлении новых элементов в список L нет необходимости вставлять новый элемент массива R в какую-либо конкретную позицию - можно просто добавить его в конец массива. Аналогично, при исключении элемента из L вместо уплотнения массива R на освободившееся место можно записать его последний элемент.
Обработку списка, таким образом, мы сводим к обработке массива, представляющего его образ. Этот массив, в свою очередь, может описываться дескриптором.
Дескриптор DR массива R={V,C,D}1^N в полной комплектации, как рассматривалось ранее, состоит из восьми элементов: DR={DRO , ..., DR7}. Дескрипторный элемент DRO содержит адрес a0 первого элемента массива, DR1 — шаг h = 3 переадресации, DR2 — количество N элементов массива, в DR3 находится адрес последнего элемента массива.
Элемент DR4 служит для переадресации при последовательном обращении к данному массиву. В нем хранится адрес aQ+jh для выработки элемента массива при j-м (j = 0,1 , ..., n-1) обращении к массиву. При каждом обращении к массиву по некоторым командам этот адрес увеличивается на шаг h (т.е. выполняется операция j := h+!). Остальные дескрипторы предназначены для организации распределения элементов массива между процессорами. DR5
содержит значение адреса aQ+ih, i = 0,1 , ..., n-1, т.е. каждый процессор Пi формирует и использует свое значение (DR5), располагая адресом регистра, содержащего значение номера i процессора, для начального обращения к "своему" элементу массива. DR6 содержит значение nh, используемое для переадресации к следующему "своему" элементу массива с учетом числа процессоров в ВС. В DR7 содержится значение адреса aQ+ih+jnh=(DR5)+j(DR6), используемое для возможности переадресации при последовательном (j = 0,1,...) обращении к массиву. Если нет необходимости, могут формироваться не все дескрипторные элементы.
Предположим, как и ранее, что в ВС реализована трехадресная система команд вида: ? I1 A1 12 A2 I3 A3, где ? — код операции, I1, I2, I3 — адреса модификаторов, дескрипторных элементов или дескрипторов, A1, A2, A3 — смещения. При выполнении команд формируются исполнительные адреса: A'r =(Ir)+ Ar, r = 1,2,3.
Для упрощения операций над дескрипторами в систему команд введены специальные команды, обеспечивающие переадресацию для различных дисциплин выбора "своих" элементов обрабатывающим процессором, анализ выхода за пределы массива, инвариантность программы относительно размера массива.
Монопрограмма нахождения последнего элемента списка представлена в табл. 1.2.
| СИНХ | ||||||
| ЗАГ | K | |||||
| ПРАД | DR7 | 012 | ||||
УП | K | 012 | ||||
| ЗАПК | DR7 | 0003 | M | |||
| УП=0 | M | 011 | ||||
| ЗАПК | M | DR7 | 0003 | |||
| ИЗМАД | DR7 | 009 | ||||
| БП | 003 | |||||
| ЗАГ | DR7 | DR5 | ||||
| БП | 0003 | |||||
| ЗАП | DR7 | 0003 | K | |||
| В |
Каждый процессор посылает сигнал на устройство СИНХ; после поступления сигналов от всех процессоров выдается обратный сигнал, по которому процессоры приступают к выполнению следующей команды.
Команда 1 (ЗАГрузка модификатора) обнуляет модификатор K, в который впоследствии одним из процессоров будет записан адрес последнего элемента списка.
Команда 2 (ПРоверка АДреса) сравнивает значение дескрипторного элемента DR1, первоначально равное a0+3i, с адресом последнего элемента массива, записанным в дескрипторном элементе DR3. Этим устанавливается возможность загрузки i-го процессора (возможен случай i>N). Если процессор не будет занят обработкой списка, то управление передается команде 12 на Выход из процедуры. В противном случае с команды 3 начинается цикл обработки элементов списка, а точнее — его последовательности ссылок. Команда 3 осуществляет Условный Переход на выход из процедуры по отличному от нуля значению K.
Команда 4 выполняется при нулевом значении K, она осуществляет ЗАПись по Косвенному адресу. При этом производится косвенное считывание по первому адресу (DR7) + 0003, т.е. по адресу ((DR7)+0003), и запись по адресу модификатора M.
Команда 5 проверяет, пуста ли выбранная ссылка. Если пуста, то анализируемый элемент списка - последний; управление передается команде 11, записывающей адрес этой ссылки в K. Если не пуста, т.е. (M)\neq 0, то выполняется команда 6 и ее значение записывается вместо значения текущей ссылки.
Команда 7 ИЗМенение АДреса задает операцию (DR7):=(DR7)+(DR6) и если полученное значение превышает (DR3), передает управление команде 9. Таким образом, каждый процессор осуществляет переадресацию для последующей выборки "своего" адреса ссылки из массива таких адресов. Если при этом массив не исчерпан, то команда 8 (Быстрый Переход) передает управление на команду 3 — продолжение цикла подстановки ссылок. Если переадресация выводит из массива, то команда 9 восстанавливает дескрипторный элемент DR7 , т.е. выполняется операция (DR7):= (DR5) = a0+3i.
По команде 10 управление передается на следующий цикл подстановки ссылок.
Команда 11 выполняется, если при выполнении команды 5 обнаружилось, что найдена пустая ссылка, адрес которой записывается в K. После выполнения в последующем команды 3 всеми процессорами закончится и выполнение программы.
Рассмотрим процесс счета программы нахождения последнего элемента списка L, содержащего семь элементов, на ВС, имеющей в составе три процессора — П0, П1 и П2.
Каждый процессор выполняет свою копию программы, обладая при этом собственным набором дескрипторов, отличающихся друг от друга только значениями дескрипторных элементов DR5 и DR7. Согласно принятому нами представлению образа списка и порядку его обработки, процессор П0 будет обрабатывать элементы списка A, F и I, процессор П1 — B и G, и процессор П2 — элементы E и H. Пусть каждая команда программы выполняется за одинаковое время — условный такт, и при обращении к памяти не возникает конфликтов (все элементы образа списка расположены в разных блоках памяти).
На рис. 1.4 показана диаграмма потактового выполнения программы на каждом из процессоров, полученная при справедливости этих предположений. Некоторое время все процессоры работают синхронно: такты 1—3 — начальные действия; такты 4—9 — первый цикл подстановки ссылок, во время которого изменяются поля D элементов A, B и E; такты 10—12 — начало второго цикла подстановки ссылок.
Рис. 1.4. Временная диаграмма выполнения программы нахождения последнего элемента списка
Во время второго цикла подстановки ссылок процессор П2 обнаруживает пустую ссылку (т.е. последний элемент списка) в такте 12 и, записав его адрес в модификатор K (такт 13), заканчивает свою работу в следующем такте командой Возврат.
Процессор П0 заканчивает второй цикл подстановки ссылок (такты 13—15), не обнаружив пустой ссылки, но завершает свою работу в тактах 16 и 17, поскольку модификатор K получил уже к этому времени ненулевое значение.
Процессор П1 в такте 14 изменяет значение дескрипторного элемента DR7 и, так как оно выводит за границы обрабатываемого массива, в такте 15 восстанавливает его исходное значение.
Далее следует переход на начало третьего цикла обработки ссылок (такт 16), но, обнаружив ненулевое значение модификатора K (такт 17), в следующем такте процессор П1 также завершает свою работу. Результатом совместной работы трех процессоров является адрес ссылки на последний элемент списка, записанный в модификаторе K.
Заметим, что детерминированный — при синхронной работе процессорных элементов — процесс выполнения алгоритма при реализации на локально-асинхронной ВС приобретает некоторую неопределенность. Дело в том, что мы не можем быть уверены в порядке выполнения процессорами операций замены значений ссылок (команда 6), поскольку в принципе не исключены обращения к одним и тем же модулям общей памяти. В результате какой-либо процессор может "подхватить" уже обновленную ссылку. Однако очевидно, что это только приблизит окончание работы алгоритма, который в таком случае как бы "перескакивает" через некоторые шаги. Например, элемент A, обрабатываемый процессором П0, после первого выполнения процессором команды 6 должен содержать ссылку на элемент E. Но если процессор П1 успел по какой-либо причине выполнить свою аналогичную операцию раньше, элемент A будет содержать ссылку на более "удаленный" от него элемент F. Поэтому появляется возможность более раннего достижения условия окончания работы программы.
Здесь иллюстрируется не всегда ясно сознаваемый факт, что принципы параллельной обработки информации могут быть использованы для нахождения самого общего решения задач, по своей природе, казалось бы, не распараллеливаемых. Эффективность параллельной обработки списков в данном случае достигается двумя встречными путями: дополнением традиционного подхода концепцией обработки массивов и использованием архитектурных особенностей ВС, реализующей SPMD-технологию.
Поиск и исключение элемента списка
Пусть задано имя S некоторого элемента списка, являющееся первым словом в массиве его данных, на которое указывает одна из ссылок C в массиве R троек (V, C, D). Необходимо по заданному S найти соответствующий ему элемент списка, т.е. такой, данные которого начинаются с S, и исключить его из списка. Для этого достаточно заменить значение ссылки C в одной из троек в массиве R, указывающей на исключаемый элемент, на значение ссылки, указанное в тройке, которая соответствует исключаемому элементу. При этом тройка, соответствующая исключаемому элементу, в свою очередь должна быть исключена из массива R.
Совместные действия процессоров можно организовать следующим образом.
Пусть все процессоры "смотрят" на соответствующие им по номеру (а затем — кратные им по номеру) элементы массива R. Какой-то из них найдет элемент, ссылка в котором указывает на элемент списка, где первое слово совпадает с S. Эта ссылка заменяется тем же процессором на ссылку, указанную в исключаемом элементе, а сам элемент массива R, соответствующий исключенному элементу, исключается из R. После этого корректируется дескриптор, соответствующий массиву R.
Проанализируем работу программы, представленной в табл. 1.3.
| СИНХ | ||||||
| <i> | 003 | ||||
| ЗАГ | K | |||||
| ПРАД | DR7 | 010 | ||||
| ЗАП | DR7 | 0002 | M1 | |||
| ЗАПК | M1 | 0001 | M2 | |||
| M2 | S | 011 | |||
| ЗАГ | K | 0001 | ||||
| ЗАП | M1 | 0002 | DR7 | 0002 | ||
| ИСКЛ | DR | M1 | ||||
| В | ||||||
| K | 010 | ||||
| ИЗМАД | DR7 | 010 | ||||
| БП | 004 |
По команде 0 производится синхронизация процессоров ВС.
По командам 1 и 2 модификатору K присваивается нулевое значение. Эту операцию выполняет процессор 0. Другие процессоры по команде 1, в которой номер i процессора сравнивается с нулем и выполняется условный переход по неравенству, перейдут к выполнению команды 3. (Иллюстрируется возможность параллельной работы процессоров по разным ветвям монопрограммы.)
По команде 3 осуществляется выход из программы, если значение текущего адреса в дескрипторном элементе DR7 превосходит значение текущего адреса последнего элемента массива R, записанное в DR3. Если DR7
Пусть ссылка, записанная в поле C, указывает на первый адрес в тройке, составляющей некоторый элемент R. Тогда по адресу (M1) + 1 находится адрес начала "тела" соответствующего элемента списка. Команда 5 выполняет запись по косвенному адресу этого начала в регистр M2.
По команде 6 начало тела анализируемого элемента списка сравнивается с исключаемым элементом, указанным в S.
При положительном результате сравнения по команде 7 модификатору K присваивается отличное от нуля значение, служащее индикатором того, что исключаемый элемент списка некоторым процессором найден. Если (M2)
По команде 8 ссылка, записанная в элементе массива R и соответствующая исключаемому из списка элементу, присваивается тому элементу, который ранее указывал на исключаемый, т.е. значение ((M1) + 2) присваивается элементу (DR7) + 2.
Команда 9 — ИСКЛючение из массива, описываемого дескриптором DR, элемента, расположенного по адресу (M1). В результате выполнения команды 4 по данному адресу находится элемент массива R, соответствующий исключаемому из списка элементу.
По команде 10 производится выход из подпрограммы.
Команда 11 получает управление в случае, если ссылка в анализируемом элементе массива R не указывает на исключаемый из списка элемент. В этом случае проверяется наличие признака того, что некоторый процессор обнаружил искомый элемент и готов исключить его из списка, т.е. если (K)
По команде 12 выполняется переадресация (DR7) := (DR7) + (DR6), где (DR6) = Nh. Если такая переадресация приводит к выходу за пределы массива, т.е. новое значение DR7 превышает значение последнего адреса массива R, указанное в DR3, производится выход из подпрограммы по команде 10.
В противном случае по команде 13 процессор приступает к анализу очередного элемента R.
В данном случае нам не пришлось в полной мере использовать существующие в системе средства синхронизации. Легко усложнить пример, рассмотрев случай, когда одновременно заданы несколько исключаемых элементов. Их исключение должно производиться последовательно, т.к. процессор, обнаруживший исключаемый элемент, должен располагать вполне определенной информацией о текущем состоянии списка, изменяемом в процессе исключения из него элементов. Ведь после каждого исключения может измениться и порядок последующего назначения элементов массива R на обработку процессорами.
Это приводит к необходимости выделения одной или группы команд исключения из списка (см. команду 9 данной монопрограммы) в критический блок, не допускающий одновременного обращения к нему более одного процессора. Формирование критического блока достигается выполнением в его начале команды ЗАКРыть Семафор с указанием адреса некоторого семафора C. Если при выполнении этой команды данный семафор уже закрыт другим процессором при выполнении этого же фрагмента программы, то процессор переходит в режим ожидания, "жужжания", т.е. повторного выполнения этой команды до открытия семафора.
Критический блок заканчивается командой ОТКРыть Семафор с указанием адреса того же семафора.
Реализация языка логического программирования ПРОЛОГ на ВС 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 | не проходит унификация |
