Войти
Поток обработки представляет собой компьютерное программирование парадигмы,эквивалентно потоков данных программирования, потоковой обработки событий, и реактивного программирования, что позволяет некоторые приложения к более легко использовать ограниченную форму параллельной обработки. Такие приложения могут использовать несколько вычислительных устройств, таких как точка плавучего о Все графики блока обработки или полевых программируемых вентильных матриц (FPGA), без явного управления распределением, синхронизацию, или связь между этими единицами.
Парадигма потоковой обработки упрощает параллельное программное и аппаратное обеспечение, ограничивая параллельные вычисления, которые могут быть выполнены. Учитывая последовательность данных ( поток), к каждому элементу потока применяется серия операций ( функций ядра ). Функции ядра обычно конвейерные, и предпринимаются попытки оптимального повторного использования локальной встроенной памяти, чтобы минимизировать потерю полосы пропускания, связанную с взаимодействием с внешней памятью. Равномерная потоковая передача, когда одна функция ядра применяется ко всем элементам в потоке, является типичной. Поскольку абстракции ядра и потока раскрывают зависимости данных, инструменты компилятора могут полностью автоматизировать и оптимизировать задачи управления на кристалле. Аппаратное обеспечение потоковой обработки может использовать табло, например, чтобы инициировать прямой доступ к памяти (DMA), когда зависимости становятся известными. Устранение ручного управления прямым доступом к памяти снижает сложность программного обеспечения, а связанное с этим устранение аппаратного кэширования ввода-вывода сокращает объем области данных, который должен быть задействован при обслуживании специализированных вычислительных устройств, таких как устройства арифметической логики.
В течение 1980-х годов обработка потоков была изучена в программировании потоков данных. Примером может служить язык SISAL (потоки и итерации на одном языке назначения).
Потоковая обработка - это, по сути, компромисс, основанный на модели, ориентированной на данные, которая очень хорошо работает для традиционных приложений типа DSP или GPU (таких как обработка изображений, видео и цифровых сигналов ), но в меньшей степени для обработки общего назначения с более рандомизированным доступом к данным ( например, базы данных). Жертвуя некоторой гибкостью модели, последствия позволяют упростить, ускорить и повысить эффективность выполнения. В зависимости от контекста конструкция процессора может быть настроена на максимальную эффективность или на компромисс для гибкости.
Потоковая обработка особенно подходит для приложений, которые обладают тремя характеристиками:
Примеры записей в потоках включают:
Для каждой записи мы можем только читать из ввода, выполнять с ней операции и записывать в выход. Допустимо иметь несколько входов и несколько выходов, но никогда не использовать часть памяти, которая может быть как для чтения, так и для записи.
Базовые компьютеры начали с парадигмы последовательного выполнения. Традиционные процессоры основаны на SISD, что означает, что они концептуально выполняют только одну операцию за раз. По мере развития компьютерных потребностей мира объем данных, которыми необходимо управлять, очень быстро увеличивался. Было очевидно, что модель последовательного программирования не может справиться с возросшей потребностью в вычислительной мощности. Различные усилия были потрачены на поиск альтернативных способов выполнения огромных объемов вычислений, но единственным решением было использование некоторого уровня параллельного выполнения. Результатом этих усилий стала SIMD, парадигма программирования, которая позволяла применять одну инструкцию к нескольким экземплярам (разных) данных. Большую часть времени SIMD использовалась в среде SWAR. Используя более сложные структуры, можно также получить параллелизм MIMD.
Хотя эти две парадигмы были эффективными, реальные реализации страдали от ограничений, от проблем с выравниванием памяти до проблем синхронизации и ограниченного параллелизма. Лишь несколько процессоров SIMD выжили в качестве автономных компонентов; большинство из них были встроены в стандартные процессоры.
Рассмотрим простую программу, складывающую два массива, содержащих 100 4-компонентных векторов (т.е. всего 400 чисел).
for (int i = 0; i lt; 400; i++) result[i] = source0[i] + source1[i];
Это наиболее известная последовательная парадигма. Варианты действительно существуют (например, внутренние циклы, структуры и т. Д.), Но в конечном итоге они сводятся к этой конструкции.
for (int el = 0; el lt; 100; el++) // for each vector vector_sum(result[el], source0[el], source1[el]);
На самом деле это слишком упрощенно. Предполагается, что инструкция vector_sumработает. Хотя это то, что происходит с внутренними функциями инструкций, большая часть информации здесь фактически не принимается во внимание, например, количество компонентов вектора и их формат данных. Это сделано для наглядности.
Однако вы можете видеть, что этот метод уменьшает количество декодируемых инструкций с numElements * componentsPerElement до numElements. Количество инструкций перехода также уменьшается, поскольку цикл выполняется меньше раз. Эти преимущества являются результатом параллельного выполнения четырех математических операций.
Однако произошло то, что упакованный регистр SIMD содержит определенный объем данных, поэтому добиться большего параллелизма невозможно. Ускорение несколько ограничено предположением, которое мы сделали о выполнении четырех параллельных операций (обратите внимание, что это характерно как для AltiVec, так и для SSE ).
// This is a fictional language for demonstration purposes. elements = array streamElement([number, number])[100] kernel = instance streamKernel("@arg0[@iter]") result = kernel.invoke(elements) В этой парадигме определяется весь набор данных, а не каждый компонентный блок отдельно. Предполагается, что описание набора данных находится в первых двух строках. После этого результат выводится из исходников и ядра. Для простоты существует отображение 1: 1 между входными и выходными данными, но это не обязательно. Прикладные ядра также могут быть намного сложнее.
Реализация этой парадигмы может «развернуть» цикл внутренне. Это позволяет масштабировать пропускную способность со сложностью микросхемы, легко используя сотни ALU. Устранение сложных шаблонов данных делает большую часть этой дополнительной мощности доступной.
Хотя потоковая обработка является ветвью обработки SIMD / MIMD, их не следует путать. Хотя реализации SIMD часто могут работать в «потоковом» режиме, их производительность несопоставима: модель предполагает совершенно иной шаблон использования, который сам по себе обеспечивает гораздо более высокую производительность.
Было отмечено, что при применении к универсальным процессорам, таким как стандартный ЦП, может быть достигнуто только 1,5-кратное ускорение. Напротив, специализированные потоковые процессоры легко достигают 10-кратной производительности, в основном за счет более эффективного доступа к памяти и более высоких уровней параллельной обработки.
Хотя модель допускает различные степени гибкости, потоковые процессоры обычно накладывают некоторые ограничения на размер ядра или потока. Например, потребительское оборудование часто не может выполнять высокоточные математические вычисления, не имеет сложных цепочек косвенного обращения или имеет более низкие ограничения на количество инструкций, которые могут быть выполнены.
Проекты потоковой обработки Стэнфордского университета включали Стэнфордский проект программируемого затенения в реальном времени, начатый в 1999 году. Прототип под названием Imagine был разработан в 2002 году. Проект под названием Merrimac выполнялся примерно до 2004 года. ATamp;T также исследовала процессоры с улучшенным потоковым воспроизведением, поскольку графические процессоры быстро развивались в и скорость, и функциональность. С тех пор были разработаны десятки языков потоковой обработки, а также специализированное оборудование.
Самая непосредственная проблема в области параллельной обработки заключается не столько в типе используемой аппаратной архитектуры, сколько в том, насколько легко будет запрограммировать рассматриваемую систему в реальной среде с приемлемой производительностью. Такие машины, как Imagine, используют простую однопоточную модель с автоматическими зависимостями, распределением памяти и планированием DMA. Это само по себе является результатом исследований Массачусетского технологического института и Стэнфорда по поиску оптимального распределения задач между программистом, инструментами и оборудованием. Программисты бить инструменты в алгоритмах отображения на параллельное аппаратное обеспечение, а также инструменты бить программист в выяснении умных схем распределения памяти и т.д. Особой озабоченность вызывают MIMD конструкцию, такие как Cell, для которых потребность программиста, чтобы иметь дело с применением разделения между несколькими ядрами и сделкой с синхронизация процессов и балансировка нагрузки. Сегодня крайне не хватает эффективных инструментов многоядерного программирования.
Недостатком программирования SIMD была проблема массива структур (AoS) и структуры массивов (SoA). Программисты часто хотели создавать структуры данных с «реальным» значением, например:
// A particle in a three-dimensional space. struct particle_t { float x, y, z; // not even an array! unsigned byte color[3]; // 8 bit per channel, say we care about RGB only float size; //... and many other attributes may follow... }; Случилось так, что эти структуры были собраны в массивы, чтобы все было хорошо организовано. Это массив структур (AoS). Когда структура размещается в памяти, компилятор будет создавать чередующиеся данные в том смысле, что все структуры будут смежными, но будет постоянное смещение между, скажем, атрибутом «size» экземпляра структуры и тем же элементом. следующего экземпляра. Смещение зависит от определения структуры (и, возможно, других вещей, которые здесь не рассматриваются, например, политик компилятора). Есть и другие проблемы. Например, три позиционные переменные не могут быть преобразованы в SIMD таким образом, потому что нет уверенности, что они будут размещены в непрерывном пространстве памяти. Чтобы гарантировать, что операции SIMD могут работать с ними, они должны быть сгруппированы в «упакованную ячейку памяти» или, по крайней мере, в массив. Другая проблема заключается в том, что и "цвет", и "xyz" должны быть определены в трехкомпонентных векторных величинах. Процессоры SIMD обычно поддерживают только 4-компонентные операции (однако, за некоторыми исключениями).
Подобные проблемы и ограничения делали ускорение SIMD на стандартных процессорах довольно неприятным. В предлагаемом решении структура массивов (SoA) выглядит следующим образом:
struct particle_t { float *x, *y, *z; unsigned byte *colorRed, *colorBlue, *colorGreen; float *size; }; Для читателей, не знакомых с C, "*" перед каждым идентификатором означает указатель. В этом случае они будут использоваться для указания на первый элемент массива, который будет выделен позже. Для программистов на Java это примерно эквивалентно «[]». Недостатком здесь является то, что различные атрибуты могут быть распределены в памяти. Чтобы убедиться, что это не вызывает промахов в кэше, нам нужно обновить все «красные», затем все «зеленые» и «синие».
Для потоковых процессоров рекомендуется использование структур. С точки зрения приложения все атрибуты могут быть определены с некоторой гибкостью. Если взять графические процессоры в качестве эталона, имеется набор атрибутов (не менее 16). Для каждого атрибута приложение может указать количество компонентов и формат компонентов (но пока поддерживаются только примитивные типы данных). Затем различные атрибуты прикрепляются к блоку памяти, возможно, определяя шаг между «последовательными» элементами одних и тех же атрибутов, что позволяет эффективно перемежать данные. Когда графический процессор начинает обработку потока, он собирает все различные атрибуты в один набор параметров (обычно это выглядит как структура или «волшебная глобальная переменная»), выполняет операции и разбрасывает результаты в некоторую область памяти для последующего использования. обработка (или получение).
Более современные фреймворки потоковой обработки предоставляют интерфейс, подобный FIFO, для структурирования данных в виде буквального потока. Эта абстракция предоставляет средства для неявного указания зависимостей данных, позволяя среде выполнения / оборудованию в полной мере использовать эти знания для эффективных вычислений. На сегодняшний день одним из самых простых и эффективных способов обработки потоков для C ++ является RaftLib, который позволяет связывать независимые вычислительные ядра вместе в виде графа потока данных с использованием операторов потока C ++. В качестве примера:
#include lt;raftgt; #include lt;raftiogt; #include lt;cstdlibgt; #include lt;stringgt; class hi: public raft::kernel { public: hi(): raft::kernel() { output.addPortlt; std::string gt;( "0"); } virtual raft::kstatus run() { output[ "0" ].push( std::string( "Hello World\n")); return( raft::stop); } }; int main( int argc, char **argv) { /** instantiate print kernel **/ raft::printlt; std::string gt; p; /** instantiate hello world kernel **/ hi hello; /** make a map object **/ raft::map m; /** add kernels to map, both hello and p are executed concurrently **/ m += hello gt;gt; p; /** execute the map **/ m.exe(); return( 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. Ключевой концепцией и нововведением, реализованным в чипе Stanford Imagine, является то, что компилятор может автоматизировать и распределять память оптимальным образом, полностью прозрачным для программиста. Зависимости между функциями ядра и данными известны через модель программирования, которая позволяет компилятору выполнять анализ потока и оптимально упаковывать SRF. Обычно это управление кешем и DMA может занять большую часть расписания проекта, что полностью автоматизирует потоковый процессор (или, по крайней мере, Imagine). Тесты, проведенные в Стэнфорде, показали, что компилятор справился с планированием памяти так же или лучше, чем если бы вы вручную настраивали его с большими усилиями.
Есть доказательства; кластеров может быть много, поскольку предполагается, что межкластерные коммуникации редки. Однако внутри каждый кластер может эффективно использовать гораздо меньшее количество ALU, поскольку внутрикластерная связь является обычным явлением и, следовательно, должна быть высокоэффективной.
Чтобы эти ALU были загружены данными, каждый ALU снабжен файлами локальных регистров (LRF), которые в основном являются его используемыми регистрами.
Этот трехуровневый шаблон доступа к данным позволяет легко хранить временные данные вдали от медленной памяти, что делает кремниевую реализацию высокоэффективной и энергосберегающей.
Хотя разумно ожидать ускорения на порядок (даже от обычных графических процессоров при вычислениях в потоковом режиме), не все приложения выигрывают от этого. Задержки связи на самом деле являются самой большой проблемой. Хотя PCI Express улучшил это с помощью полнодуплексной связи, для работы графического процессора (и, возможно, общего потокового процессора), возможно, потребуется много времени. Это означает, что использовать их для небольших наборов данных обычно непродуктивно. Поскольку смена ядра - довольно дорогостоящая операция, потоковая архитектура также влечет за собой штрафы за небольшие потоки, поведение, называемое эффектом короткого потока.
Конвейерная обработка - это очень распространенная и широко используемая практика на потоковых процессорах, причем графические процессоры имеют конвейеры, превышающие 200 этапов. Стоимость переключения настроек зависит от изменяемых настроек, но теперь считается, что это всегда дорого. Чтобы избежать этих проблем на различных уровнях конвейера, были развернуты многие методы, такие как «сверхшейдеры» и «атласы текстур». Эти методы ориентированы на игры из-за природы графических процессоров, но концепции также интересны для общей потоковой обработки.
Большинство языков программирования для потоковых процессоров начинаются с Java, C или C ++ и добавляют расширения, которые предоставляют конкретные инструкции, позволяющие разработчикам приложений помечать ядра и / или потоки. Это также относится к большинству языков затенения, которые в определенной степени можно считать языками потокового программирования.
Некоммерческие примеры языков потокового программирования включают:
Коммерческие реализации либо общего назначения, либо привязаны к конкретному оборудованию поставщиком. Примеры языков общего назначения включают:
Языки, зависящие от поставщика, включают:
Обработка на основе событий
Пакетная обработка на основе файлов (имитирует некоторую реальную потоковую обработку, но в целом гораздо более низкая производительность)
Непрерывная обработка потока оператора
Услуги потоковой обработки:
