Параллельное программирование: Учебное пособие, страница 36

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

Абстрактной моделью параллельных вычислений с такой структурой программных фрагментов вершинных процессов может служить модель, основанная на следующих положениях и требованиях к аппаратной части вычислительных систем [9]:

Условием включения с-оператора (запуском процесса выполнения) является конъюнкция двух подусловий, одно из которых характеризует присутствие/отсутствие с-оператора в списке преемников, другое соответствует условию «индивидуального» включения для . Представление условия включения в виде двух указанных подусловий является принципиальной особенностью модели параллельных вычислений. В такой трактовке модель не противоречит также и записи любого последовательного алгоритма в виде последовательности с-операторов вида:

,                                                                                    (2.39)

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

В последовательности (2.39)  выполняет функции стартового оператора алгоритма. В каждый момент выполняется только один с-оператор, имя которого находится в регистре команд (РК), а список преемников содержит только один элемент.

Сущность РК для ветви параллельного алгоритма аналогична сущности РК процессора, выполняющего последовательную программу. Регистр команд может трактоваться как переменная, значение которой изменяется автоматически и в любой момент равно значению имени с-оператора, находящегося в состоянии выполнения.

В модели параллельных вычислений в любой момент времени для любого процесса должна существовать своя переменная типа РК, которая содержит имя очередного выполняющегося с-оператора. Множество таких переменных содержат имена всех активных в этот момент с-операторов. Каждому РК соответствует его собственный список преемников. Идея иметь множество регистров, наделенных функциями регистра команд, оказалась в своем развитии очень плодотворной, так как позволила организовать одновременную выборку из общей памяти и выполнение командных инструкций для нескольких параллельных ветвей. Правда, на аппаратном и программном уровнях ежеминутно пришлось разрешать спор отдельных процессов за обладание либо процессором, либо памятью, либо устройствами ввода/вывода... Именно в разрешении конфликтов была выработана и концепция отложенного завершения операций.

В свете описанной модели параллельный алгоритм, изменяющий состояние памяти  D , считается определенным, если задана четверка

,

где     конечное множество с-операторов над ;

подмножество стартовых операторов , начинающих выполнение в заданном конечном промежутке времени  (имя каждого из них появляется на своем  из множества );

множество стартовых (исходно заданных) , взаимно однозначно соответствующих элементам из ;

конечное множество операторов меж процессных взаимодействий, в котором оператор из множества операторов   может:

создавать новые  или уничтожать существующие,

назначать преемников на любом подмножестве , существующих в момент выполнения оператора. Назначение преемником оператора останова должно приводить к уничтожению того , на котором он появляется. Уничтожение последнего из существующих  приводит к завершению параллельного алгоритма.