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

При появлении нескольких с-операторов в списке преемников какого-либо  окончательное решение о назначении “первого” преемника для регистра осуществляет оператор из , входящий в с-оператор, имя которого представлено в данный момент в рассматриваемом . Общее правило при этом – назначать “первым” преемником наиболее приоритетный из списка с-оператор, у которого выполнено условие “индивидуального” включения для соответствующего  ; если же такового нет, то назначение откладывается, пока он не появится. Зачастую приоритет отдается первому из поступивших в список с-операторов (даже если условие его “индивидуального” включения еще не выполнено), а остальные аннулируются. Другими словами, список преемников отдельного  может состоять только из одного элемента, попытка записи второго элемента трактуется как пустая операция. Таким образом, при выполнении параллельного алгоритма общее число преемников в некоторый момент времени не превышает числа , существующих в этот момент.

После выполнения с-оператора его имя в соответствующем  заменяется на имя преемника. Считается, что с этого момента начинает выполняться новый оператор, а список преемников открыт для приема “заявок”. При отсутствии заявок со стороны, то есть от с-операторов, выполняющихся на других   , преемник определяется с-оператором, выполняющимся на данном . Последовательность с-операторов, появляющихся на одном ,  определяет ветвь параллельного алгоритма.

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

Использование параллельных алгоритмов поднимает два принципиальных вопроса: о беступиковости и однозначности задаваемых ими вычислений.

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

Результатом параллельного алгоритма является конечное состояние памяти  после выполнения всех ветвей, а реализацией (историей) параллельного алгоритма – совокупность порожденных им ветвей, последовательность операторов, имевшую место в каждой ветви, а также результаты выполнения операторов.

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

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

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