stringtranslate.com

Потоковая обработка

В информатике потоковая обработка (также известная как обработка потока событий , обработка потока данных или распределенная потоковая обработка ) — это парадигма программирования , которая рассматривает потоки или последовательности событий во времени как центральные входные и выходные объекты вычислений . Потоковая обработка охватывает программирование потоков данных , реактивное программирование и распределенную обработку данных . [1] Системы потоковой обработки нацелены на предоставление параллельной обработки для потоков данных и полагаются на потоковые алгоритмы для эффективной реализации. Программный стек для этих систем включает такие компоненты, как модели программирования и языки запросов для выражения вычислений; системы управления потоками для распределения и планирования ; и аппаратные компоненты для ускорения, включая блоки с плавающей точкой , графические процессоры и программируемые пользователем вентильные матрицы . [2]

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

В 1980-х годах потоковая обработка исследовалась в рамках программирования потоков данных . Примером может служить язык SISAL (Streams and Iteration in a Single Assignment Language).

Приложения

Потоковая обработка по сути является компромиссом, обусловленным моделью, ориентированной на данные, которая очень хорошо работает для традиционных приложений DSP или GPU-типа (таких как обработка изображений, видео и цифровых сигналов ), но в меньшей степени для обработки общего назначения с более рандомизированным доступом к данным (таким как базы данных). Принося в жертву некоторую гибкость в модели, последствия позволяют более легкое, быстрое и эффективное выполнение. В зависимости от контекста, конструкция процессора может быть настроена на максимальную эффективность или компромисс для гибкости.

Потоковая обработка особенно подходит для приложений, которые демонстрируют три характеристики: [ необходима ссылка ]

Примеры записей в потоках включают в себя:

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

Примеры кода

В качестве иллюстрации следующие фрагменты кода демонстрируют обнаружение шаблонов в потоках событий. Первый пример — это обработка потока данных с использованием непрерывного SQL- запроса (запрос, который выполняет непрерывную обработку поступающих данных на основе временных меток и длительности окна). Этот фрагмент кода иллюстрирует JOIN двух потоков данных, одного для заказов на акции и одного для полученных сделок на акции. Запрос выводит поток всех заказов, соответствующих сделке в течение одной секунды с момента размещения заказа. Выходной поток сортируется по временной метке, в данном случае по временной метке из потока заказов.

ВЫБРАТЬ DataStream Orders.TimeStamp , Orders.orderId , Orders.ticker , Orders.sum , Trade.sum FROM Orders JOIN Trades OVER ( RANGE INTERVAL ' 1 ' SECOND FOLLOWING ) ON Orders.orderId = Trades.orderId ;​​​​​​​​​​​​

Другой фрагмент кода-образца обнаруживает свадьбы среди потока внешних «событий», таких как звон церковных колоколов, появление мужчины в смокинге или утреннем костюме, женщины в развевающемся белом платье и летящего по воздуху риса. «Сложное» или «составное» событие — это то, что выводится из отдельных простых событий: свадьба происходит.

КОГДА Person . Gender РАВНО " мужчина" И Person . Clothes РАВНО "смокинг" , ЗАТЕМ Person . Clothes РАВНО "платье" И ( Church_Bell ИЛИ Rice_Flying ) В ТЕЧЕНИЕ 2 ЧАСОВ ДЕЙСТВИЕ Свадьба

Сравнение с предыдущими параллельными парадигмами

Базовые компьютеры начинались с последовательной парадигмы выполнения. Традиционные процессоры основаны на SISD , что означает, что они концептуально выполняют только одну операцию за раз. По мере развития вычислительных потребностей мира объем управляемых данных увеличивался очень быстро. Было очевидно, что последовательная модель программирования не могла справиться с возросшей потребностью в вычислительной мощности. Различные усилия были потрачены на поиск альтернативных способов выполнения огромных объемов вычислений, но единственным решением было использование некоторого уровня параллельного выполнения. Результатом этих усилий стала SIMD , парадигма программирования, которая позволяла применять одну инструкцию к нескольким экземплярам (разных) данных. Большую часть времени SIMD использовалась в среде SWAR . Используя более сложные структуры, можно было также получить параллелизм MIMD .

