Введение

Тип параллельной вычислительной архитектуры с плотно связанными узлами.

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

Приложения

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

Архитектура

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

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

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

Спор о классификации

Хотя систолические массивы официально классифицируются как MISD, их классификация представляется несколько проблематичной. Поскольку входные данные обычно представляют собой вектор независимых значений, систолический массив определенно не является SISD. Так как эти входные значения объединяются и комбинируются в результат(ы) и теряют свою независимость, в отличие от векторного процессора SIMD, массив нельзя классифицировать и как SIMD. Следовательно, массив также нельзя отнести к MIMD, поскольку MIMD можно рассматривать как просто набор меньших SISD и SIMD машин. Наконец, поскольку поток данных преобразуется по мере прохождения через массив от узла к узлу, множественные узлы не оперируют с одними и теми же данными, что делает классификацию MISD не совсем корректной. Другая причина, по которой систолический массив не должен считаться MISD, аналогична той, что исключает его из категории SISD: входные данные обычно представляют собой вектор, а не одно значение данных, хотя можно утверждать, что любой входной вектор является единым элементом данных. Несмотря на все вышесказанное, систолические массивы часто приводятся в качестве классического примера архитектуры MISD в учебниках по параллельным вычислениям и на инженерных курсах. Если рассматривать массив как неделимую сущность, то, возможно, его следует классифицировать как SFMuDMeR = единая функция, множественные данные, объединенный результат(ы). Систолические массивы используют предопределенный граф вычислений, соединяющий их узлы. Сети процессов Кана используют аналогичный граф потока, но отличаются тем, что узлы в систолическом массиве работают синхронно, а в сети Кана между каждым узлом имеются FIFO-очереди.

Подробное описание

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

История

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