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

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

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

Приложения

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

Архитектура

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

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

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

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

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

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

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

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

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

Несмотря на все вышесказанное, систолические массивы часто предлагаются в качестве классического примера архитектуры MISD в учебниках. параллельные вычисления и в инженерном классе. Если смотреть на массив снаружи как атомный его, возможно, следует классифицировать как SFMuDMeR = Одна функция, несколько данных, объединенные результаты.

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

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

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

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

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

История

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

Пример применения

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Май 2016)

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

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

${ Displaystyle у = ( 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}.}$

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

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

Плюсы

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

Минусы

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

Реализации

• Cisco Сетевой процессор PXF внутренне организован как систолический массив.^[4]
• Google ТПУ также разработан на основе систолического массива.
• Система текстового поиска Paracel FDF4T TestFinder^[5]
• Система поиска Paracel FDF4G GeneMatcher Biological (ДНК и белок)
• Чип Inferentia в Веб-сервисы Amazon ^[6]

Смотрите также

• MISD - Отдельные данные с несколькими инструкциями, пример: систолические массивы
• iWarp - Компьютер систолической матрицы, СБИС, Intel / CMU
• WARP (систолический массив) - Систолический матричный компьютер, GE / CMU
• Блок тензорной обработки - AI ускоритель ASIC

Примечания

Рекомендации

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

• Х. Т. Кунг, К. Э. Лейзерсон: Алгоритмы для массивов процессоров СБИС; в: К. Мид, Л. Конвей (ред.): Введение в системы СБИС; Эддисон-Уэсли, 1979 г.
• С. Я. Кунг: Процессоры массивов СБИС; Prentice-Hall, Inc., 1988 г.
• Н. Петков: Систолическая параллельная обработка; Издательство Северной Голландии, 1992 г.

внешняя ссылка

• Инструкция систолического массива (ISA)
• «Архитектура СБИС для регистрации изображений в реальном времени» (на основе систолического массива), Vol. 15 сентября 2007 г.