Поиск различий между победителями и победителями AVX2

Я оптимизирую часть «победитель получает все» алгоритма оценки диспаратности, используя AVX2. Моя скалярная процедура точна, но при разрешении QVGA и 48 различиях время работы на моем ноутбуке разочаровывает медленно — ~ 14 мс. Я создаю изображения несоответствия LR и RL, но для простоты здесь я приведу только код для поиска RL.

Моя скалярная рутина:

int MAXCOST = 32000;
for (int i = maskRadius; i < rstep-maskRadius; i++) {

// WTA "RL" Search:
for (int j = maskRadius; j+maskRadius < cstep; j++) {
int minCost = MAXCOST;
int minDisp = 0;
for (int d = 0; d < numDisp && j+d < cstep; d++) {
if (asPtr[(i*numDisp*cstep)+(d*cstep)+j] < minCost) {
minCost = asPtr[(i*numDisp*cstep)+(d*cstep)+j];
minDisp = d;
}
}
dRPtr[(i*cstep)+j] = minDisp;
}
}

Моя попытка использования AVX2:

int MAXCOST = 32000;
int* dispVals = (int*) _mm_malloc( sizeof(int32_t)*16, 32 );

for (int i = maskRadius; i < rstep-maskRadius; i++) {

// WTA "RL" Search AVX2:
for( int j = 0; j < cstep-16; j+=16) {

__m256i minCosts = _mm256_set1_epi16( MAXCOST );
__m128i loMask   = _mm_setzero_si128();
__m128i hiMask   = _mm_setzero_si128();

for (int d = 0; d < numDisp && j+d < cstep; d++) {
// Grab 16 costs to compare
__m256i costs = _mm256_loadu_si256((__m256i*) (asPtr[(i*numDisp*cstep)+(d*cstep)+j]));

// Get the new minimums
__m256i newMinCosts = _mm256_min_epu16( minCosts, costs );

// Compare new mins to old to build mask to store minDisps
__m256i mask   = _mm256_cmpgt_epi16( minCosts, newMinCosts );
__m128i loMask = _mm256_extracti128_si256( mask, 0 );
__m128i hiMask = _mm256_extracti128_si256( mask, 1 );
// Sign extend to 32bits
__m256i loMask32 = _mm256_cvtepi16_epi32( loMask );
__m256i hiMask32 = _mm256_cvtepi16_epi32( hiMask );

__m256i currentDisp = _mm256_set1_epi32( d );
// store min disps with mask
_mm256_maskstore_epi32( dispVals, loMask32, currentDisp );    // RT error, why?
_mm256_maskstore_epi32( dispVals+8, hiMask32, currentDisp );  // RT error, why?

// Set minCosts to newMinCosts
minCosts = newMinCosts;
}

// Write the WTA minimums one-by-one to the RL disparity image
int index = (i*cstep)+j;
for( int k = 0; k < 16; k++ ) {
dRPtr[index+k] = dispVals[k];
}
}
}
_mm_free( dispVals );

Изображение пространства диспаратности (DSI) имеет размер HxWxD (320x240x48), который я выкладываю горизонтально для лучшего доступа к памяти, так что каждая строка имеет размер WxD.

Изображение пространства несоответствия имеет затраты на сопоставление для каждого пикселя. Это агрегировано
с простым блочным фильтром, чтобы сделать другое изображение точно такого же размера,
но с суммой затрат, скажем, в окне 3х3 или 5х5. Это сглаживание делает
результат более «надежный». Когда я обращаюсь с asPtr, я индексирую
в это изображение агрегированных затрат.

Кроме того, чтобы сэкономить на ненужных вычислениях, я начал
и заканчивается на строках, смещенных на радиус маски. Этот радиус маски является радиусом
моей маски переписи. Я мог бы сделать некоторое причудливое отражение границы, но это
Проще и быстрее просто не беспокоиться о несоответствии этой границы.
Это, конечно, относится и к началу и к концу cols, но возиться с
индексирование здесь не очень хорошо, когда я заставляю весь свой алгоритм работать только
на изображениях, столбцы которых кратны 16 (например, QVGA: 320×240), так что я
можно просто индексировать и поражать все с помощью SIMD (без остаточной скалярной обработки).

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

