7. Классификация многопроцессорных систем. Системы с нетрадиционной структурой. Систолические машины.

См. вопрос 2.

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

Систолические архитектуры обладают следующими достоинствами:

• минимизируются обращения к памяти, что позволяет согласовать скорость работы памяти со скоростью обработки,

• упрощается решение проблем ввода–вывода вследствие уменьшения конфликтов при обращении к памяти,

• эффективно используются технологические возможности СБИС за счет регулярности структуры систолической матрицы.

Однако для реализации этих преимуществ необходимо найти для каждой задачи соответствующие систолические алгоритмы, которые могут быть реализованы на систолической структуре системы. Такие алгоритмы существуют сегодня для широкого круга задач, среди которых задачи числовой обработки, обработки сигналов и символов; умножение и обращение матриц и т.д. Большинство этих алгоритмов сводится к рекуррентным соотношениям того или иного вида. В зависимости от вида систолического алгоритма, т.е. числа операндов, участвующих в примитивных операциях, типа этих элементарных операций и последовательности их выполнения выбирается тип процессорного элемента и структура локальных регулярных связей между ними. К типовым конфигурациям систолических матриц относятся: линейная (рис. 1.14) - для реализации алгоритмов фильтрации при обработке сигналов, сравнения цепочек литер при обработке баз данных; прямоугольная, перемножения матриц, нахождения двухмерных ДПФ; и гексагональная, для выполнения операций обращения матриц, решения линейных систем уравнений и т.д.

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

8. Обобщенная архитектура параллельных систем.

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

Типовая параллельная вычислительная система включает в себя множество законченных компьютеров, содержащих один или несколько процессоров (Пр) с кэш-буфепами (С) и память (П), соединенных между собой через масштабируемую коммуникационную сеть. Управлять генерацией выходных сообщений или приемом входных сообщений помогает вспомогательный процессорный блок communication assist(CA) – контроллер.

С одной стороны объединение всех подходов к построению параллельных систем в рамках одной общей структуры может показаться существенным ограничением в области дизайна. С другой стороны все многообразие описанных выше подходов реализуется в communication assist(CA) – контроллере. Все дело в функциональности, которая должна быть им обеспечена, т.е. каков должен быть интерфейс между процессором, системой памяти и сетью.

Не удивительно, что различные программные модели определяют собственные, отличные от других требования к дизайну CAи определяют какие системные операции являются общими и должны быть оптимизированы. В случае разделяемой памятиCAкрепко интегрируется с системой памяти (П) для того чтобы управлять событиями в памяти, которые могут потребовать взаимодействия с другими узлами системы. CA должен также управлять приемом сообщений, доступом к памяти и устанавливать транзит по направлению к другому узлу системы. В случае MPA, коммуникация инициализируется четкой акцией системного или пользовательского уровня, т.е. не требуется «наблюдаемости» системных событий в памяти. Вместо этого необходимо наличие возможности быстрой посылки сообщения и формирования ответа на входящее сообщение. Можно потребовать, чтобы под ответом подразумевалось выполнение операции сравнения тэгов(tag)на совпадение, чтобы буфера были локализованы, чтобы передача данных комментировалась. Параллельные данные и систолические подходы делают акцент на быстрой глобальной синхронизации, которая может быть прямо поддержана сетевыми механизмами илиCA.Datafllowархитектура делает акцент на быстром, динамическом распределении вычислений, основанном на входных сообщениях. Систолические алгоритмы предоставляют возможность использовать общие алгоритмические модели в специальных задачах синхронизации параллельного взаимодействия. Даже при этих различиях, важно заметить, что все из рассмотренных подходов имеют много общего, т.е. они требуют инициировать сетевую транзакцию как результат специфичных процессорных событий, и они требуют реализации прямых операций на удаленном узле системы для выполнения необходимых программных действий.

Мы также видим, что произошло разделение между программной моделью и машинной организацией, как только среда параллельного программирования достигла своей зрелости.