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

S – Конечное множество над памятью оператора Д

S’ - подмножество S

Н – множество стартовой исходно-заданных регистров команд (в нем лежит тело команд-то, что в данный момент дешифрируется)

С- операторы, задающие синхронизацию вычислительных процессов, задающие межпроцессорное взаимодействие.

С1- операторы, задающие назначающие операторы приемники.

С2- Создающие новые регистры команд или уничтожающие существующие регистры команд.

Параллельным алгоритмом над памятью Д называется кортеж или четверка в виде <S, S’, Н, С>

В каждый момент времени выполняется один оператор, тело которого находится в регистре команд.

Сущность регистра команд – алгоритма – аналогично сущности регистра команд-процессора.

НО! В регистре команд процессора лежит тело команды, а в регистре команд алгоритма лежит имя оператора (имя команды).

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

В регистре команд лежит тело. Аппаратная реализация

В регистре команд алгоритма лежит имя. Переменная, в которую положено имя.

1. В каждом регистре команд появляется имя правопреемника. После появления правопреемника его имя заменяется на имя приемника.

2. Открывается список приемников «для подачи заявок»

3. При отсутствии заявок со стороны, выполняющихся на других регистрах команд, приемника определяется оператором, выполнившем на данном этапе команд.

Ветвь параллельного алгоритма – последовательность имен операторов, появляющихся на одном регистре команд.

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

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

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

Оператор С – оператор для межпроцессорного взаимодействия.:

· Задают синхронизацию и

· ими назначаются операторы приемники и, если надо, то и создание новых регистров команд.

С(I) – оператор индивидуальных взаимодействий

C(G)- оператор групповых взаимодествий

Под результатом параллельного алгоритма понимается состояние памяти D^f ., после выполнения всех ветвей параллельного алгоритма.

Под реализацией понимается:

1. Совокупность порождённых им ветвей

2. Последовательность операторов, имеющих место в каждых ветвях

3. Результат выполнения оператора

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

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

Задача беступиковости и однозначности решается при помощи специальных операторов

Тема: Операторы задания взаимодействий

Операторы индивидуальных взаимодействий:

· Позволяют задавать индивидуальный доступ ветвей к памяти (V_j -> D_i)

· Изменять последовательность других операторов

· Задают последовательность не более двух ветвей

1. Изменить (Х, В) - данный оператор прибавляет значение целочисленного вектора В к соответствующим компонентам вектора Х.

2. Прочитать (a, j. a₁, B, X) – данная команда перевисывает (вводит) значения переменной а принадлежащая памяти D_i на место переменной a_1, которая принадлежит D_j. Компонены вектора в указывают на те компоненты Х, которые надо использовать.

3. Записать (a, j. a₁, B, X) – переписывает (выводи) значение переменной а принадлежащая памяти D_j, на место принадлежащей D_i.

4. Выполнить - назначает оператор S_h приемником ветви i и также предварительно задает новый регистр команд, если этот оператор первый в ветви i. (Приказ поступает в ветвь с указаним)

_________________________

1. ТО (b, A, L_j)- Трансляционные ветвь. Оператор задает доступ всех ветвей значений переменной а. l - имя ветви, которая читает переменную а без использования оператора С и транслирует значения а для всех остальных ветвей. L_j – переменная, в которую копируется значение а и в которую ветвь j имеет доступ к оператору С.

2. КО - Оператор конвейерного обмена.

КО(T, L_j, M_j)ю такой оператор задает сдвиг L_j на место переменной M_j +1 принадлежащей памяти D_j +1.

D_j – направление ветвей памяти.

3. Обобщенный условный переход В – логическая функция, которая имеет аргументы. В зависимости от того, какой аргумент принимает какое либо значение, может выполняться либо опертор приемник- S(F _j).

Обобщенный условный переход. Условный переход задается во всех ветвях параллельного алгоритма. Для выполнения обобщенного безусловного перехода существует специальный оператор.

4. Обобщенный безусловный переход. Задает переход на операторы, указанные в списке лиц. Для обобщения безусловного перехода необходимо и достаточно появления ОУП лишь в одной ветви.