Матричные вычислительные системы реферат
Обновлено: 05.07.2024
Основой матричных систем является матричный процессор.
Элементарный процессор (ЭП) включает в себя арифметико-логическое устройство (АЛУ) и память. Сеть связи между ЭП позволяет осуществлять обмен информацией между любыми ЭП. Поток команд поступает на матрицу ЭП от единого устройства управления. Структура связей между процессорами может иметь самую разную топологию: двумерная решетка, тор, n-мерная решетка и т.п.
Существует широкий спектр научных, технических и административно- хозяйственных задач, которые эффективно решаются на матричном процессоре. При решении задач фактически один и тот же алгоритм параллельно (одновременно) реализуется для многих массивов данных. Каждый из массивов данных размещается и обрабатывается в своем элементарном процессоре. Предварительно данные организуются в векторы. Параллелизм в работе ЭП принципиально позволяет достичь любого уровня быстродействия матричного процессора.
Примеры матричных систем.
Система ILLIAC-IV создана Иллинойским университетом и фирмой Burroughs. Работы по созданию системы начались в 1966 г., монтаж системы закончен в мае 1972 г. Быстродействие системы 10 9 оп/сек, полезное время 80-85% общего времени работы ILLIAC-IV, стоимость 30-40 млн долларов, вес 57 т, площадь 930 м 2 .
Структура ILLIAC-IV показана на рисунке 12.40.
Система ILLIAC-IV состоит из четырех квадрантов, подсистемы ввода/вывода, ЭВМ В-6700, дисковой памяти (ДП) и архивной памяти (АП).
Квадрант – матричный процессор, включающий устройство управления и 64 элементарных процессоров. Устройство управления представляет собой специализированную ЭВМ, которая используется для выполнения операций над скалярными и формирует поток команд на матрицу ОП. Элементарные процессоры матрицы регулярным образом связаны друг с другом. Матрица из 64 ЭП предназначается для выполнения операций над векторами. Все 64 ЭП работают синхронно и единообразно.
Допустимо одновременное выполнение скалярных и векторных операций. В системе ILLIAC-IV заложена возможность параллельной работы не только ЭП в матрице, но и устройства управления и матрицы в целом.
В системе ILLIAC-IV используется слово длиной 64 бит. Форматы могут быть 64 или 32 разряда с плавающей запятой и 48 или 24 или 8 разрядов с фиксированной запятой. Матрица из 64 ЭП способна обрабатывать векторы операндов, состоящие из 64, 128, и 512 компонент.
Элементарный процессор может находиться в одном из двух состояний – активном или пассивном. В первом состоянии ему разрешается, а во втором запрещается выполнять команды устройства управления. Состояние ЭП задается при помощи специальных команд, среди них, например, есть команда, установления в пассивное состояние всех ЭП, у которых передаваемая информация больше содержимого накапливающего сумматора. Сумматор и все регистры ЭП программно адресуемы. К памяти каждого ЭП непосредственный доступ имеет только собственный ЭП. Обмен информацией между памятями различных ЭП осуществляется по сети связи при помощи специальных команд пересылок.
Подсистема ввода/вывода состоит из устройства управления, буферного ЗУ и коммутатора. Комплекс этих устройств обеспечивает обмен информацией между квадрантами ILLIAC-IV и средствами ввода/вывода: ЭВМ В-6700, дисковой и архивной памятью, периферийными устройствами, сетью ARPA.
Управляющая ЭВМ В-6700 используется для реализации функций операционной системы (включая ввод/вывод, операции по компиляции и компоновки программ, распределение аппаратных ресурсов, использование служебных программ и т.п.). По сути ЭВМ В-6700 является быстродействующим периферийным устройством ILLIAC-IV.
Система ILLIAC-IV входила в состав вычислительной сети ARPA. Система ILLIAC-IV – средство решения сложных задач, таких как, матричная арифметика, системы линейных алгебраических уравнений, линейное программирование, исчисление конечных разностей, квадратуры (включая БП Фурье), обработка сигналов, задачи на собственные значения, нелинейные уравнения, отыскание корней полиномов и т.п.
Сферой применения ILLIAC-IV являются: наука, экономика, анатомия, энергетика, проектирование, предсказание погоды, радиолокация, оборона, космические исследования и т.д.
Ассоциативные процессоры (АП) предназначены для групповой (параллельной) обработки массивов информации. На макроуровне структура АП и матричные процессоры подобны (см. рис. 52): единое устройство управления и множество связанных ЭП. Однако, на микроуровне наблюдается существенное различие в реализации ЭП и связей между ними. АП в общем случае обеспечивает параллельную обработку слов и разрядов слова.
Множество связанных ЭП представляет собой ассоциативное запоминающее устройство (АЗУ). Множество ЭП способно хранить массивы информации, позволяет выбирать информацию по содержанию (по ассоциативному признаку), допускает одновременное выполнение над словами массива операций: логических, арифметических и поисковых (сортировки, отыскание числа по неравенству и т.д.)
Каждый ЭП представляет собой часть АЗУ, которая используется для хранения и обработки слов большой длины. Для каждого разряда слов предназначен свой физический элемент. Элемент АЗУ содержит логические схемы, обеспечивающие запись внешней информации, считывание данных без разрушения и сравнения содержимого с входной информацией.
Ассоциативный способ обработки данных позволяет преодолеть многие ограничения, присущие адресному доступу к памяти, за счет задания некоторого критерия отбора и проведения необходимых преобразований, только над теми данными, которые удовлетворяют этому критерию. Критерием отбора может быть совпадение с любым элементом данных, достаточным для выделения искомых данных из всех имеющихся. Поиск данных может происходить по фрагменту, имеющему большую или меньшую корреляцию с заданным элементом данных.
Исследованы и в разной степени применяются несколько подходов, различающихся полнотой реализации модели ассоциативной обработки. Если реализуется только ассоциативная выборка данных с последующим поочередным использованием найденных данных, то говорят об ассоциативной памяти или памяти, адресуемой по содержимому. При достаточно полной реализации всех свойств ассоциативной обработки используется термин "ассоциативный процессор".
Ассоциативные системы относятся к классу: один поток команд – множество потоков данных (SIMD = Single Instruction Multiple Data). Эти системы включают большое число операционных устройств, способных одновременно по командам управляющего устройства вести обработку нескольких потоков данных. В ассоциативных вычислительных системах информация на обработку поступает от ассоциативных запоминающих устройств (АЗУ), характеризующихся тем, что информация в них выбирается не по определенному адресу, а по ее содержанию.
Ассоциативная система Staran.
Ассоциативная ВС Staran (рисунок 12.41) являлась частью многомашинной ВС, управляющей воздушным движением в аэропорту. Модифицированный вариант Staran IV имел быстродействие 5-10оп/с и стоил 15 млн. долларов. Основу системы Staran составляет ассоциативный процессор. Под ассоциативным процессором понимается ассоциативная память с возможным выполнением логических и арифметических операций при ассоциативном поиске.
Ассоциативная память включает 32 блока, рассматриваемых как 32 элементарных ассоциативных процессора (ЭП). Любой ЭП способен выполнить набор логических, арифметически и поисковых операций. Суммарное быстродействие 32-х ЭП, или быстродействие АП в целом составляет 5*10оп/с.
Ассоциативная память системы Staranсостоит из матриц, любая из которых обладает возможностью одновременной (параллельной) выборки 256 бит (в направлении слов или направлении разрядов).
В ВС Staranимеется управляющее ЗУ, которое работает с ассоциативной памятью в режиме перекрытия. Управляющее ЗУ служит для хранения данных и микрокоманд и включает быстродействующее, буферное и вспомогательное запоминающие устройства.
Структура АП такова, что она обеспечивает ассоциативный поиск в пределах всей ассоциативной памяти и доступ к любым ЭП. Связь оборудования пользователя с АП осуществляется через интерфейс. Для связи используется канал прямого доступа к памяти (1), буферный канал ввода/вывода (2) внешний функциональный канал (3), канал параллельного ввода/вывода информации(4). Каналы имеют широкую полосу пропускания (свыше 3000 мегабит/с).
Функционирование системы Staran и ILLIAC-IV во многом аналогично. Однако, параллелизм Staran достигается на более низкомлогическом уровне: допустима одновременная обработка 256×32 операндов на 32 элементарных ассоциативных процессорах.
Система Staran ориентирована для работы в системах управления воздушным движением (включая обработку р/л сигналов, распознавание образов, предсказание погоды и управление данными). Она может функционировать как автономная проблемно- ориентированная ВС или работать в составе универсальной системы.
Ассоциативно-матричная система PEPE.
Максимальная производительность системы PEPE 3×10 оп/с. Это ансамбль параллельных ЭП. Система PEPE разработана фирмами Bell Telephone и System Development. Разработанный 36-ти процессорный экспериментальный вариант PEPE использовался в системе ПРО. Конечный вариант PEPE-288 ЭП работает под управлением ЭВМ СDС-7600.
Структуры PEPE и ILLIAC-IV при достаточной близости имеют свои особенности. Например, система PEPE способна обработать два независимых потока команд, но любой ЭП (в отличии от ILLIAC-IV) не имеет непосредственно связи с ближайшими соседними ЭП. Это сужает класс решаемых задач. На системе PEPE эффективно решаются такие сложные задачи, в которых нет непосредственно обмена информации между ЭП ансамбля. Например, задача слежения за многими объектами в большом аэропорту. Для этой задачи характерно большое количество данных для траектории любого объекта и один и тот же алгоритм обработки информации для любой из траекторий.
Ассоциативная ВС является значительным этапом по развитию архитектуры и достижения высокой эффективности средств вычислительной техники. Магистральные, матричные и ассоциативные ВС проблемно ориентированы.
ПС-2000(параллельные системы 2000).
Отечественная система ПС-2000 (рисунок 12.42) создана в начале 80-х годов. Ее можно отнести к матричным системам. Она ориентирована на решение задач, характеризующихся параллелизмом данных, независимостью ветвей и объектов.
Центральная часть системы – мультипроцессор ПС-200 , состоящий из решающего поля и устройство управления. Решающее поле строится из 1,2,4 или 8 устройств обработки (УО), в каждом из которых из 8 процессорных элементов. Таким образом, мультипроцессор может содержать 8,16,32 или 64 процессорных элементов. Ёмкость оперативной памяти (ОП) процессорного элемента - 4096 или 16384 слова. Быстродействие ПС-2000 примерно 30-60 млн. флоп/с. Устройство управления содержит микропрограммное управление, ОП и АЛУ. В блок микропрограммного управления загружаются микропрограммы обработки данных, ввода вывода и управления. В комплект программного обеспечения входит набор микропрограмм базовой системы операций, ориентированный на обработку матриц, реализацию быстрого преобразования Фурье (БПФ), решение задач математической статистики, спектрального анализа, линейного и динамического программирования. Возможна реализация на микропрограммном уровне любой необходимой системы операций. В ОП загружается программа обработки. Команды программы выполняются в обычном порядке.
Ввод/вывод данных в память решающего поля, то есть в ОП процессорных элементов, производится через канал прямого доступа, состоящий из магистралей ввода и вывода. Операции ввода/вывода инициализируются мониторной подсистемой, и выполняется под управлением устройства управлением мультипроцессора. Обработка ввода и вывода может выполняться одновременно. Процессорные элементы решающего поля связаны регулярным каналом, по которому передаются данные. Конфигурация регулярного канала перестраивается под управлением программы, образуя одно кольцо из 64 процессорных элементов или несколько одинаковых полей: 8 колец по 8 процессорных элементов, 4 по 16 или 2 по 32.
В целом, система управления мониторной подсистемой реализуется из одной или двух мини-ЭВМ СМ-2 и подключенных к ним периферийных устройств. На ЭВМ реализуется подготовка микропрограмм и программ для мультипроцессора с использованием языков программирования и соответствующих трансляторов. Мониторная подсистема управляет загрузкой микропрограмм в мультипроцессор, контролирует работу мультипроцессоров и обеспечивает обмен между системой и пользователями.
Матричные ВС – одна из основных тенденций построения сверхмощных средств вычислительной техники. Эти системы позволяют, в отличие от магистральных систем, в принципе осуществить неограниченное количество вычислительных процессов и, следовательно, достичь любого уровня быстродействия.
Выполняют последовательно поразрядные арифметические и логические операции. Каждый элемент соединяется с 4-мя другими. ПЭ – Процессор и ОЗУ. Разрядность слов устанавливается программно. От УУ – команды управления и различные константы.
Многомодальная логика – каждый ПЭ м.б. активным или пассивным.
25. Принципы векторной обработки
Векторная обработка увеличивает скорость и эффективность обработки за счет того, что обработка целого набора (вектора) данных выполняется одной командой. Скорость выполнения операций в векторном режиме приблизительно в 10 раз выше скорости скалярной обработки. Для фрагмента типа
в скалярном режиме потребуется сгенерировать целую последовательность команд: прочитать элемент B(I), прочитать элемент C(I), выполнить сложение, записать результат в A(I), увеличить параметр цикла, проверить условие цикла. В векторном режиме этот фрагмент преобразуется в: загрузить порцию массива B, загрузить порцию массива C (эти две операции будут выполняться со сдвигом в один такт, т.е. практически одновременно), векторное сложение, запись порции массива в память, если размер массивов больше длины векторных регистров, то повторить эту последовательность некоторое число раз.
Перед тем, как векторная операция начнет выдавать результаты, проходит некоторое время (startup), связанное с заполнением конвейера и подкачкой аргументов. Чем больше длина векторов, тем менее заметным оказывается влияние данного начального промежутка времени на все время выполнения программы.
Векторные операции, использующие различные ФУ и регистры, могут выполняться параллельно.
26. Факторы, снижающие производительность векторных ЭВМ. Возможность векторной обработки программ
Некоторый фрагмент программы может быть обработан в векторном режиме, если для его выполнения могут быть использованы векторные команды (соответственно полная или частичная векторизация). Поиск таких фрагментов в программе и их замена на векторные команды называется векторизацией программы. Для векторизации необходимы вектора-аргументы + независимые операции над ними. Кандидаты для векторизации - это самые внутренние циклы программы.
Пример. Нужно выполнить независимую обработку всех элементов поддиагональной части массива; в этом случае можем векторизовать по строкам, можем по столбцам, но не можем обработать все данные сразу в векторном режиме из-за нерегулярности расположения элементов поддиагональной части массива в памяти. Пример векторизуемого фрагмента, для которого выполнены все указанные условия:
Пример невекторизуемого фрагмента (очередная итерация не может начаться, пока не закончится предыдущая):
Препятствия для векторизации
Препятствий для векторизации конкретного цикла может быть много, вот лишь некоторые из них:
Зависимость по данным (предыдущий фрагмент).
Отсутствие регулярно расположенных векторов:
Присутствие цикла, вложенного в данный - для реализации такого фрагмента нет соответствующих векторных команд.
Вызов неизвестных подпрограмм и функций:
29. Использование параллельных вычислительных систем. Закон Амдала
Предположим, что в вашей программе доля операций, которые нужно выполнять последовательно, равна f, где 0
Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0).
Посмотрим на проблему с другой стороны: а какую же часть кода надо ускорить (а значит и предварительно исследовать), чтобы получить заданное ускорение? Ответ можно найти в следствии из закона Амдала: для того чтобы ускорить выполнение программы в q раз необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем на 99.99% кода, что почти всегда составляет значительную часть программы!
Раздел: Информатика, программирование
Количество знаков с пробелами: 52124
Количество таблиц: 1
Количество изображений: 13
Рассмотрим каждую ВС в отдельности и выявим их сходства.
Матричные Вычислительные Системы (ВС)
Наиболее распространенными из систем, класса: один поток команд - множество - потоков данных (SIMD), являются матричные системы, которые лучше всего приспособлены для решения задач, характеризующихся параллелизмом независимых объектов или данных. Организация систем подобного типа на первый взгляд достаточно проста. Они имеют общее управляющее устройство, генерирующее поток команд и большое число процессорных элементов, работающих параллельно и обрабатывающих каждая свой поток данных. Таким образом, производительность системы оказывается равной сумме производительностей всех процессорных элементов. Однако на практике, чтобы обеспечить достаточную эффективность системы при решении широкого круга задач необходимо организовать связи между процессорными элементами с тем, чтобы наиболее полно загрузить их работой. Именно характер связей между процессорными элементами и определяет разные свойства системы.
Рассмотрим структуру матричной вычислительной системы.
Структура матричной вычислительной системы представлена на рис. 3.
Рис. 3. Обобщенная модель матричной SIMD-системы
Параллельная обработка множественных элементов данных осуществляется массивом процессоров (МПр). Единый поток команд, управляющий обработкой данных в массиве процессоров, генерируется контроллером массива процессоров (КМП). КМП выполняет последовательный программный код, реализует операции условного и безусловного переходов, транслирует в МПр команды, данные и сигналы управления. Команды обрабатываются процессорами в ре жиме жесткой синхронизации.
Сигналы управления используются для синхронизации команд и пересылок, а также для управления процессом вычислений (например - определяют, какие процессоры массива должны выполнять операцию, а какие – нет). Команды, данные и сигналы управления передаются из КМП в массив процессоров по шине широковещательной рассылки. Поскольку выполнение операций условного перехода зависит от результатов вычислений, результаты обработки данных в массиве процессоров транслируются в КМП, проходя по шине результата.
Для обеспечения пользователя удобным интерфейсом при создании и отладке программ в состав подобных ВС обычно включают интерфейсную ВМ (front-end computer). В роли такой ВМ выступает универсальная вычислительная машина, на которую дополнительно возлагается задача загрузки программ и данных в КМП. Кроме того, загрузка программ и данных в КМП может производиться и напрямую с устройств ввода-вывода (например, с магнитных дисков). После загрузки КМП приступает к выполнению программы, транслируя в МПр по широковещательной шине соответствующие SIMD-команды.
Для хранения множественных наборов данных в массиве процессоров должны присутствовать и модули памяти. Кроме того, в массиве должна быть реализована сеть взаимосвязей как между процессорами, так и между процессорами и модулями памяти. Таким образом массив процессоров – это блок, состоящий из процессоров, модулей памяти и сети соединений.
Дополнительную гибкость при работе с рассматриваемой системой обеспечивает механизм маскирования, позволяющий привлекать к участию в операциях лишь определенное подмножество из входящих в массив процессоров. Маскирование реализуется как на стадии компиляции, так и на этапе выполнения. При этом процессоры, исключенные путем установки в ноль соответствующих битов маски, во время выполнения команды простаивают.
Одним из первых матричных процессоров был SОLОМОN (60-е годы), представлена на рис. 4.
Рис 4. Структура матричной вычислительной системы "SOLOMON"
Система SОLOМОN содержит 1024 процессорных элемента, соединены в виде матрицы: 32х32. Каждый процессорный элемент матрицы включает в себя процессор, обеспечивающий выполнение последовательных поразрядных арифметических и логических операций, а также оперативное ЗУ, емкостью 16 Кбайт. Длина слова - переменная от 1 до 128 разрядов. Разрядность слов устанавливается программно. По каналам связи от устройства управления передаются команды и общие константы. В процессорном элементе используется, так называемая, многомодальная логика, которая позволяет каждому процессорному элементу выполнять или не выполнять общую операцию в зависимости от значений обрабатываемых данных. В каждый момент все активные процессорные элементы выполняют одну и ту же операцию над данными, хранящимися в собственной памяти и имеющими один и тот же адрес.
Идея многомодальности заключается в том, что в каждом процессорном элементе имеется специальный регистр на 4 состояния - регистр моды. Мода (модальность) заносится в этот регистр от устройства управления. При выполнении последовательности команд модальность передается в коде операции и сравнивается с содержимым регистра моды. Если есть совпадения, то операция выполняется. В других случаях процессорный элемент не выполняет операцию, но может, в зависимости от кода, пересылать свои операнды соседнему процессорному элементу. Такой механизм позволяет выделить строку или столбец процессорных элементов, что очень полезно при операциях над матрицами. Взаимодействуют процессорные элементы с периферийным оборудованием через внешний процессор.
Дальнейшим развитием матричных процессоров стала система ILLIАS-4, разработанная фирмой BARRОYS. Первоначально система должна была включать в себя 256 процессорных элементов, разбитых на группы, каждый из которых должен управляться специальным процессором. Однако по различным причинам была создана система, содержащая одну группу процессорных элементов и управляющий процессор. Если в начале предполагалось достичь быстродействия = 1 млрд. операций в секунду, то реальная система работала с быстродействием = 200 млн. операций в секунду. Эта система в течение ряда лет считалась одной из самых высокопроизводительных в мире.
В начале 80-х годов в СССР была создана система: ПС-2000, которая также является матричной. Основой этой системы является мультипроцессор - ПС-2000, состоящий из решающего поля и устройства управления мультипроцессором. Решающее поле строится из одного, двух, четырех или восьми устройств обработки, в каждом из которых - 8 процессорных элементов. Мультипроцессор из 64 процессорных элементов обеспечивает быстродействие = 200 млн. операций в секунду на коротких операциях.
Ассоциативные Вычислительные Системы (ВС)
Эти системы характеризуются большим количеством операционных устройств способных одновременно по командам управляющего устройства вести обработку нескольких потоков данных. Однако эти системы значительно различны от матричных способом формирования потоков данных. В ассоциативных системах информация на обработку поступает от ассоциативного запоминающих устройств (АЗУ), характеризующихся тем, что информация выбирается не по определённому адресу, а по содержанию.
Ассоциативный процессор (АП) – это ассоциативная память, допускающая параллельную запись во все ячейки, для которых было зафиксировано совпадение с ассоциативным признаком. Эта особенность АП, носящая название мультизаписи, является первым отличием ассоциативного процессора от традиционной ассоциативной памяти. Считывание и запись информации могут производиться по двум срезам запоминающего массива — либо это все разряды одного слова, либо один и тот же разряд всех слов. При необходимости выделения отдельных разрядов среза лишние позиции допустимо маскировать. Каждый разряд среза в АП снабжен собственным процессорным элементом, что позволяет между считыванием информации и ее записью производить необходимую обработку, то есть параллельно выполнять операции арифметического сложения, поиска, а также эмулировать многие черты матричных ВС.
Ассоциативные ВС – это ВС класса SIMD, в основе которой лежит ассоциативный процессор. Таким образом, ассоциативные ВС представляют собой n процессорных элементов ПЭ (вертикальный разрядный срез памяти), как правило, последовательной поразрядной обработки для каждой из ячеек памяти. Операция осуществляется одновременно всеми n ПЭ. Все или часть элементарных последовательных ПЭ могут синхронно выполнять операции над всеми ячейками или над выбранным множеством слов ассоциативной памяти.
Пример ассоциативной ВС – система STARAN, разработанная Goodyear Aerospace Corporation в 1972 году.
Аналогия между матричными и ассоциативными ВС заключается в их классе архитектуры ОКМД.
Архитектура ОКМД, или SIMD (от Single Instruction Multiply Data stream), — одиночный поток команд над множественным потоком данных. Бытовым аналогом работы таких систем является ситуация, в которой несколько человек одновременно, синхронно выполняют одну и ту же операцию, последовательность одинаковых операций над разными деталями. Примером также может служить ансамбль музыкальных инструментов, синхронно исполняющих мелодию под управлением дирижера.
В вычислительной системе с архитектурой ОКМД имеется единственное устройство управления, которое организует работу группы процессорных элементов. Это устройство управления создает только один поток команд, который может включать операции над векторными данными.
В связи с обсуждением этого класса параллельных систем, по-видимому, следует напомнить о включении основанных на подходе SIMD групп команд ММХ и SSE в систему команд процессоров Pentium и аналогичных групп в системы команд других процессоров.
Основной разновидностью систем класса ОКМД являются системы ОКМДС, в которых выполняется пословная обработка данных. В этот класс входят векторные и матричные вычислительные системы, которые находят применение при решении научно-технических задач, использующих векторные и матричные структуры данных.
Примеры параллельных систем с общим управлением.
- матричные с одноразрядными процессорными элементами (SOLOMON I, ICL DAP, Goodyear MPP, CLIP, Thinking Connechtion Machine) и с многоразрядными процессорными элементами (SOLOMON II, ILLAC IV, Bu rroughs BSP, ПС-2000);
Читайте также: