c++ - numeros - ¿Cómo transpondrías una matriz binaria?

como llenar una matriz con numeros aleatorios en c++

Question

Tengo matrices binarias en C ++ que represento con un vector de valores de 8 bits.

Por ejemplo, la siguiente matriz:

1 0 1 0 1 0 1
0 1 1 0 0 1 1
0 0 0 1 1 1 1

está representado como:

const uint8_t matrix[] = {
    0b01010101,
    0b00110011,
    0b00001111,
};

La razón por la que lo hago de esta manera es porque luego de calcular el producto de dicha matriz y un vector de 8 bits se vuelve realmente simple y eficiente (solo un AND a nivel de bit y un cálculo de paridad, por fila), que es mucho mejor que calculando cada bit individualmente

Ahora estoy buscando una forma eficiente de transponer dicha matriz, pero no he podido averiguar cómo hacerlo sin tener que calcular manualmente cada bit.

Solo para aclarar, para el ejemplo anterior, me gustaría obtener el siguiente resultado de la transposición:

const uint8_t transposed[] = {
    0b00000000,
    0b00000100,
    0b00000010,
    0b00000110,
    0b00000001,
    0b00000101,
    0b00000011,
    0b00000111,
};

NOTA : Preferiría un algoritmo que pueda calcular esto con matrices de tamaño arbitrario pero también estoy interesado en algoritmos que solo pueden manejar ciertos tamaños.

Answer 1

Aquí está el texto del correo electrónico de Jay Foad sobre la rápida transposición de la matriz Booleana:

El corazón del algoritmo de transposición Boolean es una función que denominaré transpose8x8 que transpone una matriz booleana de 8x8 empaquetada en una palabra de 64 bits (en el orden principal de la fila de MSB a LSB). Para transponer cualquier matriz rectangular cuyo ancho y alto sean múltiplos de 8, divídala en bloques de 8x8, transpórtelos individualmente y guárdalos en el lugar apropiado de la salida. Para cargar un bloque de 8x8, debe cargar 8 bytes individuales y cambiarlos a O a una palabra de 64 bits. Lo mismo para almacenar.

Una implementación en C simple de transpose8x8 basa en el hecho de que todos los bits en cualquier línea diagonal paralela a la diagonal inicial se mueven la misma distancia hacia arriba / abajo y hacia la izquierda / derecha. Por ejemplo, todos los bits justo por encima de la diagonal inicial tienen que moverse un lugar a la izquierda y un lugar hacia abajo, es decir, 7 bits a la derecha en la palabra empaquetada de 64 bits. Esto lleva a un algoritmo como este:

transpose8x8(word) {

  return
    (word & 0x0100000000000000) >> 49 // top right corner

  | (word & 0x0201000000000000) >> 42

  | ...

  | (word & 0x4020100804020100) >> 7 // just above diagonal

  | (word & 0x8040201008040201) // leading diagonal

  | (word & 0x0080402010080402) << 7 // just below diagonal

  | ...
  | (word & 0x0000000000008040) << 42

  | (word & 0x0000000000000080) << 49; // bottom left corner

}

Esto se ejecuta aproximadamente 10 veces más rápido que la implementación anterior, que copió cada bit individualmente desde el byte de origen en la memoria y lo fusionó en el byte de destino en la memoria.

Alternativamente, si tiene instrucciones PDEP y PEXT, puede implementar una mezcla aleatoria perfecta y usarla para hacer la transposición como se menciona en Hacker''s Delight. Esto es significativamente más rápido (pero no tengo horarios a mano):

shuffle(word) {
    return pdep(word >> 32, 0xaaaaaaaaaaaaaaaa) | pdep(word, 0x5555555555555555);
} // outer perfect shuffle

transpose8x8(word) { return shuffle(shuffle(shuffle(word))); }

