Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS

Словарь-справочник по информатике (онтология информатики)

Вычислительные системы с систолической структурой

Синонимы: вычислительные системы с систолической структурой; систолические вычислительные системы;

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

В фон-неймановских машинах данные, считанные из памяти, однократно обрабатываются в процессорном элементе (ПЭ), после чего снова возвращаются в память. Авторы идеи систолической матрицы Кунг и Лейзерсон предложили организовать вычисления так, чтобы данные на своем пути от считывания из памяти до возвращения обратно пропускались через как можно большее число ПЭ.
Если проводить аналогию между структурами ВС и живого организма, то памяти можно отвести роль сердца, множеству ПЭ - роль тканей, а поток данных следует рассматривать как циркулирующую кровь. Отсюда и происходит название систолическая матрица (систола - сокращение предсердий и желудочков сердца при котором кровь нагнетается в артерии). Систолические структуры эффективны при выполнении матричных вычислений, обработке сигналов, сортировке данных и т.д.
В качестве примера авторами идеи был предложен линейный массив для алгоритма матричного умножения. В основе схемы лежит ритмическое прохождение двух потоков данных навстречу друг другу. Последовательные элементы каждого потока разделены одним тактовым периодом, чтобы любой из них мог пересечься с любым элементом встречного потока. Вычисления выполняются параллельно в процессорных элементах, каждый из которых реализует один шаг в операции вычисления скалярного произведения (IPS, Inner Product Step) и носит название IPS-элемента.

Таким образом, систолическая структура - это однородная вычислительная среда из процессорных элементов, совмещающая в себе свойства конвейерной и матричной обработки и обладающая следующими особенностями:

В настоящее время достигнута производительность систолических процессоров порядка 1000 млрд операций/с.

Классификация систолических структур

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

По степени гибкости среди систолических структур выделяют:Специализированные структуры ориентированы на выполнение определенного алгоритма. Эта ориентация отражается не только в конкретной геометрии систолической структуры, статичности связей между ПЭ и числе ПЭ, но и в выборе типа операции, выполняемой всеми ПЭ. Примерами являются структуры, ориентированные на рекурсивную фильтрацию, быстрое преобразование Фурье для заданного количества точек, конкретные матричные преобразования.
Алгоритмически ориентированные структуры, как явствует из их названия, ориентированы не на один конкретный алгоритм, а на определенный класс алгоритмов. Речь идет, главным образом, об алгоритмах, предполагающих выполнение однотипных операций над векторами, матрицами и другими числовыми множествами. В одних структурах настройка на нужный алгоритм производится путем частичного перепрограммирования процессорных элементов, в других - путем изменения конфигурации связей в систолической матрице, осуществляемого программными средствами.
В программируемых систолических структурах имеется возможность программирования как процессорных элементов, так и конфигурации связей между ними. При этом ПЭ могут обладать локальной памятью программ, и хотя все они имеют одну и ту же организацию, в один и тот же момент времени допускается выполнение различных операций из некоторого набора. Команды или управляющие слова, хранящиеся в памяти программ таких ПЭ, могут изменять и направление передачи операндов.

По разрядности процессорных элементов различают систолические структуры:В одноразрядных матрицах ПЭ в каждый момент времени выполняет операцию над одним двоичным разрядом; а в многоразрядных - над словами фиксированной длины.

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

Топология систолических структур

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

ULA (Unidirectional Linear Array) - это однонаправленный линейный процессорный массив, где потоки данных перемещаются в одном направлении. ПЭ в массиве могут быть связаны одним, двумя или тремя трактами.
При реализации алгоритма векторного произведения матриц один из потоков данных перемещается вправо, в то время как второй резидентно расположен в массиве. Используемый ПЭ представляет собой модифицированный IPS-элемент, поскольку имеется только один тракт данных, а элементы второго потока хранятся в ПЭ массива.

BLA (Bidirectional Linear Array) - это двунаправленный линейный процессорный массив, в котором два потока данных движутся навстречу друг другу. Массив типа BLA, где один из потоков является выходным, называется регулярным. В версии ULA процессоры используются более эффективно, поскольку в них элементы потока следуют в каждом такте, а не через такт, как в BLA.

TLA (Three-path communication Linear Array) - линейный процессорный массив с тремя коммуникационными трактами, в котором по разным направлениям перемещаются три потока данных. Фильтр ARMA, предложенный Кунгом построен по схеме TLA. Возможны несколько вариантов такого фильтра, в зависимости от числа выходных потоков данных и от значений, хранящихся в памяти. Процессорные элементы выполняют две операции IPS и обычно называются сдвоенными IPS-элементами. ПЭ могут использовать как хранимые в памяти значения, так и внешние данные.
TLA часто называют сдвоенным конвейером, поскольку он может быть разделен на два линейных конвейера типа BLA. Соответственно, TLA можно получить объединением двух BLA с одним общим потоком данных.

Ключевые термины, связанные с термином "вычислительные системы с систолической структурой":

  1. Вычислительные системы волнового фронта

Ключевые термины:  архитектура вычислительной машины;   классификация флинна;   simd-архитектура;   матричные вычислительные системы;


Контекстный поиск: Задайте образец для поиска:
    

|А.М.Федотов| |Преподавание| |Современные проблемы информатики| |Информатика| |Ключевые термины| |Персоны|

Федотова Ольга Анатольевна
[SBRAS]
НГУ
ФИТ НГУ
ИВТ СО РАН
© 2007-2024, Новосибирский государственный университет, Новосибирск
© 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2024, Федотов А.М.
    Дата последней модификации: 30.10.2013