В параллельных компьютерных архитектурах систолический массив представляет собой однородную сеть тесно связанных блоков обработки данных (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 году.
Правило Горнера для вычисления полинома:
Линейный систолический массив, в котором процессоры расположены попарно: один умножает входные данные и передает результат вправо, следующий складывает и передает результат вправо.
Плюсы
Минусы
