Оптимизация кода SSE

Question

Я бы хотел, чтобы некоторые из них помогли оптимизировать самую вычислительно интенсивную функцию моей программы. В настоящее время я нахожу, что базовая (не SSE) версия значительно быстрее (до 3x). Поэтому я прошу вас помочь в исправлении этого.

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

Первый вариант является основным вариантом. Он проверяет, является ли block_ подмножеством x.blocks_.

//Check for self comparison 
    if (this == &x) 
      return false; 

//A subset is equal to or smaller. 
    if (no_bits_ > x.no_bits_) 
      return false; 

    int i; 

    bool equal = false; 

//Pointers should not change. 
    const unsigned int *tptr = blocks_; 
    const unsigned int *xptr = x.blocks_; 


    for (i = 0; i < no_blocks_; i++, tptr++, xptr++) { 
      if ((*tptr & *xptr) != *tptr) 
        return false; 
      if (*tptr != *xptr) 
        equal = true; 
    } 

    return equal; 

Затем идет вариант SSE, который, увы, не соответствует моим ожиданиям. Оба эти фрагмента должны искать одни и те же вещи.

//starting pointers.   
    const __m128i* start = (__m128i*)&blocks_; 
    const __m128i* xstart = (__m128i*)&x.blocks_; 

    __m128i block; 
    __m128i xblock; 

    //Unsigned ints are 32 bits, meaning 4 can fit in a register. 
    for (i = 0; i < no_blocks_; i+=4) { 

      block = _mm_load_si128(start + i); 
      xblock = _mm_load_si128(xstart + i); 

        //Equivalent to (block & xblock) != block 
        if (_mm_movemask_epi8(_mm_cmpeq_epi32(_mm_and_si128(block, xblock), block)) != 0xffff) 
          return false; 

        //Equivalent to block != xblock 
        if (_mm_movemask_epi8(_mm_cmpeq_epi32(block, xblock)) != 0xffff) 
          equal = true; 
    } 
    return equal; 

Есть ли у вас какие-либо предложения относительно того, как я могу улучшить производительность версии SSE? Я делаю что-то неправильно? Или это случай, когда оптимизация должна проводиться в другом месте?

Я еще не добавил в оставшиеся вычисления для no_blocks_% 4! = 0, но это мало, поэтому пока производительность не увеличится, и это будет только загромождать код на данный момент.

Благодарим за предоставленную помощь.

Answer 1

Есть три возможности, которые я вижу здесь.

Во-первых, ваши данные могут не соответствовать широким сравнениям. Если есть высокая вероятность, что (*tptr & *xptr) != *tptr в первых нескольких блоках, простая версия C++ почти наверняка будет всегда быстрее. В этом случае ваш SSE будет выполнять больше данных &, чтобы выполнить одно и то же.

Во-вторых, ваш код SSE может быть неправильным. Здесь не совсем ясно. Если no_blocks_ идентично между двумя образцами, то start + i, вероятно, имеет нежелательное поведение индексации в 128-битных элементах, а не 32-битное в качестве первого образца.

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

Вот быстрый непроверенный снимок при обработке 2 блоков SSE сразу. Примечание. Я полностью удалял ветвь block != xblock, сохраняя состояние вне цикла и тестируя только в конце. В целом, это перемещает вещи от 1,3 филиалов на int до 0,25.

bool equal(unsigned const *a, unsigned const *b, unsigned count) 
{ 
    __m128i eq1 = _mm_setzero_si128(); 
    __m128i eq2 = _mm_setzero_si128(); 

    for (unsigned i = 0; i != count; i += 8) 
    { 
     __m128i xa1 = _mm_load_si128((__m128i const*)(a + i)); 
     __m128i xb1 = _mm_load_si128((__m128i const*)(b + i)); 

     eq1 = _mm_or_si128(eq1, _mm_xor_si128(xa1, xb1)); 
     xa1 = _mm_cmpeq_epi32(xa1, _mm_and_si128(xa1, xb1)); 

     __m128i xa2 = _mm_load_si128((__m128i const*)(a + i + 4)); 
     __m128i xb2 = _mm_load_si128((__m128i const*)(b + i + 4)); 

     eq2 = _mm_or_si128(eq2, _mm_xor_si128(xa2, xb2)); 
     xa2 = _mm_cmpeq_epi32(xa2, _mm_and_si128(xa2, xb2)); 

     if (_mm_movemask_epi8(_mm_packs_epi32(xa1, xa2)) != 0xFFFF) 
      return false; 
    } 

    return _mm_movemask_epi8(_mm_or_si128(eq1, eq2)) != 0; 
} 

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

Answer 2

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

Есть некоторые альтернативные стратегии для повышения производительности в пропускной способности, ограниченная задаче:

• памяти скрыть доступ Multi-нить путем одновременной арифметикой операций в контексте Hyper-Threading.
• Точная настройка размера загрузки данных во время улучшает пропускную способность памяти.
• Улучшите непрерывность линии трубопровода, добавив дополнительные операции независимых в цикл (сканирование двух разных наборов данных на каждом шаге вашего цикла «для»)
• Храните больше данных в кеше или в регистрах (некоторые итерации вашего код может понадобиться один и тот же набор данных много раз)