Символ в битах с SIMD (и подстроки) - PullRequest
Новая
       70

Символ в битах с SIMD (и подстроки)

0 голосов
/ 11 декабря 2018

Я учусь понемногу программированию на SIMD, и я разработал (на первый взгляд) простую проблему, которая, я надеюсь, я могу ускорить с помощью SIMD (AVX, на данный момент у меня есть доступ только к процессорам AVX).

У меня есть длинная строка, состоящая из алфавита 2^k символов (например, 0, 1, 2, 3), и я хотел бы:

  • генерирует все подстроки заданной длины substringlength
  • преобразует все подстроки в биты

Подстроки - это просто последовательности символов из входной строки: 

012301230123012301230123012301233012301301230123123213012301230 

substringlength = 6;

string    bits
------+--+-----------------
012301 -> 01 00 11 10 01 00
123012 -> 10 01 00 11 10 01
230123 -> 11 10 01 00 11 10
301230 -> 00 11 10 01 00 11
...

Мой вопрос связан с моей неопытностью в SIMD (я только читал "Современное программирование на ассемблере x86", Kusswurm):

Может ли это помочь SIMD??

Редактировать : для простоты давайте просто предположим k = 2, и поэтому числа ASCII будут просто '0'..'3'.

Итерация 1

Читая комментарии и разыгрывая, я пришел к этим осознаниям.Я могу преобразовать ASCII в значения и, как предложено, умножить-добавить соседние байты: 

        // SIMD 128-bit registers, apparently I cannot use AVX ones directly (some operations are AVX2 or AVX-512)
        __m128i sse, val, adj, res;
        auto mask = _mm_set_epi8(1, 1<<4, 1, 1<<4, 1, 1<<4, 1, 1<<4, 1, 1<<4, 1, 1<<4, 1, 1<<4, 1, 1<<4);
        auto zero = _mm_set_epi8('0', '0', '0', '0', '0', '0', '0', '0',
                                 '0', '0', '0', '0', '0', '0', '0', '0');

        // Load ascii values
        sse = _mm_loadu_si128((__m128i*) s.data());

        // Convert to integer values
        val = _mm_sub_epi8(sse[0], zero);

        // Multiply with mask byte by byte (aka SHL second bytes of val) and sum
        adj = _mm_maddubs_epi16(val, mask);

Здесь дается представление о том, что он делает, для людей, которые учатся как я (мне нужно больше 128-биты для кодирования одной подстроки, ascii в шестнадцатеричном виде ): 

bytes   15   14   13   12   11   10    9    8    7    6    5    4    3    2    1    0

ascii   30   31   30   31   30   31   30   31   30   31   30   31   30   31   30   31

_mm_sub_epi8:

value    0    1    0    1    0    1    0    1    0    1    0    1    0    1    0    1

_mm_maddubs_epi16:

value    0    1    0    1    0    1    0    1    0    1    0    1    0    1    0    1
         *    *    *    *    *    *    *    *    *    *    *    *    *    *    *    *
mask     1    4    1    4    1    4    1    4    1    4    1    4    1    4    1    4
            +         +         +         +         +         +         +         +
        |        |         |         |         |         |         |         |        |
(16-bits)
bits     ....0100  ....0100  ....0100  ....0100  ....0100  ....0100  ....0100 ....0100

Другими словами правильные первые 4 бита, кодирующие 2 символа ascii, если я правильно понимаю что _mm_maddubs_epi16 сделал с моими значениями, в чем я совсем не уверен!

Теперь мне нужно что-то вроде " shift-or "соседних байтов, что-то вроде _mm_maddubs_epi16, которое сдвигает влево первый, и OR со вторым аргументом, производя 8-битное или 16-битное значение: 

(16-bits)
bits     ....0100  ....0100  ....0100  ....0100  ....0100  ....0100  ....0100 ....0100
         | shl 4          |  | shl 4          |  | shl 4          |  | shl 4         |
         0100....  ....0100  0100....  ....0100  0100....  ....0100  0100.... ....0100
                 OR                 OR                  OR                  OR
             ....01000100      ....01000100         ....01000100       ....01000100

Однако я не вижу, как _mm_bslli_si128 может помочь мне здесь, или если есть более разумный способ сделать это.Может быть, даже этот «горизонтальный» подход глуп, и я должен переосмыслить его.

Любой намек приветствуется!

...