Хотя эти две парадигмы были эффективны, реальные реализации страдали от ограничений, связанных с проблемами выравнивания памяти, проблемами синхронизации и ограниченным параллелизмом. Лишь немногие процессоры SIMD выжили как автономные компоненты; большинство были встроены в стандартные ЦП.

Рассмотрим простую программу, складывающую два массива, содержащих 100 4-компонентных векторов (т.е. всего 400 чисел).

Обычная, последовательная парадигма

для ( int i = 0 ; i < 400 ; i ++ ) результат [ i ] = источник0 [ i ] + источник1 [ i ];

Это наиболее знакомая последовательная парадигма. Существуют вариации (например, внутренние циклы, структуры и т. п.), но в конечном итоге они сводятся к этой конструкции.

Парадигма параллельного SIMD, упакованные регистры (SWAR)

for ( int el = 0 ; el < 100 ; el ++ ) // для каждого вектора Vector_sum ( result [ el ], source0 [ el ], source1 [ el ]);

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

Однако вы можете видеть, что этот метод уменьшает количество декодированных инструкций с numElements * componentsPerElement до numElements . Количество инструкций перехода также уменьшается, поскольку цикл выполняется меньшее количество раз. Эти преимущества являются результатом параллельного выполнения четырех математических операций.

Однако произошло то, что упакованный регистр SIMD содержит определенный объем данных, поэтому невозможно получить больше параллелизма. Ускорение несколько ограничено предположением, которое мы сделали о выполнении четырех параллельных операций (обратите внимание, что это общее как для AltiVec , так и для SSE ).

Парадигма параллельного потока (SIMD/MIMD)

// Это вымышленный язык для демонстрационных целей. elements = array streamElement ( [ number , number ])[ 100 ] kernel = instance streamKernel ( "@arg0[@iter]" ) result = kernel.invoke ( elements )

В этой парадигме определяется весь набор данных, а не каждый блок компонентов определяется отдельно. Предполагается, что описание набора данных находится в первых двух строках. После этого результат выводится из источников и ядра. Для простоты существует сопоставление 1:1 между входными и выходными данными, но это не обязательно. Применяемые ядра также могут быть намного сложнее.

Реализация этой парадигмы может «развернуть» цикл изнутри. Это позволяет масштабировать пропускную способность в зависимости от сложности чипа, легко используя сотни АЛУ. [3] [4] Устранение сложных шаблонов данных делает большую часть этой дополнительной мощности доступной.

Хотя потоковая обработка является ветвью обработки SIMD/MIMD, их не следует путать. Хотя реализации SIMD часто могут работать в "потоковом" режиме, их производительность несопоставима: модель предполагает совершенно иной шаблон использования, который сам по себе обеспечивает гораздо большую производительность.

Было отмечено, что при применении на универсальных процессорах, таких как стандартный ЦП, можно достичь ускорения только в 1,5 раза. [5] Напротив, специальные потоковые процессоры легко достигают более чем 10-кратной производительности, в основном за счет более эффективного доступа к памяти и более высоких уровней параллельной обработки. [6]

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

Исследовать

Проекты потоковой обработки Стэнфордского университета включали проект Стэнфордского реального времени программируемого шейдинга, начатый в 1999 году. [7] Прототип под названием Imagine был разработан в 2002 году. [8] Проект под названием Merrimac продолжался примерно до 2004 года. [9] AT&T также исследовала потоковые процессоры, поскольку графические процессоры быстро развивались как по скорости, так и по функциональности. [1] С тех пор были разработаны десятки языков потоковой обработки, а также специализированное оборудование.

Заметки о модели программирования

