Ticker Tape - часть 2

Категории:

Скачать статью и посетить домашнюю страницу Ticker Tape

Скачать статью TickerTape Part 2 [Eng., PDF 269KB]
Домашняя страница Ticker Tape (исходный код, исполняемые файлы, видео)

Введение

Ticker Tape – это демонстрационная модель, которая может помочь разработчикам в реализации более сложного поведения систем частиц в своих приложениях. В нашей программе реализованы несколько методов, способных увеличить производительность, такие как многопоточность и оптимизация под расширения Intel® Streaming SIMD Extensions (Intel® SSE). С обзором работы можно ознакомиться по ссылке www.intel.ru/software/tickertape, оттуда также можно скачать код приложения. В данной статье мы рассмотрим, какой прирост производительности в Ticker Tape нам удалось получить, используя инструкции Intel SSE. Однако, прежде чем перейти к результатам, мы ознакомимся с приёмами программирования на SSE и рассмотрим пример расчёта скалярного произведения с использованием команд SSE.

Предварительные сведения

SSE представляет собой набор инструкций, которые предназначены для работы с архитектурой SIMD (Single Instruction Multiple Data – одна инструкция на много данных). При этом возникает возможность параллельно производить вычисления над несколькими элементами, что даёт некоторую форму параллелизма данных. Иногда такую форму называют векторной обработкой. Например, допустим, что у нас есть два массива чисел, которые мы хотим перемножить.

 

float a[nElements], b[nElements], c[nElements];

for (unsigned int i = 0; i < nElements; i++) {
    c[i] = a[i] * b[i];
}
Листинг 1 - Скалярный метод умножения двух массивов – по одному элементу за итерацию

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

MultiplyFourElements().

float a[nElements], b[nElements], c[nElements];

void MultiplyFourElements(float *a, float *b, float *c) {
    c[0] = a[0] * b[0];
    c[1] = a[1] * b[1];
    c[2] = a[2] * b[2];
    c[3] = a[3] * b[3];
}

for (unsigned int i = 0; i < nElements; i += 4) {
    MultiplyFourElements(&a[i], &b[i], &c[i]);
}
Листинг 2 - Скалярный метод умножения двух массивов – по четыре элемента за итерацию

В листинге 2 приведена функция, которая обрабатывает по четыре элемента за раз. Это даёт нам возможность использовать в четыре раза меньше итераций. С точки зрения эффективности мы почти ничего не выиграли, поскольку выполняются все те же самые математические операции. И здесь в дело вступают инструкции SSE. Вместо функции, которая последовательно выполняет четыре умножения, мы используем одну инструкцию, которая может выполнять одновременно четыре операции умножения. В командах SSE используются специальные регистры процессора, которые имеют разрядность 128 бит. Эти регистры могут содержать данные любого типа, которые вмещаются в 128 разрядов, например, два значения с плавающей точкой двойной точности или четыре одинарной точности. Существует два способа программировать с помощью SSE: можно напрямую вставлять ассемблерные инструкции, а можно использовать встроенные функции (intrinsics). В Ticker Tape и в данной статье мы будем рассматривать и использовать только встроенные функции. Их использование вместо инструкций ассемблера более наглядно и лучше подходит к стилю программирования на С/С++. Использование встроенных функций, как мы увидим, также позволяет компилятору более эффективно оптимизировать код.

// Assembly SSE Instruction
/// xmm0 and xmm1 are actual registers, not variables
mulps xmm0,xmm1

// Intrinsic SSE Instruction
__m128 a, b, c;
c = _mm_mul_ps(a, b);
Листинг 3 - Инструкции ассемблера и встроенные функции SSE

Тип __m128 объявляет выровненную по 16-ти байтам переменную, которая соответствует одному из регистров SIMD. Программа должна сначала явно загрузить данные в регистры SIMD, что и выполняется с помощью встроенной функции _mm_load_ps() (не показана на листинге 3). Сами вычисления выполняются функцией _mm_mul_ps() Полученные результаты сохраняются в массив функцией _mm_store_ps().

#include 

float a[nElements], b[nElements], c[nElements];
__m128 A, B, C;

//... load data in a, b

for (unsigned int i = 0; i < nElements; i += 4) {
    A = _mm_load_ps(&a[i]);
    B = _mm_load_ps(&b[i]);
    C = _mm_mul_ps(A, B);
    _mm_store_ps(&c[i], C);
}
Листинг 4 -Метод SIMD перемножения двух массивов

На рис. 1 показана разница в операциях:


Рис. 1 - Сравнение скалярных и SIMD операций


Расположение данных

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

class foo {
    float a;
    float b;
    ... other data ...
};

void bar() {
    foo fooArray[nElements];
    float c[nElements];
    __m128 A, B, C;

    // Non_SIMD Method
    for (unsigned int i = 0; i < nElements; i++) {
        c[i] = fooArray[i].a * fooArray[i].b;
    }

    // SIMD Method
    for (unsigned int i = 0; i < nElements; i += 4) {
        A = _mm_load_ps(&fooArray[i].a); // What will this do?
        B = _mm_load_ps(&fooArray[i].b); // Load incorrect data
        C = _mm_mul_ps(A, B);
        _mm_store_ps(&c[i], C);
    }
}
Листинг 5 - Класс со структурой данных, плохо подходящий для SIMD операций (массив структур)

В листинге 5 показано, как могут выглядеть неправильно расположенные данные. Код пытается загрузить в регистр SIMD непрерывный фрагмент памяти, получая при этом данные в неправильном формате. Не то, чтобы данные невозможно было загрузить, но для получения нужного формата необходимо выполнить ряд дополнительных действий по их перегруппировке. Неважно, сколько дополнительных вычислений для этого требуется, но при этом копируются лишние данные и, возможно, придется выгрузить в память дополнительные линии кэша. Несмотря на это, даже при всей дополнительной нагрузке, использование инструкций SSE может сказаться очень благотворно, особенно если над одними и теми же данными производится много разных операций. Альтернативной структурой может быть последовательное расположение однотипных элементов данных, чтобы их можно было эффективно загружать и сохранять. Дополнительным плюсом такого подхода является то, что при увеличении размеров SIMD регистров гораздо легче адаптировать код: нужно всего лишь загружать по восемь чисел с плавающей точкой за раз вместо четырёх. Наш пример, работающий с новым, более эффективным расположением данных, будет выглядеть так:

class foo {
    float *a;
    float *b;
    ... other data ...
};

foo::foo(unsigned int nElements) {
    a = (float *)_mm_malloc(nElements * sizeof(float), 16);
    b = (float *)_mm_malloc(nElements * sizeof(float), 16);
}

void bar() {
    foo fooVariable(nElements);
    float c[nElements];
    __m128 A, B, C;

    // Non_SIMD Method
    for (unsigned int i = 0; i < nElements; i++) {
        c[i] = fooVariable.a[i] * fooVariable.b[i];
    }

    // SIMD Method
    for (unsigned int i = 0; i < nElements; i += 4) {
        A = _mm_load_ps(&fooVariable.a[i]);
        B = _mm_load_ps(&fooVariable.b[i]);
        C = _mm_mul_ps(A, B);
        _mm_store_ps(&c[i], C);
    }
}

Листинг 6 - Класс с расположением данных, более дружественным SIMD (структура массивов)


Рис. 2 - Расположение данных в виде структуры массивов и массива структур


SIMD-оптимизация в Ticker Tape

Оптимизация Ticker Tape под использование команд SIMD состояла из двух стадий – перегруппировки данных для более эффективной работы инструкций SIMD и переделки кода под сами инструкции. При профилировании программы мы обнаружили, что основное время расходовалось в функции Newton(). Эта функция рассчитывает, как разные силы воздействуют на частицы. В оригинальном исполнении она вызывалась по одному разу на каждую частицу и выполняла вычисления четыре раза ¬– по разу на каждый угол частицы. Структура программы при этом выглядела примерно так:

 

class RigidBody
{
    void Newton();
    // ... Bunch more functions ...

    D3DXVECTOR3 Position;
    D3DXVECTOR3 Rotation;

    // ... Lots of other data ...
};

void RigidBody::Newton()
{
    for (unsigned int = 0; i < 4; i++)
    {
        // ... some math goes on ...

        // Velocity_Ground 
        D3DXVECTOR3 Vel_Ang_CM_global;
        D3DXVec3TransformCoord(&Vel_Ang_CM_global, 
            &Velocity_Angular_CM, &this->LocalGlobal);
        D3DXVec3Cross(&tmp, &Radial_Vec, &(Vel_Ang_CM_global));
        Velocity_Ground = (this->Velocity_Linear_CM) + tmp;

        // ... more math ...
    }

    return;
}
Листинг 7 - Оригинальная реализация Ticker Tape

Каждая частица была реализована как отдельный объект, который содержал методы манипуляции частицей. Существовал цикл, который пробегал по всем частицам, вызывая их управляющие методы. При переходе к SSE первым делом была создана новая функция NewtonArray()– аналог функции Newton(). Она делала ровно то же самое, что и оригинал, но вместо одной частицы брала сразу весь массив частиц. Тогда же мы создали класс RigidBody, который мог содержать целые массивы данных. Таким образом, в программе вместо массива объектов RigidBody появился один объект RigidBody, который сам содержал целые массивы данных. На основе тестирования разных структур данных, данные были ещё дополнительно разбиты на составляющие компоненты (см. листинг 8).

// Original
D3DXVECTOR3 rotation;

// Half way
D3DXVECTOR3 *rotation;

// Final
float *rotationX;
float *rotationY;
float *rotationZ;
Листинг 8 - Изменение расположения данных


После реорганизации данных, код функции NewtonArray() был изменён с применением SSE инструкций. Основной предпосылкой вносимых изменений было желание убрать вложенный цикл. Каждая переменная с индексом внутреннего цикла загружалась в SIMD регистр обычным образом, а каждая переменная с индексом внешнего цикла дублировалась в регистрах. В первую очередь мы удалили внутренний цикл (листинг 9). Инструкция _mm_set1_ps() похожа на инструкцию _mm_load_ps() за исключением того, что она загружает одно значение с плавающей точкой и копирует его во все четыре секции регистра.

// Original code example
for (unsigned int i = 0; i < nParticles; i++) {
    for (unsigned int j = 0; j < 4; j++) {
        c = a[i] * b[j]; // Notice the different indexers
    }
}

// SSE version, inner loop removed
for (unsigned int i = 0; i < nParticles; i++) {
    A = _mm_set1_ps(&a[i]);  // copy the value a[i] into all 4 slots
    B = _mm_load_ps(&b[i * 4]);
    C = _mm_mul_ps(A, B);
    _mm_store_ps(&c[i], C);
}
Листинг 9 - Удаляем внутренний цикл


Выгода от оптимизации проявилась сразу, когда была изменена лишь малая часть функции. Когда же вся оптимизация была завершена, мы сделали замеры работы функции NewtonArray()(). Используя компилятор Microsoft (MSVCC) с Visual Studio 2008, мы обнаружили увеличение скорости в 1,8 раза. Использование компилятора Intel® C++ (ICC) показало практически те же результаты на оригинальном коде благодаря встроенной поддержке автоматической векторизации. Использование ICC с переделанным под SSE кодом показало гигантское ускорение в 4,5 раза.


Компилятор

MSVCC

MSVCC + SSE

ICC

ICC + SSE

Время исполнения (мс):

16.3

8.9

9.9

3.6

Ускорение:

1.0x

1.8x

1.6x

4.5x

Таблица 1 - Время выполнения функции Newton в миллисекундах


Пример расчёта скалярного произведения

Здесь мы опишем пример использования инструкций SSE при вычислении скалярного произведения (реально, четырёх скалярных произведений), а также принцип работы алгоритма умножения. Все переменные имеют имена xmm#, поскольку восемь регистров SSE имеют названия xmm0 – xmm7. В принципе, называть переменные именно так не обязательно, количество переменных также может быть любым.

 

// Dot Product
// Computes dot products on two arrays of vectors, 1 at a time
for (unsigned int i = 0; i < nElements; i++) {
        result[i] = v1[i].x * v2[i].x + 
                    v1[i].y * v2[i].y + 
                    v1[i].z * v2[i].z;
}

// Dot Product
// Computes dot products on two arrays of vectors, 4 at a time
for (unsigned int i = 0; i < nElements; i += 4) {
    xmm0 = _mm_load_ps(X1 + i);     // Load data into SIMD registers
    xmm1 = _mm_load_ps(Y1 + i);
    xmm2 = _mm_load_ps(Z1 + i);

    xmm3 = _mm_load_ps(X2 + i);
    xmm4 = _mm_load_ps(Y2 + i);
    xmm5 = _mm_load_ps(Z2 + i);

    xmm6 = _mm_mul_ps(xmm0, xmm3);  // Multiply x's together
    xmm7 = _mm_mul_ps(xmm1, xmm4);  // Multiply y's together
    xmm8 = _mm_mul_ps(xmm2, xmm5);  // Multiply z's together

    xmm0 = _mm_add_ps(xmm6, xmm7);  // Add all the values together
    xmm7 = _mm_add_ps(xmm0, xmm8);

    _mm_store_ps(result + i, xmm7); // Save the results
}
Листинг 10 - SSE версия функции скалярного умножения


Первым делом с помощью инструкции _mm_load_ps() алгоритм загружает все данные в SIMD регистры. Она принимает в качестве аргумента адрес памяти, где находятся данные. Конечные буквы ps во всех инструкциях означают, что данные версии инструкций работают с числами единичной точности. Многие инструкции имеют по несколько версий, например, _mm_load_pd() загружает два числа двойной точности. Важно отметить, что данные должны быть выровнены по 16 байт. Если это не так, то необходимо использовать другую инструкцию _mm_loadu_ps(), но она работает не так быстро.

После загрузки данных производится операция умножения инструкцией _mm_mul_ps() . Эта команда перемножает соответствующие элементы двух регистров.


Рис. 3 - Графическое представление работы команды _mm_mul_ps()

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

 

Перспективы проекта

Для Ticker Tape очевидны некоторые дальнейшие действия по освоению SSE. Во-первых, нужно векторизовать весь остальной код. Можно использовать возможности нового расширения Intel® Advanced Vector Extensions (Intel® AVX). Далее, было бы интересно применить компилятор Intel® C++ с автоматической векторизацией кода. Существуют специальные конструкции кода, которые помогают компилятору проводить векторизацию. Можно применить в коде этот подход, тогда возможности SSE будут задействованы в программе, но скрытно.

 


Дополнительные ресурсы


Об авторе

Квентин Фрёмке (Quentin Froemke) является программистом в отделе Intel Visual Computing Software Division. Он помогает разработчикам игр более эффективно использовать многоядерные и другие технологии компании Интел.

 

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