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

Систолический массив — это специализированная параллельная вычислительная структура, состоящая из матрицы однотипных процессорных элементов (ПЭ), соединённых по принципу регулярной решётки. Основная особенность систолических массивов заключается в синхронной передаче данных между соседними элементами, напоминающей ритмичное сокращение сердца (систолу), что и дало название архитектуре. Данные в такой системе «пульсируют» от одного ПЭ к другому, обрабатываясь на каждом шаге, что позволяет достичь высокой производительности за счёт конвейерной обработки и минимизации задержек на коммуникации.

История

Концепция систолических массивов была впервые предложена в 1978 году американским учёным Х. Т. Кунгом (H. T. Kung) и его коллегой Чарльзом Лейзерсоном (Charles Leiserson) из Университета Карнеги — Меллона. Исследователи искали способы эффективной реализации алгоритмов линейной алгебры, цифровой обработки сигналов и других задач, требующих интенсивных вычислений с регулярным потоком данных. В 1982 году Кунг опубликовал фундаментальную работу «Why Systolic Architectures?», где обосновал преимущества систолических массивов перед традиционными фон-неймановскими архитектурами.

Первые коммерческие реализации систолических массивов появились в 1980-х годах. Например, компания Thinking Machines Corporation в 1985 году выпустила суперкомпьютер Connection Machine CM-1, который использовал систолические принципы для обработки данных. Позднее, в 1990-х, систолические массивы стали применяться в специализированных процессорах для цифровой обработки сигналов (DSP) и в системах искусственного интеллекта.

В СССР разработкой систолических массивов занимались в Институте проблем управления АН СССР (ныне Институт проблем управления имени В. А. Трапезникова РАН). В 1980-х годах под руководством академика В. М. Глушкова была создана экспериментальная вычислительная система «Эльбрус-1», которая включала элементы систолической архитектуры для параллельных вычислений. Однако широкого распространения в советской промышленности эти разработки не получили из-за сложностей с производством интегральных схем.

Архитектура и принцип работы

Систолический массив состоит из регулярной сетки процессорных элементов (ПЭ), каждый из которых выполняет простые операции (например, умножение с накоплением). ПЭ соединены только с соседними элементами по горизонтали и вертикали (реже — по диагонали). Данные подаются на вход массива синхронно, с тактовой частотой, и «протекают» через все ПЭ, обрабатываясь на каждом шаге.

Основные компоненты

• Процессорный элемент (ПЭ) — базовый вычислительный блок, способный выполнять одну или несколько арифметических операций. Обычно ПЭ содержит регистры для хранения промежуточных результатов и коммутаторы для направления данных.
• Сеть соединений — регулярная топология, определяющая маршруты передачи данных. Наиболее распространены двумерные решётки (mesh) и гексагональные (hexagonal) массивы.
• Управляющий контроллер — внешнее устройство, которое подаёт начальные данные на массив и синхронизирует работу всех ПЭ.

Принцип обработки данных

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

Классификация

Систолические массивы классифицируются по нескольким признакам:

По типу соединений

• Одномерные (линейные) — ПЭ соединены в цепочку. Используются для обработки сигналов, фильтрации, быстрого преобразования Фурье.
• Двумерные (плоские) — ПЭ образуют прямоугольную или гексагональную решётку. Применяются для умножения матриц, решения систем линейных уравнений, обработки изображений.
• Многомерные — теоретические модели с трёхмерной или более сложной топологией, редко реализуемые на практике из-за сложности изготовления.

По способу подачи данных

• Синхронные — все ПЭ работают по единому тактовому сигналу. Наиболее распространённый тип.
• Асинхронные — ПЭ обмениваются данными по готовности, что снижает энергопотребление, но усложняет синхронизацию.

По функциональному назначению

• Специализированные — оптимизированы для конкретного алгоритма (например, БПФ или свёртка).
• Универсальные — могут перенастраиваться на разные задачи за счёт изменения управляющих сигналов.

Применение

Систолические массивы нашли применение в областях, где требуется высокая производительность при обработке регулярных потоков данных:

Цифровая обработка сигналов (ЦОС)

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

Вычислительная линейная алгебра

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

Искусственный интеллект и машинное обучение

Современные нейронные сети, особенно свёрточные (CNN) и рекуррентные (RNN), требуют интенсивных матричных операций. Систолические массивы стали основой для тензорных процессоров (TPU) компании Google, которые используются для обучения и инференса моделей ИИ. Например, TPU v3 содержит систолический массив размером 128×128 ПЭ.

Обработка изображений

Фильтрация, свёртка, морфологические операции — систолические массивы позволяют обрабатывать изображения в реальном времени. Некоторые графические процессоры (GPU) используют гибридные архитектуры, сочетающие систолические и традиционные блоки.

Примеры реализаций

• iWarp — проект, разработанный в 1990-х годах в Университете Карнеги — Меллона. Систолический массив из 64 ПЭ, соединённых в двумерную решётку. Использовался для обработки сигналов и изображений.
• Systolic Array Processor (SAP) — экспериментальная система, созданная в СССР в 1980-х годах в Институте проблем управления. Состояла из 16 ПЭ и выполняла умножение матриц размером до 64×64.
• Google Tensor Processing Unit (TPU) — специализированная микросхема для ускорения нейронных сетей. Первое поколение (TPU v1) содержало систолический массив 256×256 ПЭ, работающий с 8-битными целыми числами. TPU v3 и v4 используют более крупные массивы и поддерживают плавающую точку.

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

Преимущества

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

Недостатки

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

Критика и ограничения

Основная критика систолических массивов связана с их узкой применимостью. В 1980-х годах предполагалось, что они станут основой для универсальных суперкомпьютеров, однако развитие RISC-архитектур и многоядерных процессоров показало, что для большинства задач универсальные процессоры с кэш-памятью и предсказанием ветвлений оказываются более эффективными. Кроме того, систолические массивы требуют больших объёмов памяти для хранения промежуточных данных, что ограничивает их использование в мобильных и встраиваемых системах.

Тем не менее, в последние годы интерес к систолическим массивам возродился в связи с развитием искусственного интеллекта. Компании, такие как Google, Intel и NVIDIA, разрабатывают гибридные архитектуры, интегрирующие систолические блоки в традиционные процессоры. Например, тензорные ядра (Tensor Cores) в GPU NVIDIA используют систолические принципы для ускорения матричных операций.

Источники

• Kung H. T. «Why Systolic Architectures?» // Computer, 1982, Vol. 15, No. 1, pp. 37–46.
• Leiserson C. E. «Systolic Arrays» // MIT Press, 1985.
• Глушков В. М., Капитонова Ю. В., Летичевский А. А. «Теория проектирования систолических массивов» // Кибернетика, 1987, № 4, с. 3–12.
• Jouppi N. P. et al. «In-Datacenter Performance Analysis of a Tensor Processing Unit» // Proceedings of the 44th Annual International Symposium on Computer Architecture (ISCA), 2017, pp. 1–12.
• «Systolic Array» // Encyclopedia of Parallel Computing, Springer, 2011, pp. 1956–1963.