array - eigen vector c++




Comment transposeriez-vous une matrice binaire? (5)

J'ai des matrices binaires en C ++ que je représente avec un vecteur de valeurs de 8 bits.

Par exemple, la matrice suivante:

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

est représenté comme:

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

La raison pour laquelle je le fais de cette façon est parce qu'alors le calcul du produit d'une telle matrice et d'un vecteur 8 bits devient vraiment simple et efficace (juste un AND binaire et un calcul de parité, par rangée), ce qui est beaucoup mieux que calculer chaque bit individuellement.

Je cherche maintenant un moyen efficace de transposer une telle matrice, mais je n'ai pas été capable de comprendre comment le faire sans avoir à calculer manuellement chaque bit.

Juste pour clarifier, pour l'exemple ci-dessus, je voudrais obtenir le résultat suivant de la transposition:

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

NOTE : Je préférerais un algorithme qui peut le calculer avec des matrices de taille arbitraire mais je m'intéresse aussi aux algorithmes qui ne peuvent gérer que certaines tailles.


C'est un peu tard, mais j'ai juste trébuché sur cet échangeur aujourd'hui. Si vous regardez Hacker's Delight, 2ème édition, il existe plusieurs algorithmes pour transposer efficacement les tableaux booléens, à partir de la page 141.

Ils sont assez efficaces: un de mes collègues a obtenu un facteur d'accélération de 10X par rapport au codage naïf, sur un X86.


J'ai ajouté un nouveau raccourci au lieu d'éditer mon original pour le rendre plus visible (aucun droit de commentaire malheureusement).

Dans votre propre réponse, vous ajoutez une exigence supplémentaire non présente dans le premier: Elle doit fonctionner sur ARM Cortex-M

J'ai trouvé une solution alternative pour ARM dans ma version originale, mais je l'ai omise car elle ne faisait pas partie de la question et semblait hors sujet (principalement à cause de la balise C ++).

Solution spécifique ARM Cortex-M:

Certains ou la plupart des Cortex-M 3/4 ont une région de bandes qui peut être utilisée pour exactement ce dont vous avez besoin, elle étend les bits dans des champs de 32 bits, cette région peut être utilisée pour effectuer des opérations de bits atomiques.

Si vous placez votre tableau dans une région en bande, il aura un miroir «éclaté» dans la région de la bande passante où vous pouvez simplement utiliser les opérations de déplacement sur les bits eux-mêmes. Si vous faites une boucle, le compilateur sera sûrement capable de se dérouler et d'optimiser pour simplement déplacer les opérations.

Si vous le voulez vraiment, vous pouvez même configurer un contrôleur DMA pour traiter un lot entier d'opérations de transposition avec un peu d'effort et le décharger entièrement du CPU :)

Peut-être que cela pourrait encore vous aider.


Ma suggestion est que, vous ne faites pas la transposition, vous ajoutez plutôt des informations d'un bit à vos données matricielles, indiquant si la matrice est transposée ou non.

Maintenant, si vous voulez multiplier une matrice transposée avec un vecteur, ce sera la même chose que multiplier la matrice sur la gauche par le vecteur (et ensuite transposer). C'est facile: juste quelques opérations xor de vos nombres de 8 bits.

Cela rend cependant certaines autres opérations compliquées (par exemple en ajoutant deux matrices). Mais dans le commentaire, vous dites que la multiplication est exactement ce que vous voulez optimiser.


Ma suggestion serait d'utiliser une table de recherche pour accélérer le traitement.

Une autre chose à noter est qu'avec la définition actuelle de votre matrice, la taille maximale sera de 8x8 bits. Cela correspond à un uint64_t donc nous pouvons l'utiliser à notre avantage en particulier lorsque vous utilisez une plate-forme 64 bits.

J'ai élaboré un exemple simple en utilisant une table de recherche que vous pouvez trouver ci-dessous et exécuter en utilisant: http://www.tutorialspoint.com/compile_cpp11_online.php compilateur en ligne.

Exemple de code

#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;
}

Comment ça marche

votre matrice 3x8 sera transposée en une matrice 8x3, représentée dans un tableau 8x8. Le problème est que vous voulez convertir des bits, votre représentation "horizontale" en une verticale, divisée sur plusieurs octets.

