Процессоры для потоковых данных

Символами нового времени становятся Интернет вещей, взаимодействие машин (Machine-to-Machine, M2M), киберфизические системы, многочисленные формы цифрового искусства, геоинформационные системы, аналитика во всех ее видах и многое другое. Миллиарды устройств по всему миру генерируют, собирают и распределяют огромное количество данных в режиме 24x7 — мы становимся свидетелями такого невиданного прежде явления, как конвергенция цифрового и физического миров. Основным средством, обеспечивающим соприкосновение этих миров, станут, конечно, компьютеры, но не те, какими они были на протяжении предшествующих семидесяти лет; теперь их главная способность будет состоять в возможности справляться с большими потоками поступающих из внешней среды данных.

Какими будут эти компьютеры? Для решения проблем, порожденных конвергенцией миров, на компьютеры из Top500 надежды нет. Одна из возможных альтернатив — Data-Intensive Computing (DIC) [1], которые отличаются такими качествами, как связь с окружающей средой и работа в ее контексте. Поэтому DIC еще называют Context-Aware Computing (CAC) [2], имея в виду способность компьютеров воспринимать извне большие объемы данных, поступающих по сетям и от разнообразных датчиков. К компьютерам, поддерживающим CAC, предъявляется ряд требований, среди которых способность обрабатывать в параллельном режиме большие потоки входных данных и энергетическая эффективность.

А на каких процессорах можно построить такие компьютеры? На данный момент одним из важнейших компонентов процессорной базы систем DIC могут стать графические процессоры. Благодаря прибыльности индустрии развлечений, за более чем тридцатилетнюю историю они прошли путь от простых графических ускорителей до полноценных потоковых процессоров, сменив векторные процессоры, более 40 лет использовавшиеся в высокопроизводительных системах.

Векторные процессоры

Пока компьютеры использовались для счета и относительно простых действий над данными, отрасли удавалось сохранять верность архитектуре Джона фон Неймана, мирясь с ее главным недостатком — узким местом в виде шины данных, объединяющей память, процессор и ввод-вывод. Архитектура один поток команд, один поток данных (Single Instruction Single Data, SISD) предполагает, что одна и та же память используется для данных и для программ — в шине оба потока пересекаются, и возникает «бутылочное горло». На протяжении десятилетий было предпринято множество попыток так или иначе его расширить, но всему есть предел — существующие процессоры не могут справиться с большими потоками данных, и необходим переход на архитектуру один поток команд, множество потоков данных (Single Instruction Multiple Data, SIMD).

Идея о возможности обработки одной командой более чем одного машинного слова далеко не нова — еще в 60-е годы компанией Westinghouse был начат проект Solomon, переросший в ILLIAC IV, в котором предполагалось 256 арифметико-логических устройств, хотя реально было 64. В 70-е годы Сеймур Крей сначала в CDC, а затем в собственной компании создавал векторные суперкомпьютеры, такие как Thinking Machines CM-2, которая могла за один такт умножать 64 тыс. пар чисел. В СССР под руководством Михаила Карцева примерно в то же время создавались машины М-9 и М-10 с векторной архитектурой, способные конкурировать, например, с CDC-7600. Попытка Intel вывести на рынок SIMD-процессор Intel i860 оказалась неудачной — процессор явно опередил время. В дальнейшем элементы SIMD появились в системах векторных команд ряда популярных процессоров: VIS в UltraSPARC I, MDMX в MIPS, MMX/SSE в x86 и AltiVec в PowerPC. При объединении в кластеры машин на базе многоядерных процессоров образуются системы класса много потоков команд, много потоков данных (Multiple Instruction Multiple Data, MIMD), и любой современный настольный компьютер попадает в категорию машин MIMD, способных выполнять команды типа SIMD над короткими векторами.