La instrucción vgbbd de POWER implementa efectivamente todo transpose8x8 en una sola instrucción (y dado que es una instrucción vectorial de 128 bits, lo hace dos veces, independientemente, en los 64 bits bajos y en los 64 bits altos). Esto dio aproximadamente un 15% de aceleración sobre la implementación de C simple. (Solo 15% porque, aunque el bit twiddling es mucho más rápido, el tiempo total de ejecución ahora está dominado por el tiempo que lleva cargar 8 bytes y ensamblarlos en el argumento para transpose8x8 , y tomar el resultado y almacenarlo como 8 separados bytes)

Answer 2

Esto es lo que publiqué en gitub (mischasan / sse2 / ssebmx.src) Cambiar INP () y OUT () para usar vars de inducción guarda un IMUL cada uno. AVX256 lo hace dos veces más rápido. AVX512 no es una opción, porque no hay _mm512_movemask_epi8 ().

#include <stdint.h>
#include <emmintrin.h>

#define INP(x,y) inp[(x)*ncols/8 + (y)/8]
#define OUT(x,y) out[(y)*nrows/8 + (x)/8]

void ssebmx(char const *inp, char *out, int nrows, int ncols)
{
    int rr, cc, i, h;
    union { __m128i x; uint8_t b[16]; } tmp;

    // Do the main body in [16 x 8] blocks:
    for (rr = 0; rr <= nrows - 16; rr += 16)
        for (cc = 0; cc < ncols; cc += 8) {
            for (i = 0; i < 16; ++i)
                tmp.b[i] = INP(rr + i, cc);
            for (i = 8; i--; tmp.x = _mm_slli_epi64(tmp.x, 1))
                *(uint16_t*)&OUT(rr, cc + i) = _mm_movemask_epi8(tmp.x);
        }

    if (rr == nrows) return;

    // The remainder is a row of [8 x 16]* [8 x 8]?

    //  Do the [8 x 16] blocks:
    for (cc = 0; cc <= ncols - 16; cc += 16) {
        for (i = 8; i--;)
            tmp.b[i] = h = *(uint16_t const*)&INP(rr + i, cc),
            tmp.b[i + 8] = h >> 8;
        for (i = 8; i--; tmp.x = _mm_slli_epi64(tmp.x, 1))
            OUT(rr, cc + i) = h = _mm_movemask_epi8(tmp.x),
            OUT(rr, cc + i + 8) = h >> 8;
    }

    if (cc == ncols) return;

    //  Do the remaining [8 x 8] block:
    for (i = 8; i--;)
        tmp.b[i] = INP(rr + i, cc);
    for (i = 8; i--; tmp.x = _mm_slli_epi64(tmp.x, 1))
        OUT(rr, cc + i) = _mm_movemask_epi8(tmp.x);
}

HTH.

Answer 3

Esto es un poco tarde, pero hoy me encontré con este intercambio. Si observa Hacker''s Delight, 2nd Edition, hay varios algoritmos para transponer de manera eficiente matrices booleanas, comenzando en la página 141.

Son bastante eficientes: un colega mío obtuvo un factor de 10 veces más velocidad en comparación con la codificación ingenua, en un X86.

Answer 4

He agregado un nuevo visor en lugar de editar el original para que sea más visible (no desafortunadamente los derechos de comentario).

En su propia versión, agrega un requisito adicional que no está presente en el primero: tiene que funcionar en ARM Cortex-M

Encontré una solución alternativa para ARM en mi original, pero la omití porque no formaba parte de la pregunta y parecía fuera de tema (sobre todo por la etiqueta C ++).

Solución específica ARM Cortex-M:

Algunos o la mayoría de Cortex-M 3/4 tienen una región de banda de bits que se puede usar para exactamente lo que necesita, expande bits en campos de 32 bits, esta región se puede usar para realizar operaciones de bits atómicos.

Si coloca su matriz en una región con bandas de bits, tendrá un espejo ''explotado'' en la región de banda de bits donde podrá usar las operaciones de movimiento en los bits. Si crea un bucle, el compilador seguramente podrá desenrollar y optimizar para simplemente mover operaciones.

Si realmente lo desea, incluso puede configurar un controlador DMA para procesar un lote completo de operaciones de transposición con un poco de esfuerzo y descargarlo por completo de la CPU :)

