Введение
В данной статье я решил привести пример оптимизации по скорости исполнения алгоритма, предназначенного для обработки видео изображения. В качестве примера, мной был выбран алгоритм медианной фильтрации. Медианная фильтрация является эффективным способом подавления шумов, которые неизбежно появляются на цифровых камерах в условиях малого освещения сцены. Алгоритм этот достаточно ресурсоемок – так например, при обработке серого изображения медианным фильтром 3х3 требуется порядка 50 операций на одну точку изображения. И если для обработки одиночных фотографий скорость в принципе не сильно важна, то при обработке видео потока скорость обработки кадра является критическим параметром при выборе алгоритма.
Для справки напоминаю суть алгоритма:
Для каждой точки исходного изображения берется некоторая окрестность (в нашем случае 3x3).
Точки данной окрестности сортируются по возрастанию яркости.
Средняя точка (5-я для фильтра 3х3) отсортированной окрестности записывается в итоговое изображение.
Для упрощения задачи я рассмотрел случай серого изображения (8 бит на точку) без учета граничных эффектов - для этого для фильтрации бралась центральная часть несколько большего изображения. Конечно, в реальных задачах граничные точки изображения следует рассчитывать по особому алгоритму, и порой реализация этих особых алгоритмов может занимать большую часть кода. Однако в плане общего времени исполнения алгоритма, эти особые точки занимают, как правило, порядка нескольких процентов, потому не интересны в контексте данного примера. Кроме того для простоты я использовал однопоточный вариант алгоритма, но эта задача в принципе может быть легко распараллелена на произвольное число потоков.
0-й вариант реализации
В этой начальной реализации задача была решена в лоб: окрестность для каждой точки исходного изображения копировалась во вспомогательный массив, который затем сортировался при помощи функции std::sort().
void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst)
{
int a[9];
for(int y = 0; y 1-я оптимизация
У предыдущего метода, впрочем, сразу видно узкое место – это стандартная функции сортировки. Она предназначена для сортировки массива произвольного размера, в ней осуществляется множество внутренних проверок, потому она, скорее всего, не будет оптимальным решением для данной задачи, где массив мал и имеет фиксированный размер. Кроме того, нам совсем не обязательно полностью сортировать массив, достаточно, что бы в 4-м элементе было требуемое нами значение. Потому мы можем применить метод сортировки «сетью». Кроме того вызов сам функций в теле цикла также вызывает дополнительные накладные расходы, потому функцию сортировки мы сделаем inline:
inline void sort(int& a, int& b) // сортирует пару чисел
{
if(a > b)
{
int t = a;
a = b;
b = t;
}
}
inline void sort(int a[9]) //частично сортирует весь массив
{
sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]);
sort(a[0], a[1]); sort(a[3], a[4]); sort(a[6], a[7]);
sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]);
sort(a[0], a[3]); sort(a[5], a[8]); sort(a[4], a[7]);
sort(a[3], a[6]); sort(a[1], a[4]); sort(a[2], a[5]);
sort(a[4], a[7]); sort(a[4], a[2]); sort(a[6], a[4]);
sort(a[4], a[2]);
}
2-я оптимизация
Хотя первый метод и получился значительно быстрее нулевого (см. результат тестирования ниже), но у него осталось одно узкое место – в этом методе очень много условных переходов. Как известно, современные процессоры очень их не любят, так как имеют конвейерную архитектуру и возможность внеочередного исполнения нескольких команд за один такт. И для первого, и для второго условные переходы крайне нежелательны, так как процессор должен останавливаться и ждать результатов вычислений, чтобы узнать по какой ветке программы ему следует идти дальше. К счастью сортировку двух 8 битных значений вполне можно реализовать и без условных переходов:
inline void sort(int& a, int& b)
{
int d = a - b;
int m = ~(d >> 8);
b += d&m;
a -= d&m;
}
3-я оптимизация
В принципе предыдущей оптимизации уже вполне достаточно, однако можно еще немного оптимизировать функцию void sort(int& a, int& b) с применением вспомогательног массива. Однако останавливаться здесь подробно на нем я не буду, так эта оптимизация не дает существенного ускорения работы алгоритма. Впрочем все желающие могут посмотреть его реализацию в приложении.
4-я оптимизация
До сих пор мы оставались в рамках стандратного С++ и не учитывали все возможности современных процессоров. Однако еще начина с процессора Pentium-MMX в процессорах появилась поддержка MMX (Multimedia Extensions) инструкций для векторной обработки данных. В частности, команды MMX могут исполнять целочисленные векторные операции сразу над 8-ю 8-битными числами за раз. А начиная с процессоров Pentium-IV и Athlon-64 появилась поддержка инструкций из набора SSE2 (Streaming SIMD Extensions), которые позволяют обрабатывать целочисленные векторные операции сразу над 16-ю 8-битными числами за раз. Сразу понятно, что теоретически использование SSE2 инструкций может потенциально ускорить программу 16 раз, потому глупо не попытаться их использовать.
К счастью, для того, чтобы задействовать инструкции из набора SSE2, совсем не обязательно использовать ассемблер. Большинство современных С++ компиляторов имеют поддержку intrinsics (встроенных функций, с помощью которых можно задействовать всевозможные расширения процессоров). Программирование с использованием intrinsics практически не отличается от программирования на чистом С. Intrinsic функции преобразуются компилятором напрямую в инструкции процессора, хотя при этом работа непосредственно с регистрами процессора остается скрытой от программиста. В большистве случаев программа с использованием intrinsics не уступает в быстродействии программе, написанной на ассемблере.
Целочисленные комманды SSE2 определены в заголовочном файле . В качестве базового типа выступает __m128i - 128 битный вектор, который в зависимости от контекста может интерпетироваться как набор 2-х 64 битных, 4-х 32 битных, 8-х 16 битных, 16-х 8 битных знаковых или беззнаковых чисел. Как видно, поддерживают не только векторные арифметические операции, но также векторные логические операции, а также векторные операции загрузки и выгрузки данных. Ниже приведен 4-й вариант оптимизации медианного фильтра при помощи SSE2 инструкций. Код, как мне кажется, довольно нагляден.
inline void sort(__m128i& a, __m128i& b)
{
const __m128i t = a;
a = _mm_min_epu8(t, b); //нахождение минимума 2-х 8 битных безннаковых чисел для каждого из 16 значений вектора
b = _mm_max_epu8(t, b); //нахождение максимума 2-х 8 битных безннаковых чисел для каждого из 16 значений вектора
}
inline void sort(__m128i a[9])
{
sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]);
sort(a[0], a[1]); sort(a[3], a[4]); sort(a[6], a[7]);
sort(a[1], a[2]); sort(a[4], a[5]); sort(a[7], a[8]);
sort(a[0], a[3]); sort(a[5], a[8]); sort(a[4], a[7]);
sort(a[3], a[6]); sort(a[1], a[4]); sort(a[2], a[5]);
sort(a[4], a[7]); sort(a[4], a[2]); sort(a[6], a[4]);
sort(a[4], a[2]);
}
inline void load(unsigned char* src, int stride, __m128i a[9])
{
a[0] = _mm_loadu_si128((__m128i*)(src - 1 - stride)); //загрузка 128 битного вектора по невыровненному по 16 битной границе адресу
a[1] = _mm_load_si128((__m128i*)(src - stride)); //загрузка 128 битного вектора по выровненному по 16 битной границе адресу
a[2] = _mm_loadu_si128((__m128i*)(src + 1 - stride));
a[3] = _mm_loadu_si128((__m128i*)(src - 1));
a[4] = _mm_load_si128((__m128i*)(src));
a[5] = _mm_loadu_si128((__m128i*)(src + 1));
a[6] = _mm_loadu_si128((__m128i*)(src - 1 + stride));
a[7] = _mm_load_si128((__m128i*)(src + stride));
a[8] = _mm_loadu_si128((__m128i*)(src + 1 + stride));
}
void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst)
{
__m128i a[9];
for(int y = 0; y Тестирование
Тестирование производилось на серых изображениях размером 1 MB. Для повышения точности измерения времени, тесты прогонялись несколько раз. Время выполнения получали делением общего времени исполнения тестов на количество прогонов. Количество прогонов выбиралось таким образом, что общее время исполнения было не меньше 1 секунды, что должно обеспечить два знака точности при измерении времени исполнения алгоритмов. Всего было протестировано 5 вариантов решения задачи:
0-й вариант с использованием стандартной сортировки.
1-й вариант с использованием сортировки "сетью".
2-й вариант с использованием сортировки "сетью" + без использования условных переходов.
3-й вариант с использованием сортировки "сетью" + без использования условных переходов (метод с применением вспомогательного массива) .
4-й вариант с оптимизацией под SSE2 расширение процессора.
Исходные коды теста находятся в приложении (см. ниже). Тест был скомпилирован с максимальной оптимизацией под Microsoft Visual Studio 2008 и был запущен на нескольких машинах со следующими результатами:
| Производитель | Intel | AMD | ||||
| Название | Core i5 750 | Core 2 Due | T2080 | Phenom II X6 | Athlon 64 X2 | Athlon |
| Частота, GHz | 2.67 | 2.3 | 1.7 | 2.8 | 2,8 | 0,8 |
| Название теста | Среднее время исполнения, мс | |||||
| base::median_filter with std::sort | 141 | 165 | 239 | 102 | 126 | 516 |
| base::median_filter with sorter_v1 | 46.7 | 59.4 | 76.6 | 39.9 | 65.8 | 170 |
| base::median_filter with sorter_v2 | 26.7 | 37.1 | 58.4 | 25.3 | 40.8 | 142 |
| base::median_filter with sorter_v3 | 24.1 | 29.7 | 41.2 | 23.7 | 47.6 | 131 |
| sse2::median_filter | 0.636 | 1.48 | 3.69 | 0.808 | 1.80 | --- |
| Название теста | Относительный/абсолютный выигрыш от оптимизации | |||||
| base::median_filter with sorter_v1 | 3.0 / 3.0 | 2.8 / 2.8 | 3.1 / 3.1 | 2.6 / 2.6 | 1.9 / 1.9 | 3.0 / 3.0 |
| base::median_filter with sorter_v2 | 1.7 / 5.3 | 1.6 / 4.4 | 1.3 / 4.1 | 1.6 / 4.0 | 1.6 / 3.0 | 1.2 / 3.6 |
| base::median_filter with sorter_v3 | 1.1 / 5.9 | 1.2 / 5.6 | 1.4 / 5.8 | 1.1 / 4.3 | 0.9 / 2.6 | 1.1 / 3.9 |
| sse2::median_filter | 37.9 / 222 | 20.1 / 111 | 11.2 / 64.8 | 29.3 / 126 | 22.6 / 70 | -- / -- |
Примечание: процессоры AMD Athlon не поддерживают инструкции из набора SSE2.
Выводы
На основании результатов тестов можно сделать следующие выводы:
При помощи стандартных средств C++ данный алгоритм может быть оптимизирован по скорости в 4-6 раз.
С применением инструкций SSE2 данный алгоритм можно еще ускорить в 10-40 раз. Это достаточно большая величина, которая перекрывает, как мне кажется, минусы отхода от потери переносимости стандартного C++.
Если соотнести время исполнения SSE2 и частоту процессоров, то можно судить о количестве инструкций SSE2 выполняемых данным процессором за один такт. Особенно это хорошо видно на примере процессоров Intel. Так настольный процессор Core 2 Due выполняет по одной операции SSE2 за такт, с мобильный процессор T2080 может выполнять лишь одну операцию за два такта. В тоже время новые процессоры Core i5 значительно ускорились и явно могут обрабатывать по 2 такие операции за такт.
Приложение
Код тестовой программы (написан на C++ под Microsoft Visual Studio 2008):
#include
#include
#include
#include
namespace base
{
const int saturate[] =
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255
};
__forceinline int cast(int t)
{
return saturate[t + 256];
}
struct sorter_v0
{
};
struct sorter_v1
{
__forceinline void operator() (int& a, int& b)
{
if(a > b)
{
int t = a;
a = b;
b = t;
}
}
};
struct sorter_v2
{
__forceinline void operator() (int& a, int& b)
{
int d = a - b;
int m = ~(d >> 8);
b += d&m;
a -= d&m;
}
};
struct sorter_v3
{
__forceinline void operator() (int& a, int& b)
{
int t = cast(a - b);
b += t;
a -= t;
}
};
template __forceinline void sort(int a[9], Sorter sorter)
{
sorter(a[1], a[2]); sorter(a[4], a[5]); sorter(a[7], a[8]);
sorter(a[0], a[1]); sorter(a[3], a[4]); sorter(a[6], a[7]);
sorter(a[1], a[2]); sorter(a[4], a[5]); sorter(a[7], a[8]);
sorter(a[0], a[3]); sorter(a[5], a[8]); sorter(a[4], a[7]);
sorter(a[3], a[6]); sorter(a[1], a[4]); sorter(a[2], a[5]);
sorter(a[4], a[7]); sorter(a[4], a[2]); sorter(a[6], a[4]);
sorter(a[4], a[2]);
}
template __forceinline void sort(int a[9], sorter_v0 sorter)
{
std::sort(a, a + 9);
}
__forceinline void load(unsigned char* src, int stride, int a[9])
{
a[0] = src[-1 - stride];
a[1] = src[-stride];
a[2] = src[1 - stride];
a[3] = src[-1];
a[4] = src[0];
a[5] = src[1];
a[6] = src[-1 + stride];
a[7] = src[stride];
a[8] = src[1 + stride];
}
template void median_filter(unsigned char* src, int width, int height, int stride, unsigned char* dst, Sorter sorter)
{
int a[9];
for(int y = 0; y 
Релоцировались? Теперь вы можете комментировать без верификации аккаунта.