Отдельную страницу истории занимают транспьютеры. В 80-е годы под руководством Тони Хоара была разработана теория ускоренных параллельных вычислений на базе приборов, способных быстро обмениваться данными и производить вычисления (само слово transpute образовано от transmit и compute). Для поддержки транспьютеров были разработаны язык Occam и операционные системы Minix и Idris. Привлекшая к себе на короткий момент широкое общественное внимание, транспьютерная инициатива сошла на нет по экономическим причинам: рентабельное производство полупроводниковых приборов не может быть мелкосерийным. Кроме этого, были и сугубо технические причины: низкая эффективность последовательного обмена данными и сложность программирования транспьютеров.

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

Стоит отдельно отметить терминологическую коллизию — архитектуру SIMD не следует путать с одновременной многопоточностью (simultaneous multithreading), реализованной в большинстве современных CPU [3]. В первом случае речь идет о множестве потоков данных, а во втором — о разбиении потока команд на несколько меньших по мощности потоков.

Потоковые процессоры и GPU

Следующим шагом в развитии идеи SIMD стали потоковые мультипроцессоры (Streaming Multiprocessor, SM), в которых имеются массивы, состоящие из отдельных процессорных устройств, каждое со своим набором регистров размером с машинное слово — все процессоры автономны, но работают синхронно, выполняя одну и ту же команду над различным содержимым регистров [4].

Рис. 1. Потоковый процессор

Потоковые мультипроцессоры (рис. 1) были разработаны в Стэнфордском университете исключительно для медийных приложений, а исследования финансировались агентством DARPA. Сразу после первых публикаций в судьбе SM произошел поворот — обнаружилось их новое применение в графических процессорах (Graphicsl Processing Unit, GPU), используемых для игр, хотя в первых публикациях разработчики вообще не упоминали игры как потенциальные сферы приложений.

Первые потоковые GPU на основе SM, Nvidia GeForce 8 и ATI FireStream, переименованного в AMD Stream Processor, вышли на рынок в 2006 году. Сначала появилась возможность создавать программируемые GPU, давшие заметный импульс игровой индустрии и, как следствие, большие прибыли, что открыло возможности для быстрого развития GPU — удвоение их производительности происходит сейчас каждые полгода. Вскоре открылась перспектива применения GPU и для вычислений, это дало жизнь новому направлению, известному как графические процессоры универсального назначения (General-Purpose Graphics Processing Unit, GPGPU).

Основы SM

Функционирование SM основывается на двух «слонах»: локализация (locality), или привязка к вычислительным узлам (к программным операциям), и согласованный между узлами параллелизм действия (concurrency). Локализация и параллелизм воплощены в программной модели потока (Stream Programming Model, SPM), а сама SPM строится на разделении приложений на две составляющие: на потоки — записи из данных одного типа (числа и более сложные структуры) и ядра — операции, выполняемые над входными потоками. SPM работает на процессоре предельно упрощенной архитектуры (рис. 2), который отличается от традиционного CPU наличием набора регистров для потоков данных (Stream Register File, SRF) и устройства для исполнения ядер (Kernel Execution Unit, KEU). В архитектуре SM локализация и параллелизм поддерживаются непосредственно на уровне набора команд, а SRF служит средством коммуникации между потоками KEU и памятью.

Рис. 2. Архитектура потокового процессора

Процессор приложений (Application Processor) имеет собственный набор команд, архитектурно напоминает RISC и служит для управления прохождением потоков — для этого имеются интерфейсы с SRF, KEU и памятью. Команды, обращенные к памяти, позволяют загрузить (load_stream) и сохранить (store_stream) поток, а обращенные к KEU — загрузить ядро (load_kernel) и выполнить ядро (run_kernel). После того как ядро загружено, KEU обрабатывает поток с использованием своего собственного набора команд. Этот набор команд тоже аналогичен RISC, но управляет только функциональностью, которая находится внутри KEU.

Над потоками могут быть выполнены следующие типы операций:

