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

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

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

ПримененияПравить

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

АрхитектураПравить

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

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

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

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

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

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

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

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

Несмотря на все вышесказанное, систолические массивы часто предлагаются в качестве классического примера архитектуры MISD в учебниках по параллельным вычислениям и на инженерных курсах. Если массив рассматривается извне как атомарный, его, возможно, следует классифицировать как SFMuDMeR (англ. Single Function, Multiple Data, Merged Result(s)) одна функция, множество данных, объединенный результат (ы).

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

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

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

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

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

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

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

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

\text{[math]}

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}.

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

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

Плюсы

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

Минусы

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

РеализацииПравить

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

См. такжеПравить

MISD — несколько инструкций, одиночные данные, пример: систолические массивы
iWarp — компьютер с систолическим массивом, СБИС, Intel/CMU
WARP (систолический массив) — Компьютер систолического массива, GE/CMU
Tensor Processing Unit — ускоритель ИИ ASIC

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

↑ Colossus - The Greatest Secret in the History of Computing на YouTube
↑ The Paracel GeneMatcher series of systolic array processors do have a program counter. More complicated algorithms are implemented as a series of simple steps, with shifts specified in the instructions.
↑ Systolic Array Matrix Multiplication
↑ Cisco 10000 Series Router Performance Routing Engine Installation (неопр.). Дата обращения: 3 августа 2020.
↑ About Paracel (неопр.). brandprosgroup.com. Paracel. Дата обращения: 4 мая 2018.
↑ Announcing availability of Inf1 instances in Amazon SageMaker for high performance and cost-effective machine learning inference (неопр.). Дата обращения: 15 августа 2020.
↑ Eyeriss Project (неопр.). eyeriss.mit.edu. Дата обращения: 21 февраля 2021.
↑ Chen, Yu-Hsin (2016-10-12). “Eyeriss: a spatial architecture for energy-efficient dataflow for convolutional neural networks”. ACM SIGARCH Computer Architecture News [англ.]. 44 (3): 367—379. DOI:10.1145/3007787.3001177. ISSN 0163-5964.