Использование технологии SIMD-R (ОКМД-в-регистре)

Технологии "ОКМД-в-регистре", такие как Intel MMX, Intel SSE/SSE2, AMD 3DNow!, SPARC VIS ISA, Digital Alpha AltiVed включают в себя набор расширений к архитектурам Intel, AMD, SPARC, Aplha, которые разработаны, чтобы увеличить производительность средств мультимедиа и коммуникаций.

Эти расширения (которые включают новые регистры, типы данных, и инструкции) объединены с моделью выполнения "одна инструкция, много данных" (ОКМД), и призваны ускорить выполнение приложений типа: подвижное видео, комбинированую графику с видео, обработкой изображений, звуковым синтезом, синтезом речи и сжатием, телефонией, видео конференц-связью, и 2D и 3D графикой, которые типично используют алгоритмы с интенсивными вычислениями, чтобы исполнять повторяющиеся действия на больших множествах простых элементов данных.

Основной причиной, побудившей производителей включать в свои изделия расширения системы команд ОКМД-Р, были свойства мультимедийных алгоритмов:

• Обычно большой объём данных;
• Большинство операций производится над целыми числами малой длины:
• 8-битовые значения цвета пикселей;
• 16-битовые аудио-отсчёты;
• Наличие параллелизма в задачах (класса ОКМД);

Основная цель введения команд класса "ОКМД-в-регистре"

Технология обеспечивает модель выполнения команд класса ОКМД - одна команда обрабатывает много данных. В классической интерпретации одинаковые вычислители выполняют одну и ту же операцию над разными элементами данных, сокращая общее время выполнения программы.

Рассмотрим пример цифрового фильтра порядка 512:

512
\---
 \ h(i)*x(512-i)
 /
/---
i=1

В процессе вычисления мы должны сложить 512 значений, которые получаются путём перемножения последовательно расположенных в памяти элементов массива. Операцию можно сделать быстрее в 4 раза, если вычислять 4 суммы 128 элементов, но независимые вычислители должны выбирать данные с шагом 4 элемента. С другой стороны, выборка данных производится последовательно (независимо в сторону увеличения или уменьшения адресов), поэтому процессор может одновременно выполнять несколько умножений по схеме ОКМД, как это показано на рисунке 1.

Рис. 1. Выполнение операции фильтрации по схеме ОКМД.

При размещении четырёх последовательных элементов в одном регистре (возможно очень широком) решается проблема их одновременной загрузки (только увеличивается ширина шины данных в кеш-память). При выполнении нескольких операций умножения одновременно над частями регистра можно добится, чтобы операция выполнялась в несколько раз быстрее. Действительно, на этой операции (запрограммированной на поддерживающем технологию "ОКМД-в-регистре" процессоре цифровой обработке сигналов ADSP TigerSHRC) быстродействие повышается в 4 раза.

Таким образом, на части алгоритмов использование ОКМД-в-регистре значительно повышает быстродействие. Однако, алгоритм должен быть в форме, которая допускает применение этой технологии, что является важным фактором пи использовании технологии.

Отметим, что использование технологии "ОКМД-в-регистре" не является панацеей при программировании алгоритмов. Использование длинного командного слова в сочетании с программным конвейером часто позволяет достичь такой же производительности на алгоритмах, для которых неприменимо ОКМД-в-регистре.

Вывод: перед попыткой использования этой технологии необходимо рассмотреть возможность записи алгоритма в форме, допускающей применение команд типа "ОКМД-в-регистре".

Рассмотрим реализацию этой технологии в современных процессорах.

Реализация технологии "ОКМД-в-регистре" в современных микропроцессорах.

Рассмотрим реализацию технологии в процессорах фирмы Интел.

Изначально реализация технологии не была слишком удачной. Первая появившаяся в Pentium-MMX технология увеличивала производительность обработк и целых чисел. Однако применение ёё на ряде задач было достаточно сложным, и накладные расходы на упаковку и распаковку данных в 64-разрядные регистры в ряде случаев сводили на нет преимущества технологии в скорости. Появление SSE в Pentium-III с поддержкой обработки плавающей запятой значительно улучшило ситуацию, и технология стала удобным и действенным средством повышения производительности вычислений. Рассмотрим особенности технологий MMX, SSE, SSE2 в таблице.