• Map-Apply («отобразить и применить») — применяется ко всем элементам потока;
• Gather and Scatter («собрать и распределить») — применяется к адресуемой с помощью вектора части потока;
• Reduce («сократить») — выделение потока меньшей мощности из большего по размерам потока;
• Filter («фильтровать») — выделение части потока по какому-то признаку;
• Sort («сортировать») — превращение потока в упорядоченный набор данных;
• Search («искать») — выделение определенных элементов потока.

В SPM есть два типа локальности: ядерная (kernel locality) и локализация связи между источником и получателем данных (producer-consumer locality). Локальность — ключ к желаемому параллелизму. При ядерной локализации ссылки на переменные ограничены только ядром, за исключением чтения входного потока и записи в выходной поток. Локализация связи распространяется на обмен данными между ядрами — для того чтобы SM мог работать, необходимо, чтобы поток, порожденный ядром-поставщиком, был немедленно поглощен ядром-потребителем. Исполнение локализовано в ядрах, а передача потоков осуществляется через связи между парами ядер. Наличие локализации гарантирует три типа коммуникаций: местные — скалярные внутри ядра; потоковые — между ядрами; глобальные — обмен с устройствами ввода-вывода.

Описанные подходы к локализации данных и их обработке открывают возможности для нескольких типов параллелизма:

• на уровне команд (Instruction Level Parallelism): параллельное выполнение скалярных операций в ядре;
• параллелизм данных (Data Parallelism): одни и те же шаблоны вычислений применяются параллельно к различным элементам потоков;
• параллелизм задач (Task Parallelism): традиционное распараллеливание вычислений.

Первым SM был медийный процессор Imagine Media Processor, разработанный в Стэнфорде и изготовленный компанией Texas Instruments в 2001 году. В Imagine было восемь KEU, собранных в кластер, работающий в режиме SIMD. Каждый из KEU состоит из шести устройств для выполнения операций с плавающей точкой, в их числе три сумматора, два устройства умножения и одно — для деления и извлечения квадратного корня. В отличие от идеальной схемы (рис. 2), в нем нет встроенного процессора приложений — Imagine был задуман как сопроцессор. При такой схеме за выполнение скалярных команд отвечает хост-процессор, а потоковые команды передаются через потоковый контроллер в Imagine. Все входные и выходные потоки передаются через SRF.

Система программирования для Imagine Media Processor состоит из двух Cи-подобных языков KernelC и StreamC, каждый из них имеет свой собственный компилятор. Таким образом обеспечивается управление исполнением и управление потоками данных. Ядро, написанное на KernelC, оперирует содержимым потоков, образованным вычислительным циклом с итерацией, обрабатывающим входной поток и создающим выходной поток. Управляющая потоками программа пишется на StreamC. Однако система программирования из двух связанных языков программирования не может быть жизнеспособной, поэтому в Лаборатории машинной графики Стэнфордского университета в 2003 году был разработан язык BrookGPU, ставший родоначальником современных потоковых языков программирования. Под влиянием Imagine были созданы экспериментальные компьютеры Merrimac и 64-битный FT64. Особо стоит отметить IBM Cell, в котором внутренний кластер собран из полноценных CPU, что позволяет им обрабатывать разные потоки.

В результате коммерциализации проекта Imagine в 2007 году была создана компания Stream Processors, выпустившая семейство процессоров Storm-1, рассчитанное на системы для обработки цифровых сигналов (Digital Signal Processing, DSP). И примерно тогда же началось постепенное заимствование идей потоковой обработки двумя основными производителями GPU, компаниями AMD и Nvidia.

GPGPU и гетерогенность

С появлением шестого и седьмого поколений GPU произошла полная конвергенция потоковых и графических процессоров (показательно, что ведущий разработчик графического процессора Imagine, профессор Стэнфордского университета Уильям Далли занял пост главного ученого Nvidia) в объединенное направление универсальных вычислений на графических процессорах.

