SIMD

Среди моделей параллельного программирования одной из самых известных является SIMD (Single Instruction Multiple Data) – концепция, которая существует уже несколько десятилетий. Для подходящих задач она обладает гигантским потенциалом, но, к сожалению, совсем неестественной моделью программирования, которая сложна для разработки и не очень практична для промышленного применения.

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

Принципы SIMD

Главная идея SIMD заключается в том, что алгоритм (или его часть, занимающая существенно много времени) представляется в виде набора инструкций, применяющихся независимо к каждому элементу линейного однородного источника данных. Идеальное SIMD-устройство каждый такт выполняет по одной инструкции из набора для каждого элемента данных.

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

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

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

Анализ принципов SIMD и практические следствия

При использовании SIMD один и тот же код выполняется сразу для нескольких элементов данных – этим такой подход схож с параллелизмом потоков операционной системы.

Но, в отличие от традиционного подхода, параллельно исполняющиеся вычисления выполняются абсолютно синхронно, то есть за каждый такт для всех элементов данных выполняется одна и та же инструкция (это ограничение называется lockstep ). Lockstep делает модель SIMD гораздо менее гибкой, чем модель потоков ОС, ведь разные потоки ОС могут в один и тот же момент времени выполнять абсолютно разные вычисления (за что и причисляются к категории MIMD – Multiple Instructions Multiple Data).

С другой стороны, так как одна и та же программа разделена между несколькими исполняющими устройствами (вследствие принципа lockstep), то потоки предельно легковесны: в отличие от потоков операционной системы, им вообще не нужен контекст (сравните с 1 Mb (по умолчанию) стека потока для Windows XP). Соответственно, типичный сценарий использования потоков ОС содержит единицы и десятки потоков, а современные видеокарты работают с единицами и десятками тысяч потоков.

Также злой гений lockstep накладывает на SIMD-программы еще одно ограничение. Алгоритмы с расходящимся потоком управления (divergent control flow) не могут быть исполнены в lockstep и поэтому неприменимы к SIMD. Таким образом, запрещается использовать ветвления и динамическую диспетчеризацию вызовов: например, виртуальные методы. Впрочем, дальше мы увидим, что современные реализации SIMD ослабляют это ограничение изящными обходными маневрами.

SIMD-устройства содержат значительное количество однородных исполнительных модулей. Поэтому обрабатываемые каждый такт данные должны быть однородными и выравненными относительно количества и вычислительной емкости модулей. В классической SIMD-модели устройство работает только с линейно упорядоченными данными, откуда имеем два важных следствия (см. Vectorized I/O):

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

2. После окончания вычислений программист должен вручную переместить линейно упорядоченные результаты обратно в адресное пространство приложения (эта процедура называется scatter).

Аппаратные реализации SIMD

Пример реализации SIMD – набор инструкций SSE, который предоставляет несколько 128-битных регистров и ряд работающих с ними команд. SSE-команды выполняют одну и ту же операцию над несколькими элементами данных: например, ADDSS поэлементно складывает данные в двух SSE-регистрах, а CMPSS производит поэлементное сравнение. Вследствие размера регистров, превосходящего как целочисленные регистры (32 или 64 бита), так и регистры сопроцессора (80 бит), SSE обеспечивает одновременную обработку либо четырех вещественных чисел одинарной точности (32 бита), либо двух вещественных чисел двойной точности (64 бита), либо нескольких целых чисел – последних может быть от двух до шестнадцати, в зависимости от размера операндов. Соответственно, SSE – векторная реализация SIMD.

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

Применение SIMD в практических задачах

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

Однако иногда удается преобразовать алгоритм к эквивалентному виду, который уже можно выразить в терминах SIMD. Например, сложение массива чисел в наивной реализации не преобразуется к нужному виду, ибо между итерациями цикла есть write-after-write зависимость по переменной-аккумулятору. Если же мы разобьем массив на последовательные фрагменты, то каждый из этих фрагментов можно просуммировать параллельно, а получившийся массив сумм снова разбить на фрагменты и снова просуммировать, и так далее.

Естественным образом подходят для SIMD алгоритмы компьютерной графики, обработки сигналов, изображений и видео, численного решения уравнений и систем уравнений, описывающих процессы в промышленности. Также в погоне за гигантскими вычислительными мощностями, которые доступны SIMD-программам, регулярно предлагаются SIMD-версии изначально неподходящих для SIMD алгоритмов, в том числе и алгоритмов общего назначения: сортировок, сканов, редукций и т.п.

Что дальше?

В последующем посте рассмотрим stream-модель – пример data-centric подхода к SIMD, естественно вытекающего из характера многих практических данных. Также поговорим об отступлениях от классической модели, делающих ее более приспособленной к практическому применению.

Материалы для чтения по темам следующих постов

1.Stream processing, Wikipedia, the free encyclopedia.

2.Running Code at a Teraflop: Overview of GPU Architecture, SIGGRAPH 2009: Beyond Programmable Shading, Kayvon Fatahalian, Stanford University.

3. Introduction to CUDA, CUDA performance, CUDA tool chain, ARCS 2008 GPGPU and CUDA Tutorials, Simon Green, NVIDIA.

4. AMD Stream SDK: Introduction and Overview, PDC/AMD workshop on GPU programming 2008, Praveen Bhaniramka, AMD.

5. AMD Stream SDK: GPU Hardware and Performance, PDC/AMD workshop on GPU programming 2008, Praveen Bhaniramka, AMD.