Введение в архитектуру компьютеров


Некоторые модели параллельных программ - часть 3


Счетчиковой схемой называется схема R=(M, A, Г ), для которой управление Г задается следующим образом.

Пусть k – целое неотрицательное число;

S – конечное множество;

S – множество с выделенным элементом S0;

pÎNk, где Nk  – множество неотрицательных целых чисел;

v – функция из S в Nk, такая, что если sÎSt, то v(s)³0;

q: SxS®S – частичная функция, всюду определенная на SxSt.

Полагая, что значение t((S,x),s) определено, если определено q(S,s) и выполнено x+v(s)³0. Если значение определено, то полагается

t((S,x),s)=(q(S,s), x+v(s)).

Более простыми и наглядными являются параллельные операторные схемы – частный случай счетчиковых схем.

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

1) S = {S0};

2) для каждого sÎS значение q(S0,s) определено;

3) если s – символ выключения, то каждая компонента вектора v(s) равна 0 или 1;

4) если s – символ включения, то каждая компонента вектора v(s) равна 0 или -1;

5) для любых двух неравных символов включения s, s¢ из

v(s)i= -1 следует v(s¢)i=0.

Параллельную операторную схему можно представить в виде ориентированного графа с операторными вершинами Оа, Оb, Оc,... и вершинами-счетчиками d1, d2, ..., dk. Каждый счетчик di помечается числом pi, которое является начальным значением этого счетчика. Дуги графа направлены либо от операторных вершин к счетчикам, либо от счетчиков к операторным вершинам. Дуги сопоставлены ненулевым компонентам векторов v(s).

Если (v(aj))i=1, то выключение оператора а с символом выключения aj увеличивает значение счетчика i на 1. Если (v(

))i= –1, то включение оператора а уменьшает значение счетчика i на 1. Условие 5 из определения параллельной операторной схемы означает, что из произвольного счетчика выходит не более чем одна дуга.

Пример. Пусть необходимо перемножить матрицу

 на вектор
,

а результат поместить в (с1, с2).

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



- Начало -  - Назад -  - Вперед -



Книжный магазин