Мой код компилируется, но не выполняется во время выполнения. Я использую VS 2012 Express Update 4. Когда я работаю с отладчиком, я не могу получить какую-либо информацию. Я относительно новичок в использовании встроенных функций и поэтому не уверен, какую информацию мне следует ожидать при отладке, количество регистров, должны ли быть видны переменные __m256i и т. Д.

Прислушиваясь к комментариям ниже, я улучшил скалярное время с ~ 14 до ~ 8, используя более умную индексацию. Мой процессор — i7-4980HQ, и я успешно использую встроенные функции AVX2 в другом месте того же файла.

Информация изображения

4

Решение

Я до сих пор не нашел проблему, но я видел некоторые вещи, которые вы могли бы изменить. Вы не проверяете возвращаемое значение _mm_malloc, хоть. Если это терпит неудачу, это объяснило бы это. (Может быть, он не любит выделять 32-байтовую выровненную память?)

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

Запустите ваш код в отладчике и выясните, что происходит не так. «Ошибка времени выполнения» не очень значима.

_mm_set1* функции медленные. VPBROADCASTD нужен его источник в памяти или векторный регистр, а не регистр GP, поэтому компилятор может movd из GP reg в векторное reg и затем транслировать, или сохранить в памяти и затем транслировать. Во всяком случае, это было бы быстрее сделать

const __m256i add1 = _mm256_set1_epi32( 1 );
__m256i dvec = _mm256_setzero_si256();
for (d;d...;d++) {
dvec = _mm256_add_epi32(dvec, add1);
}

Другие вещи:
Это, вероятно, будет работать быстрее, если вы не сохраняете в памяти каждую итерацию внутреннего цикла. Используйте инструкцию смешивания (_mm256_blendv_epi8) или что-то в этом роде, чтобы обновить вектор (ы) смещений, которые соответствуют минимальным затратам. Смешать = замаскированное перемещение с регистром назначения.

Кроме того, ваши значения смещения должны соответствовать 16b целым числам, поэтому не расширяйте их до 32b, пока ПОСЛЕ того, как вы их не найдете. Процессоры Intel могут «на лету» расширять область памяти 16 байт в регистр gp без потери скорости (movsz так быстро, как mov), так проб. просто объявите свой dRPtr массив как uint16_t, Тогда вам вообще не понадобятся элементы расширения знака в вашем векторном коде (не говоря уже о вашем внутреннем цикле!). С надеждой _mm256_extracti128_si256( mask, 0 ) ничего не компилируется, поскольку желаемое 128 — это уже low128, так что просто используйте reg в качестве src для vmovsx, но до сих пор.

Вы также можете сохранить инструкцию (и uop для слитного домена), не загрузив сначала. (если компилятор не достаточно умен, чтобы не vmovdqu и использовать vpminuw с операндом памяти, даже если вы использовали встроенную нагрузку).

Вот я и думаю что-то вроде этого:

// totally untested, didn't even check that this compiles.
for(i) { for(j) {
// inner loop, compiler can hoist these constants.
const __m256i add1 = _mm256_set1_epi16( 1 );
__m256i dvec = _mm256_setzero_si256();
__m256i minCosts = _mm256_set1_epi16( MAXCOST );
__m256i minDisps = _mm256_setzero_si256();

for (int d=0 ; d < numDisp && j+d < cstep ;
d++, dvec = _mm256_add_epi16(dvec, add1))
{
__m256i newMinCosts = _mm256_min_epu16( minCosts, asPtr[(i*numDisp*cstep)+(d*cstep)+j]) );
__m256i mask   = _mm256_cmpgt_epi16( minCosts, newMinCosts );
minDisps = _mm256_blendv_epi8(minDisps, dvec, mask); // 2 uops, latency=2
minCosts = newMinCosts;
}

// put sign extension here if making dRPtr uint16_t isn't an option.
int index = (i*cstep)+j;
_mm256_storeu_si256 (dRPtr + index, __m256i minDisps);
}}

