В параллельных компьютерных архитектур , А систолического массив является однородной сетью тесно связанных блоков обработки данных (ППН) , называемых клетками или узлами . Каждый узел или DPU независимо вычисляет частичный результат в зависимости от данных, полученных от его вышестоящих соседей, сохраняет результат внутри себя и передает его вниз по потоку. Систолические массивы были изобретены Х.Т. Кунгом и Чарльзом Лейзерсоном, которые описали массивы для многих вычислений плотной линейной алгебры (матричное произведение, решение систем линейных уравнений , LU-разложение и т. Д.) Для ленточных матриц. Ранние приложения включают вычисленияНаибольшие общие делители целых чисел и многочленов. [1] Они иногда классифицируются как архитектуры с несколькими инструкциями и одним данными (MISD) в соответствии с таксономией Флинна , но эта классификация сомнительна, поскольку может быть приведен веский аргумент, позволяющий отличить систолические массивы от любой из четырех категорий Флинна: SISD , SIMD , MISD. , MIMD , как описано далее в этой статье.
Параллельные входные данные проходят через сеть жестко подключенных процессорных узлов, которые объединяют, обрабатывают, объединяют или сортируют входные данные в производный результат. Поскольку волнообразное распространение данных через систолический массив напоминает пульс кровеносной системы человека, название систолическое произошло из медицинской терминологии. Название происходит от слова « систола» по аналогии с обычным перекачиванием крови сердцем.
Приложения [ править ]
Систолические массивы часто жестко запрограммированы для определенных операций, таких как «умножение и накопление», для выполнения массово- параллельной интеграции, свертки , корреляции , умножения матриц или задач сортировки данных. Они также используются для алгоритмов динамического программирования , используемых в анализе последовательностей ДНК и белков .
Архитектура [ править ]
Систолический массив обычно состоит из большой монолитной сети примитивных вычислительных узлов, которые могут быть аппаратно или программно настроены для конкретного приложения. Узлы обычно фиксированные и идентичные, а межсоединение программируемое. Напротив, более общие процессоры волнового фронта используют сложные и индивидуально программируемые узлы, которые могут быть или не быть монолитными, в зависимости от размера массива и параметров конструкции. Другое отличие состоит в том, что систолические массивы полагаются на синхронную передачу данных, в то время как волновой фронт, как правило, работает асинхронно .
В отличие от более общей архитектуры фон Неймана , где выполнение программы следует сценарий команд , сохраненных в общей памяти, на имя и секвенировали под контролем CPU «ы счетчика команд (PC), отдельные узлы в пределах систолического массива вызваны прибытием новых данных и всегда обрабатывайте данные одинаково. Фактическая обработка в каждом узле может быть жестко зашитой или блочно- микрокодированной , и в этом случае индивидуальность общего узла может быть блочно-программируемой.
Парадигма систолического массива с потоками данных , управляемыми счетчиками данных , является аналогом архитектуры фон Неймана с потоком команд, управляемым счетчиком программ. Поскольку систолический массив обычно отправляет и принимает несколько потоков данных, а для генерации этих потоков данных требуется несколько счетчиков данных, он поддерживает параллелизм данных .
Цели и преимущества [ править ]
Основным преимуществом систолических массивов является то, что все данные операндов и частичные результаты хранятся внутри (проходя через) массив процессора. Нет необходимости обращаться к внешним шинам, основной памяти или внутренним кэшам во время каждой операции, как в случае с последовательными машинами фон Неймана или Гарварда . Последовательные ограничения параллельной производительности, продиктованные законом Амдала, также не применяются таким же образом, потому что зависимости данных неявно обрабатываются межсоединением программируемых узлов, и нет никаких последовательных шагов в управлении высокопараллельным потоком данных.
Таким образом, систолические массивы чрезвычайно хороши для искусственного интеллекта, обработки изображений, распознавания образов, компьютерного зрения и других задач, с которыми мозг животных справляется особенно хорошо. Процессоры Wavefront в целом также могут быть очень хороши в машинном обучении, реализуя самонастраивающиеся нейронные сети на оборудовании.
Споры о классификации [ править ]
Хотя систолические массивы официально классифицируются как MISD , их классификация несколько проблематична. Поскольку входные данные обычно представляют собой вектор независимых значений, систолический массив определенно не является SISD . Поскольку эти входные значения объединяются и объединяются в результат (ы) и не сохраняют свою независимость, как это было бы в блоке векторной обработки SIMD , массив не может быть классифицирован как таковой. Следовательно, массив также не может быть классифицирован как MIMD , потому что MIMD можно рассматривать как простую совокупность меньших SISD- и SIMD- машин.
Наконец, поскольку рой данных преобразуется при прохождении через массив от узла к узлу, несколько узлов не работают с одними и теми же данными, что делает классификацию MISD неверной . Другая причина , почему систолический массив не должен считаться MISD такой же , как тот , который дисквалифицирует его из категории SISD: входные данные обычно представляют собой вектор не с Ingle д ату значения, хотя можно утверждать , что любой данный вход вектор - это единый набор данных.
Несмотря на все вышесказанное, систолические массивы часто предлагаются в качестве классического примера архитектуры MISD в учебниках по параллельным вычислениям и в инженерных классах. Если массив рассматривается снаружи как атомарный, его, вероятно, следует классифицировать как SFMuDMeR = Single Function, Multiple Data, Merged Result (s).
Систолические массивы используют заранее определенный вычислительный потоковый граф, который соединяет их узлы. Технологические сети Кана используют аналогичный потоковый граф, но отличаются узлами, работающими синхронно в систолическом массиве: в сети Кана между каждым узлом есть очереди FIFO.
Подробное описание [ править ]
Систолический массив состоит из матричных строк блоков обработки данных, называемых ячейками. Блоки обработки данных (ППН) похожи на центральных процессоров (CPU), (для обычного отсутствия кроме счетчика программы , [2] , так как операции транспортно-срабатывает , то есть, с приходом объекта данных). Каждая ячейка передает информацию своим соседям сразу после обработки. Систолический массив часто имеет прямоугольную форму, где данные передаются через массив между соседними DPU , часто с разными данными, протекающими в разных направлениях. Потоки данных, входящие и выходящие из портов массива, генерируются блоками памяти с автопоследовательностью, ASM. Каждый ASM включает данныесчетчик . Во встроенных системах поток данных также может вводиться и / или выводиться из внешнего источника.
Пример систолического алгоритма может быть разработан для умножения матриц . Одна матрица подается по строкам сверху массива и передается вниз по массиву, другая матрица подается по столбцам с левой стороны массива и проходит слева направо. Затем передаются фиктивные значения до тех пор, пока каждый процессор не увидит одну целую строку и один целый столбец. На этом этапе результат умножения сохраняется в массиве, и теперь его можно выводить по строке или столбцу за раз, перемещаясь вниз или по массиву. [3]
Систолические массивы - это массивы DPU, которые подключены к небольшому количеству ближайших соседних DPU в сетчатой топологии. DPU выполняют последовательность операций с данными, которые передаются между ними. Поскольку традиционные методы синтеза систолических массивов применялись на практике с помощью алгебраических алгоритмов, могут быть получены только однородные массивы только с линейными каналами, так что архитектуры одинаковы для всех DPU. Следствием этого является то, что на классических систолических массивах могут быть реализованы только приложения с регулярными зависимостями данных. Подобно машинам SIMD , синхронизированные систолические массивы вычисляют «синхронно», при этом каждый процессор выполняет альтернативные вычисления | общаться фазы. Но систолические массивы с асинхронным подтверждением связи между DPU называются массивами волнового фронта.. Одним из хорошо известных систолических наборов является процессор iWarp Университета Карнеги-Меллона , производимый Intel. Система iWarp имеет процессор линейного массива, соединенный шинами данных, идущими в обоих направлениях.
История [ править ]
Систолические массивы (также известные как процессоры волнового фронта ) были впервые описаны HT Kung и Charles E. Leiserson , которые опубликовали первую статью, описывающую систолические массивы в 1979 году. Однако первой машиной, которая, как известно, использовала подобную технику, была Colossus Mark II. в 1944 г.
Пример применения [ править ]
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Май 2016 г. ) |
- Полиномиальная оценка
Правило Хорнера для вычисления многочлена:
Линейный систолический массив, в котором процессоры расположены попарно: один умножает свой ввод на и передает результат вправо, следующий добавляет и передает результат вправо.
Преимущества и недостатки [ править ]
В этом разделе не процитировать любые источники . ( Декабрь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Плюсы
- Быстрее процессоров общего назначения
- Масштабируемый
Минусы
- Дорого из-за невысокой экономии на масштабе
- Требуется узкоспециализированное специализированное оборудование, которое часто зависит от конкретного приложения.
- Не широко применяется
- Ограниченная кодовая база программ и алгоритмов. (Не все алгоритмы могут быть реализованы в виде систолических массивов. Часто требуются уловки, чтобы сопоставить такие алгоритмы с систолическим массивом.)
Реализации [ править ]
- Сетевой процессор Cisco PXF внутренне организован как систолический массив. [4]
- TPU Google также разработан на основе систолического массива.
- Система текстового поиска Paracel FDF4T TestFinder [5]
- Система поиска биологических (ДНК и белки) Paracel FDF4G GeneMatcher
- Чип Inferentia в Amazon Web Services [6]
- MIT Eyeriss - это ускоритель систолического массива для сверточных нейронных сетей. [7] [8]
См. Также [ править ]
- MISD - отдельные данные с несколькими инструкциями, пример: систолические массивы
- iWarp - Компьютер систолического массива, СБИС, Intel / CMU
- WARP (систолический массив) - компьютер систолического массива, GE / CMU
- Блок тензорной обработки - AI- ускоритель ASIC
Заметки [ править ]
- ^ http://www.eecs.harvard.edu/~htk/publication/1984-ieeetoc-brent-kung.pdf
- ^ Серия процессоров систолического массива Paracel GeneMatcher имеет программный счетчик . Более сложные алгоритмы реализуются в виде серии простых шагов со сдвигами, указанными в инструкциях.
- ^ Систолическое матричное умножение массива
- ^ «Установка модуля маршрутизации производительности маршрутизатора Cisco серии 10000» . Дата обращения 3 августа 2020 .
- ^ «О Параселе» . brandprosgroup.com . Парасель . Дата обращения 4 мая 2018 .
- ^ «Объявление о доступности инстансов Inf1 в Amazon SageMaker для обеспечения высокой производительности и экономичности машинного обучения» . Проверено 15 августа 2020 .
- ^ "Проект Эйерисс" . eyeriss.mit.edu . Проверено 21 февраля 2021 года .
- ^ Чен, Ю-Синь; Эмер, Джоэл; Зе, Вивьен (12 октября 2016 г.). «Eyeriss: пространственная архитектура для энергоэффективного потока данных для сверточных нейронных сетей» . Новости компьютерной архитектуры ACM SIGARCH . 44 (3): 367–379. DOI : 10.1145 / 3007787.3001177 . ISSN 0163-5964 .
Ссылки [ править ]
 | Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Апрель 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
- HT Kung, CE Leiserson: Алгоритмы для массивов процессоров СБИС; в: К. Мид, Л. Конвей (ред.): Введение в системы СБИС; Эддисон-Уэсли, 1979 г.
- С.Ю. Кунг: Процессоры для массивов СБИС; Prentice-Hall, Inc., 1988 г.
- Н. Петков: Систолическая параллельная обработка; Издательство North Holland Publishing Co, 1992 г.
Внешние ссылки [ править ]
- Систолический массив инструкций (ISA)
- «Архитектура СБИС для регистрации изображений в реальном времени» (на основе систолического массива), Vol. 15 сентября 2007 г.
