В параллельных компьютерных архитектурах систолический массив представляет собой однородную сеть тесно связанных блоков обработки данных (DPU), называемых ячейками или узлами . Каждый узел или DPU независимо вычисляет частичный результат как функцию данных, полученных от его соседей выше по потоку, сохраняет результат внутри себя и передает его ниже по потоку. Систолические массивы впервые были использованы в Colossus , который был одним из первых компьютеров, использовавшихся для взлома немецких шифров Лоренца во время Второй мировой войны . [1] Из-за секретной природы Colossus они были независимо изобретены или переоткрыты Х. Т. Кунгом и Чарльзом Лейзерсоном, которые описали массивы для многих плотных вычислений линейной алгебры (произведение матриц, решение систем линейных уравнений , LU-разложение и т. д.) для ленточных матриц. Ранние приложения включают вычисление наибольших общих делителей целых чисел и многочленов. [2] Иногда их классифицируют как архитектуры с несколькими инструкциями и одним набором данных (MISD) в соответствии с таксономией Флинна , но эта классификация сомнительна, поскольку можно привести весомый аргумент в пользу отличия систолических массивов от любой из четырех категорий Флинна: SISD , SIMD , MISD , MIMD , как обсуждается далее в этой статье.
Параллельные входные данные проходят через сеть жестко соединенных процессорных узлов, которые объединяют, обрабатывают, объединяют или сортируют входные данные в производный результат. Поскольку волнообразное распространение данных через систолический массив напоминает пульс человеческой кровеносной системы, название «систолический» было взято из медицинской терминологии. Название происходит от слова «систола» по аналогии с регулярным перекачиванием крови сердцем.
Систолические массивы часто жестко запрограммированы для определенных операций, таких как «умножение и накопление», для выполнения задач массивной параллельной интеграции, свертки , корреляции , умножения матриц или сортировки данных. Они также используются для динамических алгоритмов программирования, используемых в анализе последовательностей ДНК и белков .
Систолический массив обычно состоит из большой монолитной сети примитивных вычислительных узлов , которые могут быть жестко подключены или сконфигурированы программно для конкретного приложения. Узлы обычно фиксированы и идентичны, в то время как межсоединение программируемо. Более общие процессоры волнового фронта , напротив, используют сложные и индивидуально программируемые узлы, которые могут быть или не быть монолитными, в зависимости от размера массива и параметров конструкции. Другое отличие заключается в том, что систолические массивы полагаются на синхронную передачу данных, в то время как волновой фронт, как правило, работает асинхронно.
В отличие от более распространенной архитектуры фон Неймана , где выполнение программы следует сценарию инструкций, хранящихся в общей памяти, адресуемых и упорядоченных под управлением счетчика программ ЦП ( ПК), отдельные узлы в систолическом массиве запускаются при поступлении новых данных и всегда обрабатывают данные точно таким же образом. Фактическая обработка в каждом узле может быть жестко запрограммирована или блочно- микрокодирована , в этом случае общая личность узла может быть блочно-программируемой.
Парадигма систолического массива с потоками данных, управляемыми счетчиками данных , является аналогом архитектуры фон Неймана с потоком инструкций, управляемым счетчиком программ. Поскольку систолический массив обычно отправляет и получает несколько потоков данных, и для генерации этих потоков данных требуется несколько счетчиков данных, он поддерживает параллелизм данных .
Главным преимуществом систолических массивов является то, что все данные операндов и частичные результаты хранятся внутри (проходя через) массива процессора. Нет необходимости обращаться к внешним шинам, основной памяти или внутренним кэшам во время каждой операции, как в случае с последовательными машинами Фон Неймана или Гарварда . Последовательные ограничения на параллельную производительность, диктуемые законом Амдаля, также не применяются таким же образом, поскольку зависимости данных неявно обрабатываются программируемым межсоединеним узлов , и нет последовательных шагов в управлении высокопараллельным потоком данных.
Поэтому систолические массивы чрезвычайно хороши в искусственном интеллекте, обработке изображений, распознавании образов, компьютерном зрении и других задачах, которые особенно хорошо выполняют мозги животных. Процессоры Wavefront в целом также могут быть очень хороши в машинном обучении, реализуя самоконфигурируемые нейронные сети в оборудовании.
Хотя систолические массивы официально классифицируются как MISD , их классификация несколько проблематична. Поскольку входные данные обычно являются вектором независимых значений, систолический массив определенно не является SISD . Поскольку эти входные значения объединяются и комбинируются в результат(ы) и не сохраняют свою независимость , как это было бы в блоке обработки векторов SIMD , массив не может быть классифицирован как таковой. Следовательно, массив также не может быть классифицирован как MIMD , поскольку MIMD можно рассматривать как простое собрание меньших машин SISD и SIMD .
Наконец, поскольку рой данных преобразуется по мере прохождения через массив от узла к узлу, несколько узлов не работают с одними и теми же данными, что делает классификацию MISD неправильной . Другая причина, по которой систолический массив не должен подпадать под категорию MISD , та же самая, что и та, которая исключает его из категории SISD: входные данные обычно представляют собой вектор, а не отдельное значение данных , хотя можно утверждать, что любой заданный входной вектор представляет собой отдельный элемент данных.
Несмотря на все вышесказанное, систолические массивы часто предлагаются как классический пример архитектуры MISD в учебниках по параллельным вычислениям и на инженерных курсах. Если массив рассматривать снаружи как атомарный, его, возможно, следует классифицировать как SFMuDMeR = single function, multiple data, merged result(s).
Систолические массивы используют предопределенный вычислительный поток, который соединяет их узлы. Сети процессов Кана используют похожий поток, но отличаются тем, что узлы работают в режиме lock-step в систолическом массиве: в сети Кана между каждым узлом существуют очереди FIFO.
Систолический массив состоит из матрично-подобных строк блоков обработки данных, называемых ячейками. Блоки обработки данных (DPU) похожи на центральные процессоры (CPU), (за исключением обычного отсутствия счетчика программ , [3] поскольку операция запускается транспортом , т. е. поступлением объекта данных). Каждая ячейка делится информацией со своими соседями сразу после обработки. Систолический массив часто бывает прямоугольным, где данные протекают через массив между соседними DPU , часто с различными данными, текущими в разных направлениях. Потоки данных, входящие и исходящие из портов массива, генерируются блоками памяти с автоупорядочением, ASM. Каждый ASM включает счетчик данных . Во встраиваемых системах поток данных также может быть введен из внешнего источника и/или выведен на него.
Пример систолического алгоритма может быть разработан для умножения матриц . Одна матрица подается по строке за раз сверху массива и передается вниз по массиву, другая матрица подается по столбцу за раз с левой стороны массива и передается слева направо. Затем передаются фиктивные значения до тех пор, пока каждый процессор не увидит одну целую строку и один целый столбец. На этом этапе результат умножения сохраняется в массиве и теперь может быть выведен по строке или столбцу за раз, протекая вниз или по массиву. [4]
Систолические массивы — это массивы DPU , которые соединены с небольшим количеством ближайших соседних DPU в сетчатой топологии. DPU выполняют последовательность операций с данными, которые передаются между ними. Поскольку традиционные методы синтеза систолических массивов практиковались алгебраическими алгоритмами, можно получить только однородные массивы только с линейными каналами, так что архитектура будет одинаковой во всех DPU. Следствием этого является то, что на классических систолических массивах можно реализовать только приложения с регулярными зависимостями данных. Как и машины SIMD , тактируемые систолические массивы вычисляют в «синхронном режиме», когда каждый процессор выполняет альтернативные фазы вычислений | связи. Но систолические массивы с асинхронным квитированием между DPU называются массивами волнового фронта . Одним из известных систолических массивов является процессор iWarp Университета Карнеги-Меллона , который был произведен Intel. Система iWarp имеет линейный процессор массива, соединенный шинами данных, идущими в обоих направлениях.
Систолические массивы (также известные как процессоры волнового фронта ) были впервые описаны Х. Т. Кунгом и Чарльзом Э. Лейзерсоном , которые опубликовали первую статью, описывающую систолические массивы, в 1979 году. Однако первой известной машиной, использовавшей подобную технологию, был Colossus Mark II , выпущенный в 1944 году.
Правило Горнера для оценки многочлена:
Линейный систолический массив, в котором процессоры расположены парами: один умножает свой вход на и передает результат вправо, следующий складывает и передает результат вправо.
