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



              

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


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

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

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

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

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

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


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