Вычислительные схемы асинхронного процесса.
5.1 Вычислительные схемы
Определение 5.1. Вычислительная схема - это представление в графической форме асинхронной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистров» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления.
Граф потока данных (информационный граф) определяет входные и выходные данные для каждого оператора. Дуга (Ri Sk) от регистра Ri к оператору Sk означает, что данные Riявляются элементом входных данных этого оператора; дуга (Sk Rj) определяет данные Rjкак выходные для Sk. Некоторые данные R могут являться выходными для оператора Si и входными для оператора Sj. Пример графа потока данных для некоторой вычислительной схемы представлен на рисунке 5.1 а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.
a) граф потока данных б) граф управления
Рисунок 5.1 - Пример вычислительной схемы
Граф управления определяет последовательность выполнения операторов. Каждый оператор (представлен кружком) связан с некоторым количеством управляющих счетчиков (представлены прямоугольниками). Каждый из управляющих счетчиков содержит неотрицательное целое число. Текущие значения счетчиков совместно со значениями данных на графе потока данных определяют состояние вычислительной схемы. Пример графа управления представлен на рисунке 5.1 б. Если все счетчики, указывающие на оператор S (то есть входные счетчики), имеют ненулевые значения, то говорят, что оператор S определен. В этом случае он может выполниться, изменив свои выходные регистры в соответствии с графом потока данных и изменив счетчики графа управления по следующему правилу: значения всех входных счетчиков оператора S уменьшаются на единицу, а значения выходных – увеличивается. Причем для каждого выходного счетчика оператора S приращение может быть свое, персональное, и определяется оно с помощью специальной функции от значений регистров.
Определение 5.2. Последовательность операторов S1, S2, … , Sn, ..., такая, что каждый оператор Sj определен (то есть его входные счетчики не равны нулю) при тех значениях счетчиков, которые получаются в результате выполнения предшествующих операторов, называется последовательностью исполнения схемы.
Т.к. с операторами не связано никакого особого отсчета времени, то порядок, в котором операторы будут выполняться, не всегда может быть предсказан. Любая допустимая последовательность исполнения является возможной последовательностью событий.
Определение 5.3. Вычислительная схема называется детерминированной, если она вырабатывает одинаковые результаты для всех допустимых последовательностей исполнения.
Пример 5.1. Схема на рисунке 5.1 является детерминированной.
Рассмотрим вычислительную схему на рисунке 5.2. Две последовательности операторов S1, S2 и S3, S4, как это видно из графа управления, выполняются параллельно и асинхронно. Очевидно, что значения регистров R2 и R3 будут различными в зависимости от того, выполняется ли первая последовательность операторов раньше или позже второй. Поскольку граф управления здесь допускает последовательности исполнения, которые приводят к различным результатам, то эта схема недетерминирована.
Определение 5.4. Говорят, что два оператора соперничают в регистре R, если один из них изменяет R, а другой либо изменяет R, либо обращается к нему.
Если два оператора, которые соперничают в некотором регистре, могут быть выполнены в одно и то же время, то говорят, что в схеме существует условие соперничества и такая схема является недетерминированной. Одна из возможных форм недетерминированного исполнения заключается в том, что схема может «зависнуть» (попасть в тупиковую ситуацию).
Вычислительные схемы не являются конструктивной моделью, несмотря на свою интуитивную понятность и возможность сделать вывод о возникновении тупиков в системе.
Рисунок 5.2 - Пример недетерминированной вычислительной схемы