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

Основа МПД – активная память, пакеты в ней. МПД включает в себя: 3 вида сетей, операционные блоки, блоки принятия решений.

Управляющая сеть предназначена для выбора ячеек команд, которые отсылают управляющие пакеты. Распределительная сеть распределяет пакеты по соответствующим ячейкам. Селекторная сеть предназначена для тнсылки готовых пакетов на операционные блоки иблоки принятия решений.

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

В селекторной сети адрес назначения определяется кодом поля операции (полем КОП).

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

Для передачи пакетов по сетям существует два основных типа элементов:

1. Селектор – много входов, один выход.

2. Переключатель – с одного входа, на много выходов.

Кроме них существует два дополнительных элемента:

3. Буфер.

4. Преобразователи кодов информации.

1-й уровень параллелизма в МПД – асинхронная и параллельная передача пакетов по сетям. 2-ой: одновременное выполнение пакетов на многих процессорах  высокая скорость передачи информации. Естественный параллелелизм.

Достоинства МПД.

1. Высокая степень однородности арифметических и логических блоков и блоков принятия решений, что удешевляет процесс обработки информации.

2. Наличие большого числа операционных блоков и блоков принятия решений, которое можно непрерывно наращивать.

3. При организации сетей передачи информации (3 шт.) так же используются простые однородные элементы, состоящие из селекторов, переключателей, буферов и преобразователей кодов, следовательно, не требуется разработки специальных СБИС, следовательно, низкая стоимость машины. Высокая производительность системы обеспечивается двумя уровнями параллелизма: на уровне процессоров и тракта передачи информации.

Недостатки МПД.

1. Возможное переполнение трактов сетей передачи информации.

2. Возможность появления тупиковых ситуаций.

Тупиковая ситуация возникает в том случае, когда несколько объектов обращаются к одному ресурсу и требуется завершение операции над одним объектом, чтобы смог работать второй. Радикальный способ избегать тупиковых ситуаций - посылка сигнала подтверждения, т.е. сигнала обратной связи. Для этого к функциональному блоку добавляют еще один вход – сигнальный.

30. Принцип вычислений на основе графовой редукции. «Энергичные» и «ленивые» вычисления.

(Редукционные машины) Построены на принципе реализации F-машин. Функциональные языки основаны на представлении вычислительного процесса в виде вычисления некоторой функции над операндами. Развертывание вычислительного процесса во времени удобно представлять в виде графической структуры, которую легко хранить в памяти.

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

Операции с графом часто связаны с его редуцированием, т.е. со сворачиванием графа и приведением его к одной вершине. Вводят инфиксную, префиксную и постфиксную запись. Префиксная наиболее удобна. Операция применения функции к аргументу называется операцией аппликации @.

В

@

функциональном программировании вводится понятие абстрактной -функции - -х.f

х – аргумент; f – тело функции;

Процесс вычисления графа, т.е. подстановка вместо переменных определенных значений, т.е. приведение его к аппликативной форме, называется его редуцированием. Левоориентированный обход. Машины, которые вычисляют графы – редукционные машины. Редуцирование – получение нормальной формы графа.

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

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

Для повышения эффективности редукционных машин используется принцип параллельной редукции или сверхмультиобработки. Параллельной редукции заключается в параллельном вычисление отдельных ветвей графа. Организация параллельной редукции повышает быстродействие таких машин. В этом случае реализуется принцип естественного параллелизма.

Использование комбинаторов в редукционном вычислении

Комбинаторы введены для упрощения процесса вычисления. Это некоторые конструкции. Они были предложены Д. Тернером.

1. S-комбинатор: f g x  f x (g x)

2. K-комбинатор: x y  x

3. I-комбинатор: x x