Технологии ОКМД-в-регистре фирмы Intel

Некоторые дополнительные сведения по архитектуре ОКМД-в-регистре.

Технология ОКМД-в-регистре: сумма сумм

Базовой концепцией ОКМД-Р является, то что операции на значениях длиной в слово или полуслово, могут быть ускорены при применении ОКМД-операций на n-ом количестве значений шириной k/n бит. Однако, некоторые ОКМД-Р операции имеют большую стоимость выполнения, чем их скалярные аналоги, поскольку требуют накладных расходов на пересылку и создание серий значений в ОКМД-Р регистрах.

Проиллюстрируем этот механизм, рассмотрим упрощенный ОКМД-Р механизм, оперирующий 8-битовыми полями в 32-битовом регистре. Значения в регистрах могут быть обозначены как:

Каждый регистр рассматривается как массив из четырёх независимых значений

Рассмотрим осоновные классы ОКМД-Р операций над векторами и реализацию некоторых функций.

Полиморфные операции

Некоторые ОКМД-операции могут быть исполнены используя обычные 32-битные целые числа, не обращая внимания на то, что реальный регистр не разделен на поля. Назовём эти операции полиморфными, так как они не зависят от конкретной конфигурации полей в регистре.

Полиморфно тестирование полей на нуль, все булевы операции полиморфны. Например, булево "И" полиморфно, при его выполнении мы получаем:

Естественно, полиморфны операции, которые осуществляются поразрядно независимо.

Раздельные операции

Большинство ОКМД-Р операций неполиморфны. Арифметические операции сложения, вычитания, умножения и деления используют заём/перенос из соседних полей. Для проведения таких операций регистры должны быть разделены для предотвращения заёмов и переносов.

Существуют 3 метода осуществления разделения регистров.

Раздельные инструкции

Наиболее эффективный метод - аппаратное разделение на регистров на поля с помощью аппаратной логики, не допускающей переносов. Способ предполагает наибольшее быстродействие, но предполагает введение в процессор новых ОКМД-Р команд, и в принципе позволяет лишь ограниченные конфигурации разделения полей (например, невозможны 12-битные поля, зато есть 8 и 16 бит.) AMD/Cyrix/Intel MMX, Digital MAX, HP MAX, и Sun VIS реализуют ограниченные версии раздельных инструкций. Однако, разные множества инструкций и разные ограничения на разных процессорах создают ограничения по переносимости. Например, рассмотрим различные реализации ОКМД-Р:

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

Неразделённые операции с коррекцией.

Рассмотрим случай, когда раздельные операции не поддержаны процессором. В этом случае необходимо предусмотреть невозможность заёма или переноса при выполнении операций над обычными регистрами.

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

Первый вопрос: насколько неэффективна такая реализация (симуляция ОКМД-Р)?

Рассмотрим реализацию сложения четырёхэлементного массива 8-битовых чисел, используя обычные 32-битные операции.

Едиснтвенной проблемой является перенос, и задачей является недопущение переноса из старшего разряда числа. Поэтому просто обнуляет старший бит каждого байта в регистре путем "логического И" операнда и константы 0x7f7f7f7f и затем следует простое 32-разрядное сложение:

t = ((x & 0x7f7f7f7f) + (y & 0x7f7f7f7f));

Результат вполне корректен - кроме самых значащих битов каждого поля. Расчёт корректных значений прост - необходимо 2 однобитных раздельных сложения наиболее значащих битов из x и y с результатом переноса из седьмых разрядов рассчитанного значения t. Отметим, 1-битное раздельное сложение реализуется просто с помощью операции "исключающее ИЛИ", поэтому результат просто равен

(t ^ ((x ^ y) & 0x80808080))

Итак, для 4-х сложений понадобилось 6 операций, хотя количество этих операций не зависит от числа полей, при большем числе полей увеличение скорости налицо. С другой стороны результат налицо хотя бы в уменьшенном количестве загрузок чисел.

Контроль значений полей

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

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

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

Предположим, что 8-битовые поля из предыдущего примера стали 7-битовыми с 1-битовыми промежутками для битов переноса/заёма.

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

((x + y) & 0x7f7f7f7f)

Для четырёх сложений использованы 2 инструкции. Отметим, что обнуление этих битов не работает на операциях вычитания. В этом случае коррекция тоже проста - для операции x-y начальное состояние промежуточных битов должно быть "1" в x и "0" в y. В общем случае операция выглядит как:

(((x | 0x80808080) - y) & 0x7f7f7f7f)

Естественно, использовать для ОКМД-Р операций можно любой метод из предложенных, в зависимости от условий задачи и прироста быстродействия.

Связи и операции преобразования операндов

В некоторых случая ОКМД-Р вычислений i-е значения векторов-результатов зависят не только от i-х позиций векторов-операндов. Например, такие операции как сглаживание пискелов и быстрое преобразование Фурье требуют не только параллеьных, но и сложных локальных связей.

Нетрудно организовать перемещение данных с помощью нераздельной операции сдвига. Например для пересылки значения из PE(i) в PE(i+1), можно использовать сдвиг. Если поля имеют в ширину 8 бит, можно использовать:

(x << 8)

Однако не всё так просто. Передвижка из PE(i) to PE(i-1) несколько сложнее, из-за распространения (обычно) знакового бита. Поэтому в общем случае, мы должны очистить расширенный знак:

((x >> 8) & 0x00ffffff)

Добавление "циклический перенос" может быть сделано эффективно, используя неразделённые сдвиги. Например, перемещение из PE(i) в PE(i+1) с циклическим сдвигом:

((x << 8) | ((x >> 24) & 0x000000ff))

Проблемы возникают скорее, если требуются более сложные случае перемещения. Только система команд HP MAX поддерживает сложные перестроения полей с помощью одной инструкции, называемой Permute. Она может не только перестраивать поля, но и делать перестроения несколько раз. Вкратце - она реализует произвольную операцию x[y].

К сожалению, реализация x[y] очень сложна без специализированных инструкций. Фрагмент кода обычно длинный и неэффективный. Относительно высокое быстродействие инструкций x[y] на машинам MasPar MP1/MP2 и Thinking Machines CM1/CM2/CM200 ОКМД-суперкомпьютерах было ключевым фактором быстродействие ОКМД-вычислений. Хотя x[y] всегда более медленна, чем операция получения соседнего элемента, множество алгоритмов разрабатывалось с целью меньшего использования операции x[y]. В общем, без аппаратной поддержки лучше всего разрабатывать ОКМД-Р программы, руководствуясь тем, что команды x[y] не существует, либо её исполнение дорого стоит (по времени).

Рекуррентные операции (редукции)

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

Наиболее общий класс распараллеливаемых рекуррентных соотношений - это класс ассоциативных редукций. Например, рассчитаем сумму значений массива, дан код на языке Си:

t = 0;
for (i=0; i<MAX; ++i) t += x[i];

Обычно порядок сложений важен очень нечасто (обычно в случае, если надо соблюдать требования точности). Поэтому можно переписать алгоритм в виде "дерева" параллельных сложений, где сначала мы складываем пары чисел, затем пары частичных сумм, и так пока не получим одно значение. Для вектора из 4-х 8-битовых значений нужны только 2 шага суммирования, на первом шаге делаются сложения двух пар 8-битовых значений, получая 2 16-битовых результата:

t = ((x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff));

На втором шаге эти 9-битовые значения суммируются для получения 10-битового результата:

((t + (t >> 16)) & 0x000003ff)

Реально на втором шаге производится 2 16-битовых сложения, хотя используются всего 10 бит.

Заключение

Расширения множества инструкций в каждом МП фокусированы на увеличении производительности некоторой группы мультимедийных операций. Различные архитектуры МП акселерируют коды различных приложений, нельзя сказать однозначно без знания архитектуры, за счёт чего увеличится скорость. Результатом является практическая непереносимость программ, написанных с использованием кода ОКМД-Р, между различными микропроцессорами.

Остаётся только надеяться на разработку в будущем комиляторов, которые смогут генерировать ОКМД-Р команды при рассмотрении циклов программ АВТОМАТИЧЕСКИ.