Comme je l'ai mentionné ci-dessus, nous pouvons profiter du fait que la sortie (8x8) sera toujours dans un uint64_t. Nous utiliserons ceci à notre avantage car nous pouvons maintenant utiliser uint64_t pour écrire le tableau de 8 octets, mais nous pouvons aussi l'utiliser pour ajouter, xor, etc. parce que nous pouvons effectuer des opérations arithmétiques de base sur un entier de 64 bits.

Chaque entrée de votre matrice 3x8 (entrée) a une largeur de 8 bits, pour optimiser le traitement, nous générons d'abord une table de correspondance de 256 entrées (pour chaque valeur d'octet). L'entrée elle-même est un uint64_t et contiendra une version pivotée des bits.

Exemple:

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

Maintenant pour le calcul:

Pour les calculs, nous utilisons uint64_t mais gardons à l'esprit que sous l'eau il représentera un tableau uint8_t [8]. Nous décalons simplement la valeur actuelle (commence par 0), recherchons notre premier octet et l'ajoutons à la valeur actuelle.

La 'magie' ici est que chaque octet de l'uint64_t dans la table de recherche sera soit 1 ou 0, donc il ne fera que définir le bit le moins significatif (de chaque octet). Le déplacement de l'uint64_t décalera chaque octet, tant que nous nous assurons que nous ne le faisons pas plus de 8 fois! nous pouvons faire des opérations sur chaque octet individuellement.

Problèmes

Comme quelqu'un l'a noté dans les commentaires: Traduire (Traduire (M))! = M donc si vous en avez besoin, vous avez besoin de travail supplémentaire.

Perfomance peut être amélioré en mappant directement les tableaux de uint64_t au lieu de uint8_t [8] car il omet une "copie sécurisée" pour éviter les problèmes d'alignement.


Voici le texte de l'email de Jay Foad à propos de la transposition de la matrice booléenne rapide:

Le cœur de l'algorithme de transposition booléenne est une fonction que j'appellerai transpose8x8 qui transpose une matrice booléenne 8x8 dans un mot de 64 bits (dans l'ordre majeur de MSB à LSB). Pour transposer une matrice rectangulaire dont la largeur et la hauteur sont des multiples de 8, divisez-la en 8x8 blocs, transposez chacun individuellement et stockez-les à l'endroit approprié dans la sortie. Pour charger un bloc 8x8, vous devez charger 8 octets individuels et les déplacer et les transformer en un mot de 64 bits. Même chose pour le stockage.

Une implémentation C simple de transpose8x8 repose sur le fait que tous les bits de toute ligne diagonale parallèle à la diagonale principale se déplacent à la même distance haut / bas et gauche / droite. Par exemple, tous les bits juste au-dessus de la diagonale de tête doivent se déplacer d'une place vers la gauche et d'une place vers le bas, c'est-à-dire 7 bits vers la droite dans le mot de 64 bits. Cela conduit à un algorithme comme celui-ci:

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

}

Cela s'exécute environ 10 fois plus vite que l'implémentation précédente, qui a copié chaque bit individuellement de l'octet source en mémoire et l'a fusionné dans l'octet de destination en mémoire.

Alternativement, si vous avez des instructions PDEP et PEXT vous pouvez implémenter un shuffle parfait, et l'utiliser pour faire la transposition comme mentionné dans Hacker's Delight. C'est beaucoup plus rapide (mais je n'ai pas de timing pratique):

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

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

L'instruction vgbbd de POWER vgbbd effectivement l'ensemble de transpose8x8 dans une seule instruction (et comme c'est une instruction vectorielle de 128 bits, elle le fait deux fois, indépendamment, sur les 64 bits les plus bas et les 64 bits les plus hauts). Cela a donné environ 15% d'accélération par rapport à la mise en œuvre de la plaine C. (Seulement 15% car, bien que le bit twiddling soit beaucoup plus rapide, le temps d'exécution total est maintenant dominé par le temps nécessaire pour charger 8 octets et les assembler dans l'argument de transpose8x8 , et prendre le résultat et le stocker comme 8 octets.)





transpose