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


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


Текущее значение счетчика ci фиксирует разность между числом имевших место включений и числом имевших место выключений

оператора ai.

Тогда модель Котова–Нариньяни можно записать в виде рекурсивных соотношений:

qt

= Y(M0, P||t-1);

At=At-1\+At-1È-At-1;

*At=F1(0At, qt);

+At Í *At;

рAt=рAt-1\-At-1È +At;

-At Í рAt.

В основу модели Карпа – Миллера легло представление программы как множества элементарных операторов, использующих ячейки памяти и воздействующих на них, для которых указаны правила включения и выключения. Формально параллельная схема программы R = (M, A, ) определяется следующим образом.

1. М – множество ячеек памяти.

2. A={a,b,...} – конечное множество операторов; для каждого оператора из А заданы:

K(a) – количество символов выключения оператора a (целое положительное число);

Д (а) £ М – множество входных ячеек оператора а;

Т (а) £ М – множество выходных ячеек оператора а.

3.Четверка Г = (а, q0,S,t)  – управление схемы,

где    q0 – выделенное начальное состояние.

При этом каждому оператору а сопоставлены один символ включения

 и множество символов выключения {a1, ..., ak(a)};
 

где

,

t – функция переходов – частичная функция из QxS в Q, всюду определенная на QxSt.

Управление Г формирует последовательность выполнения операторов. Элементы из Si обозначают акты включения операторов, элементы из St – акты выключения. Включение оператора а допустимо лишь в таком состоянии q, что значение t

(q, a) определено. После включения оператора завершение его работы допустимо в произвольном состоянии, поскольку функция t всюду определена на QxSt. При включении оператор а использует значения ячеек из Д (а), при выключении он засылает свои результаты в ячейки из Т(а) и формирует символ выключения, который соответствует одному из K(а) направлений условной передачи.

Полезным для эффективного распознавания свойств параллельных схем программ является класс счетчиковых схем.




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



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