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


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


Развитие точных методов в программировании привело к возникновению различных формальных моделей программ, в том числе и моделей параллельных программ.

Рассмотрим модели параллельных программ, прототипом которых явились операторные схемы программ, в частности схемы Янова.

В.Е.Котовым и А.С.Нариньяни была предложена формальная модель параллельных вычислений, названная асинхронной моделью.

Асинхронная программа над памятью M (A-программа) представляет собой множество X блоков и массивов блоков. Блок x образован парой (y, 0), где y – предикат над MCÌM, MC  – управляющая память, O – оператор над памятью M. С O-оператором связаны входные и выходные наборы переменных из М. По входному набору О-оператор вычисляет значение переменных выходного набора. Предикат y – спусковая функция блока x.

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

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

Пусть A – множество операторов над памятью M.

Для каждого момента t множество операторов вычислительного процесса можно разбить на 4 непересекающихся множества:

+At  – включающиеся в t;

-At – выключающиеся в t;

pAt – находящиеся во включенном состоянии;

0At – находящиеся в выключенном состоянии.

Q = {q} – множество состояний метасистемы, q0 – начальное состояние.

F – функция, однозначно сопоставляющая каждому множеству

 одно из его подмножеств в соответствии с состоянием q.

y – функция, ставящая в соответствие каждому набору

 некоторое состояние q (
 – предыстория процесса Р до момента t

включительно).

Каждому оператору aiÎA сопоставляется счетчик ci с начальным значением Æ.


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



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