Успех GPU на поле универсальных вычислений оказал серьезное влияние на гетерогенные системы, состоящие из более чем одного типа процессоров — к CPU добавляют графические процессоры, сигнальные процессоры DSP, программируемые логические матрицы FPGA, процессоры с фиксированными функциями, например видеодекодеры и еще какие-либо ускорители.

Еще совсем недавно одинаковые шансы на признание были у двух разных гетерогенных систем — наиболее перспективными казались асимметричные мультипроцессоры (Asymmetric Multiprocessing, AMP) и FPGA. Самым ярким образцом AMP был процессор Cell, разработанный альянсом Sony, Toshiba и IBM. Проект стартовал в марте 2001 года и обошелся почти в полмиллиарда долларов, а в 2009 году, когда стала ясна бесперспективность 32-разрядных процессоров, работы над начальной версией Cell приостановились, хотя IBM утверждает, что на уровне исследований они продолжаются. FPGA задумывались как платформа для специальных процессоров, но с появлением межпроцессорных соединений QuickPath Interconnect и Hyper-Transport стало возможным использовать FPGA в качестве ускорителей для процессоров x86-архитектуры. Сегодня FPGA занимают определенную нишу с монопольным положением Xilinx и Altera, а еще пять-шесть компаний сосредоточены на производстве специализированных массивов. После 2010 года все внимание в сфере гетерогенных процессоров сосредоточилось исключительно на GPU.

Сегодня гетерогенность становится одним из важнейших направлений развития индустрии. Важно подчеркнуть, что гетерогенность не достигается формальным суммированием в одной установке сотен ядер CPU с тысячами ядер GPU, как это делается в суперкомпьютерах типа Tianhe-2, — каким бы большим ни был суперкластер, он остается группой машин, связанных между собой, но при этом работающих по классической схеме SISD. Гетерогенные компьютеры отличаются от кластеров тем, что все их процессоры должны иметь доступ к унифицированной общей памяти. Однако при решении этой задачи возникают сложности, поскольку принципы, по которым организован доступ к памяти CPU и GPU, радикально различаются. В первых компьютерах арифметико-логическое устройство общалось непосредственно с памятью, содержимое ячеек загружалось в регистры и обратно, в 70-е годы возникла идея кэш-памяти, которая расширялась, и в современных CPU применяются многоуровневые кэши, обеспечивающие эффективное использование тракта CPU — память. GPU умеют работать с ограниченным объемом данных, предварительно загруженных в локальную графическую память процессора. Сегодня используются два подхода к унификации памяти для GPGPU — Nvidia в CUDA 6 предлагает программное решение, а AMD применяет аппаратное решение hUMA (heterogeneous Uniform Memory Access).

***

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

Литература

1. Дмитрий Волков, Александр Фролов. Оценка быстродействия нерегулярного доступа к памяти // Открытые системы.СУБД. — 2008. — № 1. — С. 15–19. URL: http://www.osp.ru/os/2008/01/4836914 (дата обращения 22.05.2014).
2. Леонид Черняк. Вперед, к контексту // Открытые системы.СУБД. — 2012. — № 3. — С. 43–45. URL:http://www.osp.ru/os/2012/03/13015158 (дата обращения 22.05.2014).
3. Михаил Кузьминский. Многонитевая архитектура микропроцессоров // Открытые системы.СУБД. — 2002. — № 1. — С. 22–26. URL: http://www.osp.ru/os/2002/01/180943 (дата обращения 22.05.2014).
4. Михаил Кузьминский. GPU для HPC — время пришло // Открытые системы.СУБД. — 2011. — № 6. — С. 12–15. URL: http://www.osp.ru/os/2011/06/13009975 (дата обращения 22.05.2014).

Леонид Черняк (osmag@osp.ru) — научный редактор, «Открытые системы. СУБД» (Москва).