Вы можете получить лучшую производительность, имея две параллельные цепочки зависимостей: minCosts0 / minDisps0, а также minCosts1 / minDisps1и затем объединяя их в конце. minDisps является зависимостью, переносимой циклом, но цикл содержит только 5 инструкций (включая vpadd, который выглядит как накладные расходы цикла, но не может быть уменьшен при развертывании). Они декодируют до 6 мопов (blendv равно 2), плюс накладные расходы цикла. Он должен работать в 1,5 циклах / итерация (не считая накладных расходов цикла) на haswell, но цепочка dep будет ограничивать его одной итерацией на 2 цикла. (Предполагая развертывание, чтобы избавиться от накладных расходов цикла). Параллельное выполнение двух цепочек dep исправляет это и имеет тот же эффект, что и развертывание цикла: меньше накладных расходов цикла.

Хм, на самом деле на Haswell,

  • pminuw может работать на p1 / p5. (и нагрузочная часть на p2 / p3)
  • pcmpgtw может работать на p1 / p5
  • vpblendvb 2 мопа для р5.
  • padduw может работать на p1 / p5
  • movdqa reg,reg может работать на p0 / p1 / p5 (и может вообще не нуждаться в исполнительном модуле). Развертывание должно избавить от любых накладных расходов для minCosts = newMinCosts, так как компилятор может просто в конечном итоге newMinCosts из последнего развернутого тела цикла в правом регистре для первого тела цикла следующей итерации.
  • плавленый sub / jge (счетчик петель) может работать на p6. (с помощью PTEST + jcc на двек бы помедленнее). add/sub может работать на p0 / p1 / p5 / p6, если не соединен с jcc,

Итак, на самом деле цикл займет 2,5 цикла на итерацию, ограниченный инструкциями, которые могут выполняться только на p1 / p5. Развертывание на 2 или 4 уменьшит цикл / movdqa накладные расходы. Поскольку Haswell может выдавать 4 мопа за такт, он может более эффективно ставить в очередь мопы для выполнения не по порядку, поскольку цикл не будет иметь слишком большого числа итераций. (Ваш пример был 48.) Наличие большого количества мопов в очереди даст ЦП что-то делать после выхода из цикла, и сократит любые задержки из-за промахов в кеше и т. Д.

_mm256_min_epu16 (PMINUW) — еще одна цепочка зависимостей, переносимая циклами. Использование его с операндом памяти приводит к задержке в 3 или 4 цикла. Тем не менее, загрузочная часть инструкции может начаться, как только будет известен адрес, поэтому сложение нагрузки в модифицированном операторе, чтобы воспользоваться преимуществами микро-слияния, не делает депозвуковые цепочки длиннее или короче, чем при использовании отдельной загрузки.

Иногда вам нужно использовать отдельную загрузку для невыровненных данных (AVX убрал требование выравнивания для операндов памяти). Мы ограничены в большей степени единицами выполнения, чем лимит выдачи 4 мегапикселя / такт, поэтому, вероятно, хорошо использовать специальную инструкцию загрузки.

источник для портов / задержек insn.

2

Другие решения

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

Это может быть не совсем точно, но дает общее представление:

int MAXCOST = 32000, numDispXcstep = numDisp*cstep;
for (int i = maskRadius; i < rstep - maskRadius; i+=numDispXcstep) {
for (int j = maskRadius; j < cstep - maskRadius; j++) {
int minCost = MAXCOST, minDisp = 0;
for (int d = 0; d < numDispXcstep - j; d+=cstep) {
if (asPtr[i+j+d] < minCost) {
minCost = asPtr[i+j+d];
minDisp = d;
}
}
dRPtr[i/numDisp+j] = minDisp;
}
}

Как только вы это сделаете, станет ясно, что на самом деле происходит. Похоже, «i» — это самый большой шаг, за которым следует «d», где «j» — переменная, работающая с последовательными данными. … следующим шагом будет соответствующее переупорядочение циклов, и, если вам все еще нужна дополнительная оптимизация, примените специфичные для платформы встроенные функции.

2

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector