6-битный поиск с использованием SIMD AVX2

Я пытаюсь правильно выполнить 6-битный поиск на SIMD AVX2. Я разделяю 6 бит на младшие 4 бита и старшие 2 бита, младшие 4 используются для операции перемешивания, а затем смешиваю результаты с включенными соответствующими масками. Мне кажется, что логика в порядке, и мне нужна помощь в понимании того, что я делаю неправильно. Значения довольно близки по сравнению со скалярным эквивалентом, но неверны.

Обновлено: таблица поиска содержит 64 записи, поэтому я загружаю 16-байтовые регистры четыре раза.


pub fn senary_weighted_wrapper(data: &[u8]) -> u64 {
    // Initialize lookup table
    let mut lookup = [0u8; 64];
    for i in 0..64 {
        lookup[i] = i.count_ones() as u8;
    }

    unsafe { senary_weighted_simd_avx2(data.as_ptr(), data.len(), &lookup) }
}


unsafe fn senary_weighted_simd_avx2(data: *const u8, n: usize, lookup: &[u8; 64]) -> u64 {
    let mut i = 0;
    let lookup_vec0 = _mm256_loadu_si256(lookup.as_ptr() as *const __m256i);
    let lookup_vec1 = _mm256_loadu_si256(lookup.as_ptr().add(16) as *const __m256i);
    let lookup_vec2 = _mm256_loadu_si256(lookup.as_ptr().add(32) as *const __m256i);
    let lookup_vec3 = _mm256_loadu_si256(lookup.as_ptr().add(48) as *const __m256i);
    let low_mask = _mm256_set1_epi8(0x0f); // 4 bits mask
    let mut acc = _mm256_setzero_si256();

    while i + 32 < n {
        let mut local = _mm256_setzero_si256();
        for _ in 0..255 / 8 {
            if i + 32 >= n {
                break;
            }
            let vec = _mm256_loadu_si256(data.add(i) as *const __m256i);
            let vec_masked = _mm256_and_si256(vec, _mm256_set1_epi8(0x3F)); // Mask to lower 6 bits

            let lo = _mm256_and_si256(vec_masked, low_mask);
            let hi = _mm256_srli_epi16(vec_masked, 4);

            let result0 = _mm256_shuffle_epi8(lookup_vec0, lo);
            let result1 = _mm256_shuffle_epi8(lookup_vec1, lo);
            let result2 = _mm256_shuffle_epi8(lookup_vec2, lo);
            let result3 = _mm256_shuffle_epi8(lookup_vec3, lo);

            let blend01 = _mm256_blendv_epi8(result0, result1, _mm256_slli_epi16(hi, 7));
            let blend23 = _mm256_blendv_epi8(result2, result3, _mm256_slli_epi16(hi, 7));
            let popcnt = _mm256_blendv_epi8(blend01, blend23, _mm256_slli_epi16(hi, 6));

            local = _mm256_add_epi8(local, popcnt);
            i += 32;
        }
        acc = _mm256_add_epi64(acc, _mm256_sad_epu8(local, _mm256_setzero_si256()));
    }

    let mut result = 0u64;
    result += _mm256_extract_epi64(acc, 0) as u64;
    result += _mm256_extract_epi64(acc, 1) as u64;
    result += _mm256_extract_epi64(acc, 2) as u64;
    result += _mm256_extract_epi64(acc, 3) as u64;

    // Handle remaining bytes
    while i < n {
        let byte = *data.add(i) & 0x3F; // Mask to lower 6 bits
        result += lookup[byte as usize] as u64;
        i += 1;
    }

    result
}

Значения довольно близки по сравнению со скалярным эквивалентом, но неверны.

_mm256_srli_epi16 - почему там сдвиг на 16 бит? Это приведет к перемещению мусора в каждый второй элемент.
Ext3h 03.08.2024 08:46

@Ext3h, насколько я понимаю, hi используется только таким образом, что это не имеет значения (но также этот сдвиг вообще не нужно делать, вместо этого можно отрегулировать более поздние сдвиги влево)

user555045 03.08.2024 08:51

@Tin сдвиг в обратном направлении вообще не требовался, также не имеет значения, на какой размер слова вы сдвигаете. Ошибка была не в этом.

Ext3h 03.08.2024 08:58

Да, я согласен. Спасибо за разъяснения. Все еще не уверен, что понимаю суть проблемы.

Tin 03.08.2024 09:01

Вы на самом деле ищете popcnt или это просто для иллюстрации?

chtz 03.08.2024 09:43
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
5
88
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

let lookup_vec0 = _mm256_loadu_si256(lookup.as_ptr() as *const __m256i);

Это неправильно, это не должна была быть непрерывная загрузка в 32 байта, но вам нужны были одни и те же 16 байтов как в нижней, так и в верхней половине для каждого из 4 регистров поиска.

В таблице поиска 64 записи, поэтому я четыре раза загружаю регистры по 16 байт, не так ли?

Tin 03.08.2024 08:59

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

Ext3h 03.08.2024 09:02

Вы имели в виду, что lookup.as_ptr().add(16) используется неправильно? это абсолютная позиция от начала массива. В чем проблема?

Tin 03.08.2024 09:12

Отлично, я наконец-то это понял. ` let lookup_vec1 = _mm256_broadcastsi128_si256(_mm_loadu_si128(lookup.as_ptr().‌​add(16) as *const __m128i)); `

Tin 03.08.2024 09:20

Другие вопросы по теме