Самая непосредственная проблема в области параллельной обработки заключается не столько в типе используемой аппаратной архитектуры, сколько в том, насколько легко будет запрограммировать рассматриваемую систему в реальной среде с приемлемой производительностью. Такие машины, как Imagine, используют простую однопоточную модель с автоматизированными зависимостями, распределением памяти и планированием DMA . Это само по себе является результатом исследований в MIT и Стэнфорде по поиску оптимального распределения задач между программистом, инструментами и оборудованием. Программисты превосходят инструменты в отображении алгоритмов на параллельное оборудование, а инструменты превосходят программистов в определении самых умных схем распределения памяти и т. д. Особую озабоченность вызывают конструкции MIMD, такие как Cell , для которых программисту необходимо иметь дело с разделением приложений на несколько ядер и заниматься синхронизацией процессов и балансировкой нагрузки.

Недостатком программирования SIMD была проблема массива структур (AoS) и структуры массивов (SoA) . Программисты часто создают представления сущностей в памяти, например, местоположение частицы в трехмерном пространстве, цвет мяча и его размер, как показано ниже:

 // Частица в трехмерном пространстве. struct partial_t { float x , y , z ; // даже не массив! unsigned byte color [ 3 ]; // 8 бит на канал, скажем, нас интересует только RGB float size ; // ... и многие другие атрибуты могут следовать... };

Если в памяти существует несколько таких структур, они размещаются встык, создавая массивы в топологии массива структур (AoS). Это означает, что если какой-то алгоритм будет применен к местоположению каждой частицы по очереди, он должен пропустить области памяти, содержащие другие атрибуты. Если эти атрибуты не нужны, это приводит к расточительному использованию кэша ЦП. Кроме того, инструкция SIMD обычно ожидает, что данные, с которыми она будет работать, будут смежными в памяти, элементы также могут нуждаться в выравнивании . Перемещая область памяти данных из структуры, данные могут быть лучше организованы для эффективного доступа в потоке и для инструкций SIMD для работы с ним. Структура массивов (SoA), как показано ниже, может позволить это.

struct partial_t { float * x , * y , * z ; беззнаковый байт * colorRed , * colorBlue , * colorGreen ; float * size ; };

Вместо того, чтобы хранить данные в структуре, он хранит только указатели (места памяти) для данных. Недостатки в том, что если необходимо обработать несколько атрибутов объекта, они могут оказаться удаленными в памяти, что приведет к пропуску кэша. Выравнивание и любое необходимое заполнение приводят к увеличению использования памяти. В целом, управление памятью может быть более сложным, если, например, структуры добавляются и удаляются.

Для потоковых процессоров рекомендуется использовать структуры. С точки зрения приложения все атрибуты могут быть определены с некоторой гибкостью. Если взять в качестве примера графические процессоры, то доступен набор атрибутов (не менее 16). Для каждого атрибута приложение может указать количество компонентов и формат компонентов (но на данный момент поддерживаются только примитивные типы данных). Затем различные атрибуты прикрепляются к блоку памяти, возможно, определяя шаг между «последовательными» элементами тех же атрибутов, что фактически позволяет чередовать данные. Когда графический процессор начинает обработку потока, он собирает все различные атрибуты в один набор параметров (обычно это выглядит как структура или «магическая глобальная переменная»), выполняет операции и распределяет результаты по некоторой области памяти для последующей обработки (или извлечения).

Более современные фреймворки потоковой обработки предоставляют интерфейс типа FIFO для структурирования данных в виде буквального потока. Эта абстракция предоставляет средства для неявного указания зависимостей данных, позволяя среде выполнения/оборудованию в полной мере использовать эти знания для эффективных вычислений. Одним из самых простых [ требуется цитата ] и наиболее эффективных [ требуется цитата ] модальностей потоковой обработки на сегодняшний день для C++ является RaftLib , который позволяет связывать независимые вычислительные ядра вместе в виде графа потока данных с использованием потоковых операторов C++. Например:

#include <raft> #include <raftio> #include <cstdlib> #include <string>    класс hi : public raft :: kernel { public : hi () : raft :: kernel () { output . addPort < std :: string > ( "0" ); }            virtual raft :: kstatus run () { output [ "0" ]. push ( std :: string ( "Hello World \n " )); return raft :: stop ; } };        int main ( int argc , char ** argv ) { /** создать экземпляр ядра print **/ raft :: print < std :: string > p ; /** создать экземпляр ядра hello world **/ hi hello ; /** создать объект map **/ raft :: map m ; /** добавить ядра к map, hello и p выполняются одновременно **/ m += hello >> p ; /** выполнить map **/ m . exe (); return EXIT_SUCCESS ; }

Модели вычислений для потоковой обработки

Помимо спецификации потоковых приложений на языках высокого уровня, модели вычислений (MoC) также широко используются в качестве моделей потоков данных и моделей, основанных на процессах.

Общая архитектура процессора

Исторически ЦП начали реализовывать различные уровни оптимизации доступа к памяти из-за постоянно растущей производительности по сравнению с относительно медленно растущей внешней пропускной способностью памяти. По мере увеличения этого разрыва большие объемы площади кристалла были выделены для сокрытия задержек памяти. Поскольку извлечение информации и кодов операций для этих нескольких АЛУ обходится дорого, очень малая часть площади кристалла выделена для фактической математической машины (в качестве грубой оценки считайте, что она составляет менее 10%).

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

Начиная с точки зрения всей системы, потоковые процессоры обычно существуют в контролируемой среде. Графические процессоры существуют на дополнительной плате (это, кажется, также применимо к Imagine). Процессоры продолжают выполнять работу по управлению системными ресурсами, запуску приложений и т. д.

Потоковый процессор обычно оснащен быстрой, эффективной, фирменной шиной памяти (сейчас распространены перекрестные коммутаторы, в прошлом использовались многошинные). Точное количество полос памяти зависит от рыночного диапазона. На момент написания все еще существуют 64-битные межсоединения (начального уровня). Большинство моделей среднего класса используют быструю 128-битную матрицу перекрестных коммутаторов (4 или 2 сегмента), в то время как высокопроизводительные модели развертывают огромные объемы памяти (фактически до 512 МБ) с немного более медленной перекрестной матрицей шириной 256 бит. Напротив, стандартные процессоры от Intel Pentium до некоторых Athlon 64 имеют только одну 64-битную шину данных.

Модели доступа к памяти гораздо более предсказуемы. Хотя массивы существуют, их размерность фиксируется при вызове ядра. То, что наиболее близко соответствует множественной косвенной адресации указателя, — это цепочка косвенной адресации , которая, однако, гарантированно в конечном итоге прочитает или запишет из определенной области памяти (внутри потока).

Из-за SIMD-природы исполнительных блоков потокового процессора (кластеров АЛУ) ожидается, что операции чтения/записи будут выполняться оптом, поэтому память оптимизируется для высокой пропускной способности, а не для низкой задержки (в этом отличие от Rambus и DDR SDRAM , например). Это также позволяет эффективно согласовывать шину памяти.

Большая часть (90%) работы потокового процессора выполняется на чипе, требуя только 1% глобальных данных для хранения в памяти. Вот где знание временных объектов и зависимостей ядра окупается.

Внутри потоковый процессор имеет несколько умных схем связи и управления, но что интересно, так это потоковый регистровый файл (SRF). Это концептуально большой кэш, в котором потоковые данные хранятся для передачи во внешнюю память большими партиями. Как кэш-подобная программно-управляемая структура для различных ALU , SRF совместно используется всеми различными кластерами ALU. Ключевая концепция и инновация, реализованная здесь с помощью чипа Imagine Стэнфорда, заключается в том, что компилятор может автоматизировать и выделять память оптимальным образом, полностью прозрачным для программиста. Зависимости между функциями ядра и данными известны через модель программирования, которая позволяет компилятору выполнять анализ потока и оптимально упаковывать SRF. Обычно это кэширование и управление DMA могут занимать большую часть расписания проекта, что потоковый процессор (или, по крайней мере, Imagine) полностью автоматизирует. Тесты, проведенные в Стэнфорде, показали, что компилятор справился с планированием памяти так же хорошо или даже лучше, чем если бы вы вручную настраивали это с большими усилиями.

Доказательство есть; кластеров может быть много, поскольку предполагается, что межкластерная коммуникация редка. Однако внутри каждый кластер может эффективно использовать гораздо меньшее количество АЛУ, поскольку внутрикластерная коммуникация обычна и, следовательно, должна быть высокоэффективной.

Для хранения данных в этих АЛУ каждое АЛУ оснащено локальными файлами регистров (LRF), которые по сути являются его используемыми регистрами.

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

Проблемы с аппаратным обеспечением

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

Конвейеризация — очень распространенная и активно используемая практика в потоковых процессорах, причем графические процессоры имеют конвейеры, превышающие 200 стадий. Стоимость переключения настроек зависит от изменяемой настройки, но теперь она всегда считается дорогой. Чтобы избежать этих проблем на различных уровнях конвейера, было развернуто много методов, таких как «über shaders» и «texture atlases». Эти методы ориентированы на игры из-за природы графических процессоров, но концепции интересны и для общей потоковой обработки.

Примеры

Библиотеки и языки потокового программирования

Большинство языков программирования для потоковых процессоров начинаются с Java, C или C++ и добавляют расширения, которые предоставляют специальные инструкции, позволяющие разработчикам приложений помечать ядра и/или потоки. Это также относится к большинству языков шейдеров , которые в определенной степени можно считать потоковыми языками программирования.

Некоммерческие примеры потоковых языков программирования включают в себя:

Коммерческие реализации являются либо общими, либо привязаны к определенному оборудованию поставщиком. Примеры языков общего назначения включают:

Языки, специфичные для поставщика, включают:

Обработка на основе событий

Пакетная обработка файлов (эмулирует часть реальной потоковой обработки, но в целом имеет гораздо более низкую производительность [ необходимо пояснение ] [ необходима ссылка ] )

Непрерывная обработка потока оператора [ требуется разъяснение ]

Услуги потоковой обработки:

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

Ссылки

  1. ^ КРАТКОЕ ВВЕДЕНИЕ В ОБРАБОТКУ ПОТОКА
  2. ^ FCUDA: Обеспечение эффективной компиляции ядер CUDA на FPGA
  3. ^ Журнал IEEE по твердотельным схемам: «Программируемый потоковый процессор 512 GOPS для обработки сигналов, изображений и видео», Стэнфордский университет и Stream Processors, Inc.
  4. ^ Хайлани, Далли, Рикснер, Капаси, Оуэнс и Тоулз: «Изучение масштабируемости СБИС потоковых процессоров», Стэнфордский университет и университет Райса.
  5. ^ Гуммараджу и Розенблюм, «Потоковая обработка в процессорах общего назначения», Стэнфордский университет.
  6. ^ Капаси, Далли, Рикснер, Хайлани, Оуэнс, Ан и Мэттсон, «Программируемые потоковые процессоры», Университеты Стэнфорда, Райса, Калифорнии (Дэвис) и Reservoir Labs.
  7. ^ Эрик Чан. "Stanford Real-Time Programmable Shading Project". Веб-сайт исследовательской группы . Получено 9 марта 2017 г.
  8. ^ "The Imagine - Image and Signal Processor". Веб-сайт группы . Получено 9 марта 2017 г.
  9. ^ "Merrimac - Stanford Streaming Supercomputer Project". Веб-сайт группы . Архивировано из оригинала 18 декабря 2013 г. Получено 9 марта 2017 г.
  10. ^ Представьте себе
  11. ^ Мерримак
  12. ^ Memeti, Suejb; Pllana, Sabri (октябрь 2018 г.). «HSTREAM: расширение языка на основе директив для гетерогенных потоковых вычислений». Международная конференция IEEE по вычислительной науке и технике (CSE) 2018 г. IEEE. стр. 138–145. arXiv : 1809.09387 . doi :10.1109/CSE.2018.00026. ISBN 978-1-5386-7649-3.
  13. ^ PeakStream представляет решение для программирования многоядерных процессоров и ЦП/ГП
  14. ^ TStreams: модель параллельных вычислений (технический отчет).
  15. ^ TStreams: Как написать параллельную программу (технический отчет).
  16. ^ "GitHub - walmartlabs/Mupd8: Маппет". GitHub .