Tal vez esto aún pueda ayudarte.

Answer 5

Mi sugerencia es que no realice la transposición, sino que agrega información de un bit a los datos de su matriz, indicando si la matriz está transpuesta o no.

Ahora, si quieres multiplicar una matriz de transposición con un vector, será lo mismo que multiplicar la matriz de la izquierda por el vector (y luego transponer). Esto es fácil: solo algunas operaciones xor de sus números de 8 bits.

Sin embargo, esto complica algunas otras operaciones (por ejemplo, agregar dos matrices). Pero en el comentario dices que la multiplicación es exactamente lo que quieres optimizar.

Answer 6

Mi sugerencia sería usar una tabla de búsqueda para acelerar el procesamiento.

Otra cosa a tener en cuenta es que con la definición actual de su matriz, el tamaño máximo será de 8x8 bits. Esto encaja en uint64_t para que podamos usar esto para nuestra ventaja, especialmente cuando usamos una plataforma de 64 bits.

He resuelto un ejemplo simple utilizando una tabla de búsqueda que puede encontrar a continuación y ejecutar utilizando el compilador en línea http://www.tutorialspoint.com/compile_cpp11_online.php .

Código de ejemplo

#include <iostream>
#include <bitset>
#include <stdint.h>
#include <assert.h>

using std::cout;
using std::endl;
using std::bitset;

/* Static lookup table */
static uint64_t lut[256];

/* Helper function to print array */
template<int N>
void print_arr(const uint8_t (&arr)[N]){
    for(int i=0; i < N; ++i){
        cout << bitset<8>(arr[i]) << endl;
    }
}

/* Transpose function */

template<int N>
void transpose_bitmatrix(const uint8_t (&matrix)[N], uint8_t (&transposed)[8]){
    assert(N <= 8);

    uint64_t value = 0;
    for(int i=0; i < N; ++i){
        value = (value << 1) + lut[matrix[i]];
    }

    /* Ensure safe copy to prevent misalignment issues */
    /* Can be removed if input array can be treated as uint64_t directly */
    for(int i=0; i < 8; ++i){
        transposed[i] = (value >> (i * 8)) & 0xFF;
    }
}

/* Calculate lookup table */
void calculate_lut(void){
    /* For all byte values */
    for(uint64_t i = 0; i < 256; ++i){
        auto b = std::bitset<8>(i);
        auto v = std::bitset<64>(0);

        /* For all bits in current byte */
        for(int bit=0; bit < 8; ++bit){
            if(b.test(bit)){
                v.set((7 - bit) * 8);
            }
        }

        lut[i] = v.to_ullong();
    }
}

int main()
{
    calculate_lut();

    const uint8_t matrix[] = {
        0b01010101,
        0b00110011,
        0b00001111,
    };

    uint8_t transposed[8];

    transpose_bitmatrix(matrix, transposed);
    print_arr(transposed);

   return 0;
}

Cómo funciona

su matriz 3x8 se transpondrá a una matriz de 8x3, representada en una matriz de 8x8. El problema es que desea convertir bits, su representación "horizontal" a una vertical, dividida en varios bytes.

Como mencioné anteriormente, podemos aprovechar el hecho de que la salida (8x8) siempre encajará en uint64_t. Usaremos esto para nuestra ventaja porque ahora podemos usar un uint64_t para escribir el arreglo de 8 bytes, pero también podemos usarlo para agregar, xor, etc. porque podemos realizar operaciones aritméticas básicas en un entero de 64 bits.

Cada entrada en su matriz 3x8 (entrada) tiene 8 bits de ancho, para optimizar el procesamiento, primero generamos 256 tablas de búsqueda de entrada (para cada valor de byte). La entrada en sí misma es uint64_t y contendrá una versión girada de los bits.

ejemplo:

byte = 0b01001111 = 0x4F
lut [0x4F] = 0x0001000001010101 = (uint8_t []) {0, 1, 0, 0, 1, 1, 1, 1}

Ahora para el cálculo:

Para los cálculos usamos uint64_t, pero tenga en cuenta que debajo del agua representará una matriz uint8_t [8]. Cambiamos simplemente el valor actual (comienza por 0), buscamos nuestro primer byte y lo agregamos al valor actual.

La ''magia'' aquí es que cada byte del uint64_t en la tabla de búsqueda será 1 o 0, por lo que solo establecerá el bit menos significativo (de cada byte). Al desplazar el uint64_t se desplazará cada byte, ¡siempre que nos aseguremos de no hacer esto más de 8 veces! podemos hacer operaciones en cada byte individualmente.

Cuestiones

Como alguien señaló en los comentarios: Traducir (Traducir (M))! = M así que si necesita esto necesita un trabajo adicional.

El rendimiento se puede mejorar mapeando directamente las matrices uint64_t en lugar de uint8_t [8] ya que omite una "copia segura" para evitar problemas de alineación.

Answer 7

Pasé más tiempo buscando una solución y encontré algunas buenas.

La forma SSE2

En una CPU x86 moderna, la transposición de una matriz binaria se puede hacer de manera muy eficiente con las instrucciones SSE2. Usando tales instrucciones, es posible procesar una matriz de 16 × 8.

Esta solución está inspirada en esta publicación de blog de mischasan y es muy superior a todas las sugerencias que he recibido hasta ahora sobre esta cuestión.

La idea es simple:

• #include <emmintrin.h>
• Empaque 16 variables uint8_t en un __m128i
• Usa _mm_movemask_epi8 para obtener los MSB de cada byte, produciendo un uint16_t
• Use _mm_slli_epi64 para cambiar el registro de 128 bits por uno
• Repite hasta que tengas los 8 uint16_t s

Una solución genérica de 32 bits

Desafortunadamente, también necesito hacer que esto funcione en ARM. Después de implementar la versión SSE2, sería fácil simplemente encontrar los equivalentes de NEON, pero la CPU Cortex-M (al contrario que la Cortex-A ) no tiene capacidades SIMD, por lo que NEON no es demasiado útil para mí en el momento.

NOTA : Debido a que Cortex-M no tiene aritmética nativa de 64 bits , no pude usar las ideas en ninguna respuesta que sugiera hacerlo tratando un bloque de 8x8 como uint64_t . La mayoría de los microcontroladores que tienen una CPU Cortex-M tampoco tienen demasiada memoria, por lo que prefiero hacer todo esto sin una tabla de búsqueda.

Después de pensar un poco, el mismo algoritmo se puede implementar usando aritmética simple de 32 bits y alguna codificación inteligente. De esta manera, puedo trabajar con 4 × 8 bloques a la vez. Fue sugerido por un collegaue y la magia radica en la forma en que funciona la multiplicación de 32 bits: puedes encontrar un número de 32 bits con el que puedes multiplicar y luego el MSB de cada byte se ubica uno al lado del otro en los 32 bits superiores de el resultado.

• Pack 4 uint8_t s en una variable de 32 bits
• Enmascare el primer bit de cada byte (usando 0x80808080 )
• Multiplicarlo con 0x02040810
• Tome los 4 LSB de los 32 bits superiores de la multiplicación
• En general, puede enmascarar el N en cada byte (desplazar la máscara a la derecha en N bits) y multiplicar con el número mágico, desplazado a la izquierda por N bits. La ventaja aquí es que si su compilador es lo suficientemente inteligente como para desenrollar el bucle, tanto la máscara como el "número mágico" se convierten en constantes de tiempo de compilación, por lo que al cambiarlos no se incurre en ninguna penalización de rendimiento. Hay un problema con la última serie de 4 bits, porque entonces se pierde un LSB, por lo que en ese caso tuve que cambiar la entrada de 8 bits y utilizar el mismo método que la primera serie de 4 bits.

Si haces esto con dos bloques de 4 × 8, entonces puedes hacer un bloque de 8x8 y organizar los bits resultantes para que todo vaya al lugar correcto.