Систолический массив

В параллельных компьютерных архитектурах систолический массив представляет собой однородную сеть тесно связанных блоков обработки данных (DPU), называемых ячейками или узлами . Каждый узел или DPU независимо вычисляет частичный результат в зависимости от данных, полученных от его вышестоящих соседей, сохраняет результат внутри себя и передает его ниже по потоку. Систолические массивы впервые были использованы в Colossus , первом компьютере, использовавшемся для взлома немецких Лоренца шифров во время Второй мировой войны . ^[1]Из-за секретного характера Колосса они были независимо изобретены или переоткрыты Х. Т. Кунгом и Чарльзом Лейзерсоном , которые описали массивы для многих вычислений плотной линейной алгебры (матричное произведение, решение систем линейных уравнений , LU-разложение и т. д.) для полосовых матриц. Ранние приложения включают вычисление наибольших общих делителей целых чисел и многочленов. ^[2] Их иногда классифицируют как архитектуры с несколькими инструкциями и одними данными (MISD) в соответствии с таксономией Флинна , но эта классификация сомнительна, поскольку можно привести веские аргументы, чтобы отличить систолические массивы от любой из четырех категорий Флинна: SISD , SIMD , MISD , MIMD , как обсуждается далее в этой статье.

Параллельные входные данные проходят через сеть проводных процессорных узлов, которые комбинируют, обрабатывают, объединяют или сортируют входные данные в производный результат. Поскольку волнообразное распространение данных по систолическому массиву напоминает пульс кровеносной системы человека, название «систолический» было придумано из медицинской терминологии. Название происходит от систолы как аналогии с регулярным перекачиванием крови сердцем.

Приложения [ править ]

Систолические массивы часто жестко привязаны к определенным операциям, таким как «умножение и накопление», для выполнения задач массового параллельного интегрирования, свертки , корреляции , умножения матриц или сортировки данных. Они также используются для алгоритмов динамического программирования ДНК и белков , используемых в анализе последовательностей .

Архитектура [ править ]

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

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

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

Цели и преимущества [ править ]

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

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

Споры о классификации [ править ]

Хотя систолические массивы официально классифицируются как MISD , их классификация несколько проблематична. Поскольку вход обычно представляет собой вектор независимых значений, систолический массив определенно не является SISD . Поскольку эти входные значения объединяются и объединяются в результат(ы) и не сохраняют свою независимость , как в SIMD блоке векторной обработки , массив не может быть классифицирован как таковой. Следовательно, массив также нельзя классифицировать как MIMD , поскольку MIMD можно рассматривать как простую совокупность меньших машин SISD и SIMD .

данных Наконец, поскольку поток преобразуется при прохождении через массив от узла к узлу, несколько узлов не работают с одними и теми же данными, что делает классификацию MISD неправильным термином . Другая причина, по которой систолический массив не должен квалифицироваться как MISD его из категории SISD: входные данные обычно представляют собой вектор, а не одно , та же, что и та, которая исключает значение данных, хотя можно утверждать, что любой заданный входной массив вектор — это один элемент данных.

Несмотря на все вышесказанное, в учебниках по параллельным вычислениям и на инженерных занятиях в качестве классического примера архитектуры MISD часто предлагаются систолические массивы. Если массив рассматривается снаружи как атомарный, его, возможно, следует классифицировать как SFMuDMeR = одна функция, несколько данных, объединенные результаты.

Систолические массивы используют заранее определенный граф вычислительного потока, соединяющий их узлы. Сети процессов Кана используют аналогичный граф потока, но отличаются узлами, работающими синхронно в систолическом массиве: в сети Кана существуют очереди FIFO. между каждым узлом.

Подробное описание [ править ]

Систолический массив состоит из матричных строк блоков обработки данных , называемых ячейками. Блоки обработки данных (DPU) аналогичны центральным процессорам (CPU), (за исключением обычного отсутствия счетчика программ , ^[3]поскольку операция инициируется транспортом , т. е. по прибытии объекта данных). Каждая ячейка делится информацией со своими соседями сразу после обработки. Систолический массив часто имеет прямоугольную форму, где данные проходят через массив между соседними DPU , часто разные данные передаются в разных направлениях. Потоки данных, входящие и исходящие из портов массива, генерируются блоками памяти с автоматическим упорядочением (ASM). Каждый ASM включает в себя счетчик данных . Во встроенных системах поток данных также может вводиться и/или выводиться из внешнего источника.

Пример систолического алгоритма может быть разработан для умножения матриц . Одна матрица подается построчно сверху массива и передается вниз по массиву, другая матрица подается по столбцу за раз с левой стороны массива и передается слева направо. Затем передаются фиктивные значения до тех пор, пока каждый процессор не увидит одну целую строку и один целый столбец. На этом этапе результат умножения сохраняется в массиве и теперь может выводиться по строке или по столбцу за раз, проходя вниз или по массиву. ^[4]

Систолические массивы — это массивы DPU , которые подключены к небольшому количеству ближайших соседних DPU в топологии, напоминающей сетку. DPU выполняют последовательность операций над данными, которые передаются между ними. Поскольку традиционные методы синтеза систолического массива применяются с использованием алгебраических алгоритмов, можно получить только однородные массивы только с линейными каналами, так что архитектура одинакова во всех DPU. В результате на классических систолических массивах можно реализовать только приложения с регулярными зависимостями данных. Подобно машинам SIMD , тактируемые систолические массивы выполняют синхронные вычисления, при этом каждый процессор выполняет попеременные вычисления | коммуницировать фазы. А вот систолические массивы с асинхронным установлением связи между DPU называются массивами волнового фронта . Университета Карнеги-Меллона Одним из хорошо известных систолических массивов является процессор iWarp , производимый Intel. Система iWarp имеет процессор с линейным массивом, соединенный шинами данных, идущими в обоих направлениях.

История [ править ]

Систолические матрицы (также известные как процессоры волнового фронта ) были впервые описаны Х. Т. Кунгом и Чарльзом Э. Лейзерсоном , которые опубликовали первую статью с описанием систолических матриц в 1979 году. Однако первой машиной, которая, как известно, использовала подобную технику, был Colossus Mark II. в 1944 году.

Пример применения [ править ]

Полиномиальная оценка

Правило Горнера для вычисления полинома:

y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.

Линейный систолический массив, в котором процессоры расположены попарно: входные данные умножаются на $x$ и передает результат вправо, следующий добавляет $a_{j}$ и передает результат вправо.

Преимущества и недостатки [ править ]

Плюсы

Быстрее, чем процессоры общего назначения
Масштабируемый

Минусы

Дорого из-за низкой экономии за счет масштаба.
Требуется узкоспециализированное, специальное оборудование, часто зависящее от приложения.
Не широко реализовано
Ограниченная кодовая база программ и алгоритмов. (Не все алгоритмы могут быть реализованы в виде систолических массивов. Часто требуются хитрости, чтобы сопоставить такие алгоритмы с систолическим массивом.)

Реализации [ править ]

Сетевой процессор Cisco PXF внутренне организован в виде систолического массива. ^[5]
Google TPU также разработан на основе систолического массива.
Система текстового поиска Paracel FDF4T TestFinder ^[6]
Paracel FDF4G GeneMatcher Биологическая поисковая система (ДНК и белок)
Чип Inferentia в Amazon Web Services ^[7]
MIT Eyeriss — это ускоритель систолических массивов для сверточных нейронных сетей. ^[8]^[9]

См. также [ править ]

MISD - отдельные данные с несколькими командами, пример: систолические массивы
iWarp – компьютер с систолическим массивом, СБИС, Intel/CMU
WARP (систолическая матрица) – компьютер систолической матрицы, GE/CMU
Тензорный процессор – AI -ускоритель ASIC

Примечания [ править ]

^ Колосс - Величайший секрет в истории вычислений на YouTube
^ http://www.eecs.harvard.edu/~htk/publication/1984-ieeetoc-brent-kung.pdf ^{[ пустой URL PDF ]}
^ Серия процессоров систолического массива Paracel GeneMatcher имеет программный счетчик . Более сложные алгоритмы реализуются как серия простых шагов со сменами, указанными в инструкциях.
^ Умножение матрицы систолического массива
^ «Установка механизма маршрутизации производительности маршрутизатора Cisco серии 10000» . Проверено 3 августа 2020 г. .
^ «О Параселе» . www.brandprosgroup.com . Парасель . Проверено 4 мая 2018 г.
^ «Объявляем о доступности экземпляров Inf1 в Amazon SageMaker для высокопроизводительного и экономичного вывода машинного обучения» . 14 августа 2020 г. Проверено 15 августа 2020 г.
^ «Проект Айрисс» . Eyeriss.mit.edu . Проверено 21 февраля 2021 г.
^ Чен, Ю-Синь; Эмер, Джоэл; Сзе, Вивьен (12 октября 2016 г.). «Eyeriss: пространственная архитектура энергоэффективного потока данных для сверточных нейронных сетей» . Новости компьютерной архитектуры ACM SIGARCH . 44 (3): 367–379. дои : 10.1145/3007787.3001177 . ISSN 0163-5964 . S2CID 3291270 .

Ссылки [ править ]

Х.Т. Кунг, К.Э. Лейзерсон: Алгоритмы для процессорных массивов СБИС; в: К. Мид, Л. Конвей (ред.): Введение в системы СБИС; Аддисон-Уэсли, 1979 год.
С.Ю. Кунг: Процессоры массивов СБИС; Прентис-Холл, Инк., 1988 г.
Н. Петков: Систолическая параллельная обработка; Издательство Северной Голландии, 1992 г.

Внешние ссылки [ править ]

[1] Колосс - Величайший секрет в истории вычислений на YouTube

[2] ttp://www.eecs.harvard.edu/~htk/publication/1984-ieeetoc-brent-kung.pdf ^{[ пустой URL PDF ]}

[3] Серия процессоров систолического массива Paracel GeneMatcher имеет программный счетчик . Более сложные алгоритмы реализуются как серия простых шагов со сменами, указанными в инструкциях.

[4] Умножение матрицы систолического массива

[5] «Установка механизма маршрутизации производительности маршрутизатора Cisco серии 10000» . Проверено 3 августа 2020 г. .

[FDF4-6] «О Параселе» . www.brandprosgroup.com . Парасель . Проверено 4 мая 2018 г.

[7] «Объявляем о доступности экземпляров Inf1 в Amazon SageMaker для высокопроизводительного и экономичного вывода машинного обучения» . 14 августа 2020 г. Проверено 15 августа 2020 г.

[8] «Проект Айрисс» . Eyeriss.mit.edu . Проверено 21 февраля 2021 г.

[9] Чен, Ю-Синь; Эмер, Джоэл; Сзе, Вивьен (12 октября 2016 г.). «Eyeriss: пространственная архитектура энергоэффективного потока данных для сверточных нейронных сетей» . Новости компьютерной архитектуры ACM SIGARCH . 44 (3): 367–379. дои : 10.1145/3007787.3001177 . ISSN 0163-5964 . S2CID 3291270 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]