Implementar el desplazamiento de bits de BigInt utilizando intrínsecos sobre una matriz.

23 Jul, 2023 Programación 0

Me gustaría implementar desplazamiento de bits sobre un bloque de memoria utilizando SIMD. He encontrado esta solución que sigue esencialmente estos pasos:
– Desplazamientos por bytes de shift / CHAR_BIT utilizando memmove si el desplazamiento es mayor que CHAR_BIT.
– Desplazamientos de bits iterando sobre cada char del bloque de memoria.

Esto es esencialmente un O(n). Sé que puedo simplemente iterar sobre tipos de datos más grandes que char, sin embargo, estoy bastante seguro de que esto se puede hacer incluso más rápido utilizando intrínsecos.

void rshift(void *self, int other, size_t size) {
    if (other < size * CHAR_BIT) {
        unsigned char *s = self,
                      *pass = calloc(2, sizeof(unsigned char));

<pre><code>        if (pass != NULL) {
            int chars = other / CHAR_BIT,
                bits = other % CHAR_BIT;

            if (chars > 0) {
                memmove(s + chars, s, size - chars);
                memset(s, 0, chars);
            }

            if (bits > 0) {
                for (size_t i = 0; i < size;
                     i++, pass[0] = pass[1] << (CHAR_BIT - bits)) {
                    pass[1] = s[i] & ((1 << bits) - 1);
                    s[i] = (s[i] >> bits) | pass[0];
                }
            }

            free(pass);
        }
    } else memset(self, 0, size);
}

He intentado echar un vistazo a las diferentes operaciones intrínsecas, como _mm_srli_si128, que sin embargo realiza desplazamientos por bytes, no desplazamientos por bits.

¿Existe alguna manera de implementar la función anterior utilizando instrucciones SIMD?

davy.ai

July 23, 2023 at 7:55 pm

Sí, hay una forma de implementar la función anterior utilizando instrucciones SIMD. Una forma de hacer esto es utilizando las funciones intrínsecas de desplazamiento a derecha bitwise (_mm_srli_epi*_) disponibles en las Intel Intrinsics para SSE y AVX.

Este enfoque implica cargar los datos en un registro SIMD (por ejemplo, __m128i o __m256i) y realizar la operación de desplazamiento en ese registro. Dado que los registros tienen un tamaño mayor que char, podemos realizar la operación de desplazamiento en varios bytes (o incluso enteros) a la vez, lo que resulta en una implementación más rápida.

Aquí tienes un ejemplo de implementación de la función rshift utilizando instrucciones SIMD:

#include <immintrin.h>
#include <stdlib.h>
#include <string.h>

void rshift(void* self, int other, size_t size) {
    if (other < size * CHAR_BIT) {
        unsigned char* s = self,
                     * pass = calloc(2, sizeof(unsigned char));

        if (pass != NULL) {
            int chars = other / CHAR_BIT,
                bits = other % CHAR_BIT;

            if (chars > 0) {
                memmove(s + chars, s, size - chars);
                memset(s, 0, chars);
            }

            // Calcula el número de registros SIMD necesarios para procesar los datos
            int num_regs = size / sizeof(__m128i);
            int num_leftover = size % sizeof(__m128i);

            // Prepara los desplazamientos y máscaras para las operaciones bitwise
            __m128i shift_v = _mm_cvtsi32_si128(bits);
            __m128i mask_v = _mm_set1_epi8((1 << bits) - 1);
            __m128i carry_v = _mm_setzero_si128();
            __m128i prev_carry_v = _mm_setzero_si128();

            // Desplaza los datos utilizando instrucciones SIMD
            for (int i = 0; i < num_regs; i++) {
                // Carga los datos en un registro SIMD
                __m128i data_v = _mm_load_si128((__m128i*)(s + i * sizeof(__m128i)));

                // Desplaza los datos utilizando operaciones bitwise
                __m128i shifted_v = _mm_srli_epi16(data_v, bits);

                if (i > 0) {
                    // Combina los datos desplazados con los bits retenidos previos
                    __m128i combined_v = _mm_or_si128(shifted_v, prev_carry_v);

                    // Guarda los bits retenidos para la siguiente iteración
                    carry_v = _mm_slli_epi16(data_v, CHAR_BIT - bits);
                } else {
                    carry_v = _mm_slli_si128(data_v, sizeof(__m128i) - bits / CHAR_BIT);
                    carry_v = _mm_srli_si128(carry_v, sizeof(__m128i) - bits / CHAR_BIT);
                }

                // Realiza una operación bitwise AND entre los datos y la máscara para obtener los bits pasados
                __m128i pass_v = _mm_and_si128(data_v, mask_v);

                // Combina los datos desplazados con los bits retenidos previos y guarda los bits pasados
                _mm_store_si128((__m128i*)(s + i * sizeof(__m128i)), _mm_or_si128(shifted_v, prev_carry_v));
                _mm_store_si128((__m128i*)(pass), pass_v);

                prev_carry_v = carry_v;
            }

            // Procesa los bytes restantes
            for (size_t i = num_regs * sizeof(__m128i); i < size; i++, pass[0] = pass[1] << (CHAR_BIT - bits)) {
                pass[1] = s[i] & ((1 << bits) - 1);
                s[i] = (s[i] >> bits) | pass[0];
            }

            free(pass);
        }
    } else {
        memset(self, 0, size);
    }
}

Esta implementación utiliza intrínsecas SSE2 para __m128i, pero también puedes utilizar intrínsecas AVX (__m256i) para registros más anchos y aún mejor rendimiento. Ten en cuenta que la implementación SIMD puede no ser necesariamente más rápida que la implementación original, dependiendo del tamaño de los datos y la cantidad de desplazamiento. Siempre se recomienda realizar pruebas de rendimiento con diferentes implementaciones para encontrar la más óptima para tu caso de uso.</string.h></stdlib.h></immintrin.h>

es.davy.ai

¿Tienes una pregunta?

Implementar el desplazamiento de bits de BigInt utilizando intrínsecos sobre una matriz.

Answer

davy.ai