В информатике потоковая обработка (также известная как обработка потока событий , обработка потока данных или обработка распределенного потока ) — это парадигма программирования , которая рассматривает потоки или последовательности событий во времени как центральные объекты ввода и вывода вычислений . Потоковая обработка включает в себя программирование потоков данных , реактивное программирование и распределенную обработку данных . [1] Системы потоковой обработки стремятся обеспечить параллельную обработку потоков данных и полагаются на потоковые алгоритмы для эффективной реализации. Стек программного обеспечения для этих систем включает такие компоненты, как модели программирования и языки запросов для выражения вычислений; системы управления потоками для распределения и планирования ; и аппаратные компоненты для ускорения , включая модули с плавающей запятой , графические процессоры и программируемые пользователем вентильные матрицы . [2]
Парадигма потоковой обработки упрощает параллельное программное и аппаратное обеспечение, ограничивая возможные параллельные вычисления. Учитывая последовательность данных ( поток ), к каждому элементу потока применяется ряд операций ( функций ядра ). Функции ядра обычно являются конвейерными , и предпринимаются попытки оптимального повторного использования локальной памяти на кристалле, чтобы минимизировать потери пропускной способности, связанные с взаимодействием с внешней памятью. Типичной является унифицированная потоковая передача , при которой одна функция ядра применяется ко всем элементам потока. Поскольку абстракции ядра и потока раскрывают зависимости данных, инструменты компилятора могут полностью автоматизировать и оптимизировать задачи управления на кристалле. Аппаратное обеспечение потоковой обработки может использовать табло , например, для инициации прямого доступа к памяти (DMA), когда зависимости становятся известны. Устранение ручного управления DMA снижает сложность программного обеспечения, а связанное с этим исключение аппаратного кэширования ввода-вывода уменьшает объем области данных, которая должна быть задействована при обслуживании специализированными вычислительными устройствами, такими как арифметико-логические устройства .
В 1980-е годы обработка потоков изучалась в рамках программирования потоков данных . Примером может служить язык SISAL (потоки и итерации в одном языке присвоения).
Потоковая обработка, по сути, является компромиссом, основанным на модели, ориентированной на данные, которая очень хорошо работает для традиционных приложений типа DSP или GPU (таких как обработка изображений, видео и цифровых сигналов ), но в меньшей степени для обработки общего назначения с более рандомизированным доступом к данным ( например, базы данных). Жертвуя некоторой гибкостью модели, это обеспечивает более простое, быстрое и эффективное выполнение. В зависимости от контекста конструкция процессора может быть настроена на максимальную эффективность или на компромисс с гибкостью.
Потоковая обработка особенно подходит для приложений, которые демонстрируют три характеристики приложения :
Примеры записей в потоках включают в себя:
Каждую запись мы можем только читать со входа, выполнять над ней операции и записывать на выход. Допустимо иметь несколько входов и несколько выходов, но никогда не использовать часть памяти, доступную как для чтения, так и для записи.
В качестве иллюстрации следующие фрагменты кода демонстрируют обнаружение шаблонов в потоках событий. Первый — это пример обработки потока данных с использованием непрерывного SQL- запроса (запрос, который выполняет постоянную обработку поступающих данных на основе временных меток и продолжительности окна). Этот фрагмент кода иллюстрирует СОЕДИНЕНИЕ двух потоков данных: одного для заказов на акции, а другого для результирующих сделок с акциями. Запрос выводит поток всех ордеров, соответствующих сделке, в течение одной секунды после размещения ордера. Выходной поток сортируется по временной метке, в данном случае по временной метке из потока Orders.
ВЫБЕРИТЕ заказы потока данных . Метка времени , Заказы . идентификатор заказа , Заказы . тикер , заказы . сумма , Торговля . сумма ОТ ордеров ПРИСОЕДИНЯЙТЕСЬ к сделкам НАД ( ДИАПАЗОННЫЙ ИНТЕРВАЛ '1' СЛЕДУЮЩАЯ СЕКУНА ) НА ордера . orderId = Сделки . номер заказа ; Другой пример фрагмента кода обнаруживает свадьбы среди потока внешних «событий», таких как звон церковных колоколов, появление мужчины в смокинге или утреннем костюме, женщины в струящемся белом платье и летящего в воздухе риса. «Сложное» или «составное» событие — это то, что можно сделать из отдельных простых событий: происходит свадьба.
КОГДА Человек . Пол РАВНО «мужчина» И Личность . Одежда РАВНО «смокингу» , за которым следует человек . Одежда РАВНО «платью» И ( Церковный колокол ИЛИ Рисовый полет ) В ТЕЧЕНИЕ 2 ЧАСОВ АКЦИЯ Свадьба Базовые компьютеры начинались с парадигмы последовательного выполнения. Традиционные процессоры основаны на SISD , что означает, что они концептуально выполняют только одну операцию за раз. По мере развития мировых вычислительных потребностей объем данных, которыми нужно управлять, очень быстро увеличивался. Было очевидно, что модель последовательного программирования не может справиться с возросшей потребностью в вычислительной мощности. Были потрачены различные усилия на поиск альтернативных способов выполнения огромных объемов вычислений, но единственным решением было использование некоторого уровня параллельного выполнения. Результатом этих усилий стала SIMD — парадигма программирования, которая позволяла применять одну инструкцию к множеству экземпляров (разных) данных. Большую часть времени SIMD использовался в среде SWAR . Используя более сложные структуры, можно также обеспечить параллелизм MIMD .
Хотя эти две парадигмы были эффективны, реальные реализации имели ограничения: от проблем с выравниванием памяти до проблем синхронизации и ограниченного параллелизма. Лишь немногие процессоры SIMD сохранились как автономные компоненты; большинство из них были встроены в стандартные процессоры.
Рассмотрим простую программу, складывающую два массива, содержащие 100 4-компонентных векторов (т.е. всего 400 чисел).
for ( int i = 0 ; i < 400 ; i ++ ) результат [ i ] = source0 [ i ] + source1 [ i ]; Это наиболее знакомая последовательная парадигма. Вариации действительно существуют (например, внутренние циклы, структуры и т. д.), но в конечном итоге они сводятся к этой конструкции.
for ( int el = 0 ; el < 100 ; el ++ ) // для каждого вектора вектор_сумма ( result [ el ], source0 [ el ], source1 [ el ]); На самом деле это слишком упрощенно. Предполагается, что инструкция vector_sumработает. Хотя именно это и происходит с внутренними функциями инструкций , здесь на самом деле не учитывается большая часть информации, такая как количество векторных компонентов и формат их данных. Это сделано для ясности.
Однако вы можете видеть, что этот метод уменьшает количество декодированных инструкций с numElements *ComponentsPerElement до numElements . Количество инструкций перехода также уменьшается, поскольку цикл выполняется меньшее количество раз. Эти преимущества являются результатом параллельного выполнения четырех математических операций.
Однако произошло следующее: упакованный регистр SIMD содержит определенный объем данных, поэтому добиться большего параллелизма невозможно. Ускорение несколько ограничено тем, что мы сделали предположение о выполнении четырех параллельных операций (обратите внимание, что это характерно как для AltiVec , так и для SSE ).
// Это вымышленный язык, предназначенный для демонстрационных целей. elements = массивstreamElement ([ число , число ] )[ 100 ] kernel = экземплярstreamKernel ( "@arg0[@iter] " ) result = kernel . вызвать ( элементы ) В этой парадигме определяется весь набор данных, а не каждый компонентный блок отдельно. Предполагается, что описание набора данных находится в первых двух строках. После этого результат выводится из исходников и ядра. Для простоты между входными и выходными данными существует соотношение 1:1, но это не обязательно. Прикладные ядра также могут быть гораздо более сложными.
Реализация этой парадигмы может «развернуть» цикл внутри. Это позволяет масштабировать пропускную способность в зависимости от сложности чипа, легко используя сотни ALU. [3] [4] Устранение сложных шаблонов данных делает большую часть этой дополнительной мощности доступной.
Хотя потоковая обработка является ветвью обработки SIMD/MIMD, их не следует путать. Хотя реализации SIMD часто могут работать «потоковым» образом, их производительность несопоставима: модель предполагает совершенно другой шаблон использования, который сам по себе обеспечивает гораздо большую производительность.
Было отмечено, что при применении к универсальным процессорам, таким как стандартный ЦП, можно достичь ускорения только в 1,5 раза. [5] Напротив, одноранговые потоковые процессоры легко достигают десятикратного увеличения производительности, главным образом благодаря более эффективному доступу к памяти и более высокому уровню параллельной обработки. [6]
Хотя модель допускает различные степени гибкости, потоковые процессоры обычно накладывают некоторые ограничения на размер ядра или потока. Например, потребительское оборудование часто неспособно выполнять высокоточные математические операции, не имеет сложных цепочек косвенных адресов или имеет более низкие ограничения на количество команд, которые могут быть выполнены.
Проекты обработки потоков Стэнфордского университета включали Стэнфордский проект программируемого затенения в реальном времени, начатый в 1999 году. [7] Прототип под названием Imagine был разработан в 2002 году. [8] Проект под названием Merrimac работал примерно до 2004 года. [9] AT&T также исследовала потоковые потоки. усовершенствованные процессоры, поскольку графические процессоры быстро развивались как по скорости, так и по функциональности. [1] С тех пор были разработаны десятки языков потоковой обработки, а также специализированное оборудование.
Самая неотложная проблема в области параллельной обработки заключается не столько в типе используемой аппаратной архитектуры, сколько в том, насколько легко будет запрограммировать рассматриваемую систему в реальной среде с приемлемой производительностью. Такие машины, как Imagine, используют простую однопоточную модель с автоматическими зависимостями, распределением памяти и планированием DMA . Это само по себе является результатом исследований Массачусетского технологического института и Стэнфорда по поиску оптимального распределения задач между программистом, инструментами и оборудованием. Программисты превосходят инструменты в сопоставлении алгоритмов с параллельным оборудованием, а инструменты превосходят программистов в определении наиболее разумных схем распределения памяти и т. д. Особую озабоченность вызывают конструкции MIMD, такие как Cell , для которых программисту приходится иметь дело с разделением приложений по нескольким ядрам и иметь дело с синхронизация процессов и балансировка нагрузки.
Недостатком программирования SIMD была проблема массивов структур (AoS) и структур массивов (SoA) . Программисты часто создают в памяти представления объектов, например расположение частицы в трехмерном пространстве, цвет шара и его размер, как показано ниже:
// Частица в трехмерном пространстве. structarticle_t { float x , y , z ; _ // даже не массив! цвет беззнакового байта [ 3 ]; // 8 бит на канал, скажем, нас интересует только размер плавающей точки RGB ; // ... и за ним могут следовать многие другие атрибуты... }; Когда в памяти существует несколько таких структур, они размещаются встык, образуя массивы в топологии массива структур (AoS). Это означает, что если какой-либо алгоритм будет применен к местоположению каждой частицы по очереди, он должен будет пропустить ячейки памяти, содержащие другие атрибуты. Если эти атрибуты не нужны, это приводит к расточительному использованию кэша ЦП. Кроме того, инструкция SIMD обычно ожидает, что данные, с которыми она будет работать, будут непрерывными в памяти; элементы также могут нуждаться в выравнивании . Перемещая область памяти данных из структуры, данные можно лучше организовать для эффективного доступа в потоке и для выполнения инструкций SIMD. Структура массивов (SoA), как показано ниже, позволяет это сделать.
structarticle_t { float * x , * y , * z ; _ беззнаковый байт * colorRed , * colorBlue , * colorGreen ; плавающий * размер ; }; Вместо хранения данных в структуре он хранит только указатели (ячейки памяти) для данных. Недостатки заключаются в том, что если необходимо обработать несколько атрибутов объекта, они могут оказаться удаленными в памяти и, таким образом, привести к промаху в кэше. Выравнивание и любые необходимые дополнения приводят к увеличению использования памяти. В целом, управление памятью может быть более сложным, если, например, структуры добавляются и удаляются.
Для потоковых процессоров приветствуется использование структур. С точки зрения приложения все атрибуты могут быть определены с некоторой гибкостью. Если взять за основу графические процессоры, то имеется набор атрибутов (не менее 16). Для каждого атрибута приложение может указать количество компонентов и формат компонентов (но на данный момент поддерживаются только примитивные типы данных). Различные атрибуты затем прикрепляются к блоку памяти, возможно, определяя шаг между «последовательными» элементами одних и тех же атрибутов, что эффективно позволяет чередовать данные. Когда графический процессор начинает обработку потока, он собирает все различные атрибуты в единый набор параметров (обычно это выглядит как структура или «магическая глобальная переменная»), выполняет операции и распределяет результаты в некоторую область памяти для дальнейшего использования. обработка (или извлечение).
Более современные платформы потоковой обработки предоставляют интерфейс типа FIFO для структурирования данных в виде буквального потока. Эта абстракция предоставляет средства для неявного указания зависимостей данных, позволяя при этом среде выполнения/аппаратному обеспечению в полной мере использовать эти знания для эффективных вычислений. Одним из самых простых [ нужна цитата ] и наиболее эффективных [ нужна цитата ] модальностей потоковой обработки для C++ на сегодняшний день является RaftLib , который позволяет связывать независимые вычислительные ядра вместе в виде графа потока данных с помощью потоковых операторов C++. В качестве примера:
#include <raft> #include <raftio> #include <cstdlib> #include <string> класс привет : общественный плот :: ядро { общественный : привет () : плот :: ядро () { выход . addPort < std :: string > ( «0» ); } виртуальный плот :: kstatus run () { вывод [ "0" ]. push ( std :: string ( "Hello World \n " )); возвращение плота :: остановка ; } }; int main ( int argc , char ** argv ) { /** создаем экземпляр ядра печати **/ raft :: print < std :: string > p ; /** создать экземпляр ядра hello world **/ hi hello ; /** создаем объект карты **/ raft :: map m ; /** добавляем ядра в карту, и hello, и p выполняются одновременно **/ m += hello >> p ; /** выполнить карту **/ m . Exe (); вернуть EXIT_SUCCESS ; } Помимо описания потоковых приложений на языках высокого уровня, модели вычислений (MoC) также широко используются в качестве моделей потоков данных и моделей, основанных на процессах.
Исторически процессоры начали реализовывать различные уровни оптимизации доступа к памяти из-за постоянно растущей производительности по сравнению с относительно медленно растущей пропускной способностью внешней памяти. По мере того, как этот разрыв увеличивался, большие площади кристалла были отведены для сокрытия задержек памяти. Поскольку получение информации и кодов операций в эти несколько ALU обходится дорого, очень небольшая площадь кристалла отведена под реальные математические машины (по грубой оценке, считайте, что она составляет менее 10%).
Похожая архитектура существует в потоковых процессорах, но благодаря новой модели программирования количество транзисторов, предназначенных для управления, на самом деле очень мало.
С точки зрения всей системы потоковые процессоры обычно существуют в контролируемой среде. Графические процессоры существуют на плате расширения (похоже, это относится и к Imagine). Процессоры продолжают выполнять работу по управлению системными ресурсами, запуску приложений и тому подобное.
Потоковый процессор обычно оснащен быстрой и эффективной собственной шиной памяти (в настоящее время широко распространены перекрестные переключатели, раньше использовались несколько шин). Точное количество полос памяти зависит от рыночного диапазона. На момент написания все еще существуют 64-битные соединения (начального уровня). В большинстве моделей среднего класса используется быстрая 128-битная перекрестная матрица коммутации (4 или 2 сегмента), а в моделях высокого класса используются огромные объемы памяти (фактически до 512 МБ) с немного более медленной перекрестной матрицей шириной 256 бит. Напротив, стандартные процессоры от Intel Pentium до некоторых Athlon 64 имеют только одну шину данных шириной 64 бита.
Шаблоны доступа к памяти гораздо более предсказуемы. Хотя массивы существуют, их размерность фиксируется при вызове ядра. Косвенность с несколькими указателями наиболее точно соответствует цепочке косвенности , которая, однако, гарантированно в конечном итоге будет читать или записывать из определенной области памяти (внутри потока).
Из-за SIMD-природы исполнительных блоков потокового процессора (кластеров ALU) ожидается, что операции чтения/записи будут выполняться массово, поэтому память оптимизирована для высокой пропускной способности, а не для низкой задержки (в этом отличие от Rambus и DDR SDRAM , поскольку пример). Это также позволяет эффективно согласовывать шину памяти.
Большая часть (90%) работы потокового процессора выполняется на кристалле, поэтому в памяти требуется хранить только 1% глобальных данных. Именно здесь полезно знать временные параметры ядра и зависимости.
Внутри потокового процессора имеется несколько умных схем связи и управления, но что интересно, так это файл регистрации потока (SRF). Концептуально это большой кеш, в котором хранятся потоковые данные для массовой передачи во внешнюю память. Являясь программно-управляемой структурой, напоминающей кэш, для различных ALU , SRF совместно используется всеми различными кластерами ALU. Ключевая концепция и новшество, реализованное с помощью чипа Imagine из Стэнфорда, заключается в том, что компилятор способен автоматизировать и распределять память оптимальным способом, полностью прозрачным для программиста. Зависимости между функциями ядра и данными известны через модель программирования, которая позволяет компилятору выполнять анализ потока и оптимально упаковывать SRF. Обычно управление кешем и DMA может занимать большую часть расписания проекта, что полностью автоматизирует потоковый процессор (или, по крайней мере, Imagine). Тесты, проведенные в Стэнфорде, показали, что компилятор справился с планированием памяти не хуже, а то и лучше, чем если бы вы настроили его вручную с большими усилиями.
Есть доказательства; Кластеров может быть много, поскольку предполагается, что межкластерные коммуникации редки. Однако внутри каждый кластер может эффективно использовать гораздо меньшее количество ALU, поскольку внутрикластерная связь является обычным явлением и, следовательно, должна быть высокоэффективной.
Чтобы обеспечить выборку данных из этих ALU, каждое ALU оснащено файлами локальных регистров (LRF), которые по сути являются его используемыми регистрами.
Этот трехуровневый шаблон доступа к данным позволяет легко хранить временные данные вдали от медленной памяти, что делает полупроводниковую реализацию высокоэффективной и энергосберегающей.
Хотя можно разумно ожидать ускорения на порядок (даже от основных графических процессоров при потоковых вычислениях), не все приложения выигрывают от этого. Задержки связи на самом деле являются самой большой проблемой. Хотя PCI Express улучшил эту ситуацию за счет полнодуплексной связи, запуск графического процессора (и, возможно, обычного потокового процессора) может занять много времени. Это означает, что обычно использовать их для небольших наборов данных непродуктивно. Поскольку изменение ядра — довольно дорогостоящая операция, потоковая архитектура также влечет за собой штрафы за небольшие потоки — такое поведение называется эффектом короткого потока .
Конвейерная обработка — очень распространенная и активно используемая практика в потоковых процессорах, при этом графические процессоры имеют конвейеры, превышающие 200 стадий. Стоимость переключения настроек зависит от изменяемой настройки, но теперь считается, что она всегда дорогая. Чтобы избежать этих проблем на различных уровнях конвейера, было использовано множество методов, таких как «сверхшейдеры» и «атласы текстур». Эти методы ориентированы на игры из-за особенностей графических процессоров, но эти концепции интересны и для общей потоковой обработки.
Большинство языков программирования для потоковых процессоров начинаются с Java, C или C++ и добавляют расширения, которые предоставляют специальные инструкции, позволяющие разработчикам приложений маркировать ядра и/или потоки. Это также относится к большинству языков шейдеров , которые в определенной степени можно считать потоковыми языками программирования.
Некоммерческие примеры языков потокового программирования включают:
Коммерческие реализации либо универсальны, либо привязаны к конкретному оборудованию поставщиком. Примеры языков общего назначения включают в себя:
Языки, специфичные для конкретного поставщика, включают:
Обработка событий
Пакетная обработка на основе файлов (имитирует часть реальной потоковой обработки, но в целом производительность гораздо ниже [ необходимы пояснения ] [ нужна ссылка ] )
Непрерывная обработка потока операторов [ нужны разъяснения ]
Сервисы потоковой обработки: