Подтвердить что ты не робот

C против ассемблера и производительности NEON

Я работаю над приложением iPhone, которое выполняет обработку изображений в реальном времени. Одним из первых шагов в его конвейере является преобразование изображения BGRA в оттенки серого. Я пробовал несколько разных методов, и разница в результатах синхронизации намного больше, чем я себе представлял. Сначала я попытался использовать C. Я аппроксимирую преобразование в светимость, добавив B + 2 * G + R/4

void BGRA_To_Byte(Image<BGRA> &imBGRA, Image<byte> &imByte)
{
uchar *pIn = (uchar*) imBGRA.data;
uchar *pLimit = pIn + imBGRA.MemSize();

uchar *pOut = imByte.data;
for(; pIn < pLimit; pIn+=16)   // Does four pixels at a time
{
    unsigned int sumA = pIn[0] + 2 * pIn[1] + pIn[2];
    pOut[0] = sumA / 4;
    unsigned int sumB = pIn[4] + 2 * pIn[5] + pIn[6];
    pOut[1] = sumB / 4;
    unsigned int sumC = pIn[8] + 2 * pIn[9] + pIn[10];
    pOut[2] = sumC / 4;
    unsigned int sumD = pIn[12] + 2 * pIn[13] + pIn[14];
    pOut[3] = sumD / 4;
    pOut +=4;
}       
}

Этот код занимает 55 мс для преобразования изображения 352х288. Затем я нашел некоторый код ассемблера, который делает практически то же самое

void BGRA_To_Byte(Image<BGRA> &imBGRA, Image<byte> &imByte)
{
uchar *pIn = (uchar*) imBGRA.data;
uchar *pLimit = pIn + imBGRA.MemSize();

unsigned int *pOut = (unsigned int*) imByte.data;

for(; pIn < pLimit; pIn+=16)   // Does four pixels at a time
{
  register unsigned int nBGRA1 asm("r4");
  register unsigned int nBGRA2 asm("r5");
  unsigned int nZero=0;
  unsigned int nSum1;
  unsigned int nSum2;
  unsigned int nPacked1;
  asm volatile(

               "ldrd %[nBGRA1], %[nBGRA2], [ %[pIn], #0]       \n"   // Load in two BGRA words
               "usad8 %[nSum1], %[nBGRA1], %[nZero]  \n"  // Add R+G+B+A 
               "usad8 %[nSum2], %[nBGRA2], %[nZero]  \n"  // Add R+G+B+A 
               "uxtab %[nSum1], %[nSum1], %[nBGRA1], ROR #8    \n"   // Add G again
               "uxtab %[nSum2], %[nSum2], %[nBGRA2], ROR #8    \n"   // Add G again
               "mov %[nPacked1], %[nSum1], LSR #2 \n"    // Init packed word   
               "mov %[nSum2], %[nSum2], LSR #2 \n"   // Div by four
               "add %[nPacked1], %[nPacked1], %[nSum2], LSL #8 \n"   // Add to packed word                 

               "ldrd %[nBGRA1], %[nBGRA2], [ %[pIn], #8]       \n"   // Load in two more BGRA words
               "usad8 %[nSum1], %[nBGRA1], %[nZero]  \n"  // Add R+G+B+A 
               "usad8 %[nSum2], %[nBGRA2], %[nZero]  \n"  // Add R+G+B+A 
               "uxtab %[nSum1], %[nSum1], %[nBGRA1], ROR #8    \n"   // Add G again
               "uxtab %[nSum2], %[nSum2], %[nBGRA2], ROR #8    \n"   // Add G again
               "mov %[nSum1], %[nSum1], LSR #2 \n"   // Div by four
               "add %[nPacked1], %[nPacked1], %[nSum1], LSL #16 \n"   // Add to packed word
               "mov %[nSum2], %[nSum2], LSR #2 \n"   // Div by four
               "add %[nPacked1], %[nPacked1], %[nSum2], LSL #24 \n"   // Add to packed word                 

               ///////////
               ////////////

               : [pIn]"+r" (pIn), 
         [nBGRA1]"+r"(nBGRA1),
         [nBGRA2]"+r"(nBGRA2),
         [nZero]"+r"(nZero),
         [nSum1]"+r"(nSum1),
         [nSum2]"+r"(nSum2),
         [nPacked1]"+r"(nPacked1)
               :
               : "cc"  );
  *pOut = nPacked1;
  pOut++;
 }
 }

Эта функция преобразует одно и то же изображение в 12 мс, почти на 5 раз быстрее! Я раньше не программировался на ассемблере, но я предположил, что для такой простой операции это будет не намного быстрее, чем C. Вдохновленный этим успехом, я продолжил поиск и нашел пример преобразования NEON здесь.

void greyScaleNEON(uchar* output_data, uchar* input_data, int tot_pixels)
{
__asm__ volatile("lsr          %2, %2, #3      \n"
                 "# build the three constants: \n"
                 "mov         r4, #28          \n" // Blue channel multiplier
                 "mov         r5, #151         \n" // Green channel multiplier
                 "mov         r6, #77          \n" // Red channel multiplier
                 "vdup.8      d4, r4           \n"
                 "vdup.8      d5, r5           \n"
                 "vdup.8      d6, r6           \n"
                 "0:                           \n"
                 "# load 8 pixels:             \n"
                 "vld4.8      {d0-d3}, [%1]!   \n"
                 "# do the weight average:     \n"
                 "vmull.u8    q7, d0, d4       \n"
                 "vmlal.u8    q7, d1, d5       \n"
                 "vmlal.u8    q7, d2, d6       \n"
                 "# shift and store:           \n"
                 "vshrn.u16   d7, q7, #8       \n" // Divide q3 by 256 and store in the d7
                 "vst1.8      {d7}, [%0]!      \n"
                 "subs        %2, %2, #1       \n" // Decrement iteration count
                 "bne         0b            \n" // Repeat unil iteration count is not zero
                 :
                 :  "r"(output_data),           
                 "r"(input_data),           
                 "r"(tot_pixels)        
                 : "r4", "r5", "r6"
                 );
}

Результаты синхронизации были трудно поверить. Он преобразует одно и то же изображение за 1 мс. 12X быстрее, чем ассемблер и поразительный 55X быстрее, чем C. Я понятия не имел, что такое повышение производительности возможно. В свете этого у меня есть несколько вопросов. Во-первых, я делаю что-то ужасное в коде C? Мне все еще трудно поверить, что это так медленно. Во-вторых, если эти результаты абсолютно точны, в каких ситуациях я могу ожидать, что эти выгоды получат? Вы, вероятно, можете себе представить, насколько я рад, что буду делать другие части моего конвейера быстрее на 55X. Должен ли я изучать ассемблер /NEON и использовать их внутри любого цикла, который занимает значительное время?

Обновление 1: я опубликовал вывод ассемблера из моей функции C в текстовом файле в http://temp-share.com/show/f3Yg87jQn Это было слишком велико, чтобы включать прямо здесь.

Сроки выполняются с использованием функций OpenCV.

double duration = static_cast<double>(cv::getTickCount()); 
//function call 
duration = static_cast<double>(cv::getTickCount())-duration;
duration /= cv::getTickFrequency();
//duration should now be elapsed time in ms

Результаты

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

for(; pIn < pLimit; pIn+=16)   // Does four pixels at a time
{     
  //Jul 16, 2012 MR: Read and writes collected
  sumA = pIn[0] + 2 * pIn[1] + pIn[2];
  sumB = pIn[4] + 2 * pIn[5] + pIn[6];
  sumC = pIn[8] + 2 * pIn[9] + pIn[10];
  sumD = pIn[12] + 2 * pIn[13] + pIn[14];
  pOut +=4;
  pOut[0] = sumA / 4;
  pOut[1] = sumB / 4;
  pOut[2] = sumC / 4;
  pOut[3] = sumD / 4;
}

Это изменение привело к сокращению времени обработки до 53 мс при улучшении 2 мс. Далее, как рекомендовал Виктор, я сменил свою функцию на выбор в качестве uint. Внутренний цикл тогда выглядел как

unsigned int* in_int = (unsigned int*) original.data;
unsigned int* end = (unsigned int*) in_int + out_length;
uchar* out = temp.data;

for(; in_int < end; in_int+=4)   // Does four pixels at a time
{
    unsigned int pixelA = in_int[0];
    unsigned int pixelB = in_int[1];
    unsigned int pixelC = in_int[2];
    unsigned int pixelD = in_int[3];

    uchar* byteA = (uchar*)&pixelA;
    uchar* byteB = (uchar*)&pixelB;
    uchar* byteC = (uchar*)&pixelC;
    uchar* byteD = (uchar*)&pixelD;         

    unsigned int sumA = byteA[0] + 2 * byteA[1] + byteA[2];
    unsigned int sumB = byteB[0] + 2 * byteB[1] + byteB[2];
    unsigned int sumC = byteC[0] + 2 * byteC[1] + byteC[2];
    unsigned int sumD = byteD[0] + 2 * byteD[1] + byteD[2];

    out[0] = sumA / 4;
    out[1] = sumB / 4;
    out[2] = sumC / 4;
    out[3] = sumD / 4;
    out +=4;
    }

Эта модификация имела драматический эффект, снизив время обработки до 14 мс, падение на 39 мс (75%). Этот последний результат очень близок к производительности ассемблера 11 мс. Окончательная оптимизация, рекомендованная rob, заключалась в том, чтобы включить ключевое слово __restrict. Я добавил его перед каждым объявлением указателя, изменяя следующие строки

__restrict unsigned int* in_int = (unsigned int*) original.data;
unsigned int* end = (unsigned int*) in_int + out_length;
__restrict uchar* out = temp.data;  
...
__restrict uchar* byteA = (uchar*)&pixelA;
__restrict uchar* byteB = (uchar*)&pixelB;
__restrict uchar* byteC = (uchar*)&pixelC;
__restrict uchar* byteD = (uchar*)&pixelD;  
...

Эти изменения не оказали заметного влияния на время обработки. Спасибо вам за вашу помощь, я буду уделять гораздо больше внимания управлению памятью в будущем.

4b9b3361

ОТВЕТЫ

Ответ 1

Здесь есть объяснение относительно некоторых причин успеха NEON: http://hilbert-space.de/?p=22

Попробуйте выполнить компиляцию кода C с помощью переключателей "-S-O3", чтобы увидеть оптимизированный вывод компилятора GCC.

IMHO, ключом к успеху является оптимизированный шаблон чтения/записи, используемый обе версиями сборки. И NEON/MMX/другие векторные двигатели также поддерживают насыщенность (результаты зажима до 0..255 без использования "unsigned ints" ).

Смотрите эти строки в цикле:

unsigned int sumA = pIn[0] + 2 * pIn[1] + pIn[2];
pOut[0] = sumA / 4;
unsigned int sumB = pIn[4] + 2 * pIn[5] + pIn[6];
pOut[1] = sumB / 4;
unsigned int sumC = pIn[8] + 2 * pIn[9] + pIn[10];
pOut[2] = sumC / 4;
unsigned int sumD = pIn[12] + 2 * pIn[13] + pIn[14];
pOut[3] = sumD / 4;
pOut +=4;

Чтения и записи действительно смешаны. Немного лучшая версия цикла цикла будет

// and the pIn reads can be combined into a single 4-byte fetch
sumA = pIn[0] + 2 * pIn[1] + pIn[2];
sumB = pIn[4] + 2 * pIn[5] + pIn[6];
sumC = pIn[8] + 2 * pIn[9] + pIn[10];
sumD = pIn[12] + 2 * pIn[13] + pIn[14];
pOut +=4;
pOut[0] = sumA / 4;
pOut[1] = sumB / 4;
pOut[2] = sumC / 4;
pOut[3] = sumD / 4;

Имейте в виду, что строка "unsigned in sumA" здесь может действительно означать вызов alloca() (распределение в стеке), поэтому вы тратите много циклов на временные распределения var (вызов функции 4 раза).

Кроме того, индексирование pIn [i] выполняет только однобайтную выборку из памяти. Лучший способ сделать это - прочитать int, а затем извлечь одиночные байты. Чтобы ускорить работу, используйте "unsgined int *" для чтения 4 байта (pIn [i * 4 + 0], pIn [i * 4 + 1], pIn [i * 4 + 2], pIn [i * 4 + 3]).

Версия NEON явно превосходит: строки

             "# load 8 pixels:             \n"
             "vld4.8      {d0-d3}, [%1]!   \n"

и

             "#save everything in one shot   \n"
             "vst1.8      {d7}, [%0]!      \n"

сохранить большую часть времени для доступа к памяти.

Ответ 2

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

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

Тем не менее, вы по-прежнему сможете использовать свой опыт работы с новоиспеченными ассемблерами в хорошем качестве, поскольку теперь вы можете проверить сборку, подготовленную вашим компилятором, и выяснить, является ли это глупостью. Если это так, вы можете настроить код C (возможно, используя pipelining вручную, если компилятор не справляется), перекомпилируйте его, посмотрите на сборку, чтобы узнать, выполняет ли компилятор то, что вы хотите, а затем проверите, чтобы увидеть, действительно ли он работает быстрее...

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

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

Ответ 3

Ответ Виктора Латыпова есть много хорошей информации, но я хочу указать еще одну вещь: в вашей исходной функции C компилятор не может сказать, что pIn и pOut указывают на неперекрывающиеся области памяти, Теперь посмотрите на эти строки:

pOut[0] = sumA / 4;
unsigned int sumB = pIn[4] + 2 * pIn[5] + pIn[6];

Компилятор должен предположить, что pOut[0] может быть таким же, как pIn[4] или pIn[5] или pIn[6] (или любой другой pIn[x]). Таким образом, он в принципе не может изменить порядок кода в вашем цикле.

Вы можете сказать компилятору, что pIn и pOut не перекрываются, объявляя их __restrict:

__restrict uchar *pIn = (uchar*) imBGRA.data;
__restrict uchar *pOut = imByte.data;

Это может немного ускорить исходную версию C.

Ответ 4

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

Также, глядя на сборку, они не используют деление, а скорее только умножения, поэтому изучите это для своего кода на C. Другим примером является то, что он оптимизирует ваше умножение на 2 из двух дополнений. Это снова может быть еще одним трюком, поскольку умножение может быть медленнее в приложении iPhone, чем добавление.