Esecuzione efficiente dell'espressione booleana su bitmap in C o C++

Question

Qual è il modo più efficiente di eseguire un'espressione booleana su una bitmap in C o C++? Ad esempio, supponiamo di avere una bitmap a 4 bit (a, b, c, d). Ora, diciamo che ho un'espressione booleana semplice come (a AND b) OR (c AND d). Come dovrei rappresentare l'espressione booleana in modo da poterla applicare efficacemente alla mia bitmap? Sto cercando una soluzione generica che possa essere applicata a qualsiasi espressione booleana, non solo a quella fornita come esempio. In altre parole, sto cercando un modo per "compilare" l'espressione booleana in un'altra struttura dati che potrebbe essere utilizzata per ridurre in modo efficiente la mia bitmap in un booleano.

La struttura bitmap è il risultato di operazioni di filtro sui record di un database. Ogni record ha la propria bitmap e ogni bit in una bitmap è il risultato di una singola regola di filtro. L'espressione booleana viene utilizzata per combinare queste regole di filtro per decidere se il record deve essere incluso nei risultati di una query di database. Possono esistere fino a 64 regole di filtro individuali che possono essere combinate mediante l'operazione booleana, quindi la bitmap può essere rappresentata come unsigned long long int se necessario.

La soluzione deve essere efficiente in termini di velocità e non deve alterare la struttura bitmap. La conversione dell'espressione booleana in un'altra struttura non deve essere efficiente in termini di memoria, né veloce, perché può essere memorizzata nella cache (almeno nel mio attuale caso d'uso). La riduzione della bitmap con l'espressione booleana trasformata dovrebbe essere sia rapida che efficiente in termini di memoria.

Note:

• L'espressione booleana è solo utilizzando nidificato operazioni AND e OR (senza IF).
• La soluzione deve assumere la disponibilità di una CPU a 64 bit.
• La soluzione non deve essere dipendente dalla CPU (oltre a indirizzamento a 64 bit).
• La soluzione non deve presupporre la disponibilità di nessun altro particolare hardware (ad esempio GPU).
• Tutte le bitmap sono in memoria.
• Può esserci un numero molto elevato di bitmap (miliardi).
• Le bitmap vengono aggiornate una alla volta.

Answer 1

È possibile rappresentare l'espressione come un albero binario e potrebbe anche utilizzare due classi per i due tipi di nodo. È anche possibile parametrizzare ciascun nodo con l'operazione, ma non ne vale la pena. Forse crei anche un nodo Not con un input. Gli input ai nodi sono posti nella tua bitmap o in altri nodi, quindi sto creando una sottoclasse per il primo caso che prende l'indice nella bitmap come parametro. Hai finito questo codice scrivendo la funzione valore per il nodo E e completando il nodo Or.

typedef unsigned long long Bitmap; 
Bitmap bitmap; 

struct Node { 
    virtual bool value()=0; 
}; 

struct AbsNode : public Node { 
    int bit; 
    bool value() {return (bitmap>>bit)&1; } 
} 

struct AndNode : public Node { 
    Node *operandA, *operandB; 
    etc. 
} 

Answer 2

Il metodo più efficace di usare AND e OR operazioni sulle immagini bitmap è di usare assistenza hardware. Molti processori grafici possono eseguire operazioni su due bitmap. Non esiste alcuna operazione di libreria standard C++ per questo.

È necessario eseguire l'operazione su ciascun bit, byte, parola o doppia parola nelle bitmap.

Il prossimo metodo efficiente di velocità consiste nello srotolare il loop. Le istruzioni per le filiali scaricano i cicli di esecuzione (che potrebbero essere utilizzati per le istruzioni sui dati) e possono eliminare il tempo di eliminazione della pipeline di istruzioni ricaricandolo.

È inoltre possibile ottenere un po 'di efficienza utilizzando efficacemente la cache dei dati del processore. Carica una serie di variabili, esegui l'operazione, memorizza il risultato, ripeti.

È inoltre necessario recuperare i gruppi utilizzando la dimensione della parola del processore. Un processore a 32 bit ama recuperare 32 bit alla volta. Quindi questo ti darebbe 8 serie di pixel a 4 bit caricati con un recupero. Altrimenti, dovresti recuperare 8 bit alla volta, il che si traduce in 4 feti di 8 bit rispetto a 1 fetch di 32-bit.

Ecco l'algoritmo di base:

uint8_t * p_bitmap_a = &Bitmap_A[0]; 
uint8_t * p_bitmap_b = &Bitmap_B[0]; 
uint8_t * p_bitmap_c = &Bitmap_C[0]; 

// C = A AND B 

for (unsigned int i = 0; i < bitmap_size/4; ++i) 
{ 
    uint32_t a = *((uint32_t*) p_bitmap_a); 
    uinte2_t b = *((uint32_t*) p_bitmap_b); 
    uint32_t c = a & b; 
    *((uint32_t *) p_bitmap_c) = c; 
    p_bitmap_a += sizeof(uint32_t); 
    p_bitmap_b += sizeof(uint32_t); 
    p_bitmap_c += sizeof(uint32_t); 
} 

Edit 1:
Il processore potrebbe avere istruzioni che possono aiutare con le operazioni. Ad esempio, il processore ARM7 può caricare molti registri dalla memoria con un'istruzione. Ricerca il set di istruzioni del tuo processore. Potrebbe essere necessario utilizzare il linguaggio assembly inline per sfruttare le istruzioni specifiche del processore.

Edit 2: Threading & processo parallela.

A meno che le immagini bitmap non siano enormi, il sovraccarico del mantenimento di più thread di esecuzione o esecuzione parallela potrebbe superare il vantaggio. Ad esempio, se il sovraccarico di sincronizzazione con un altro core della CPU è 200 ms e l'elaborazione della bitmap senza interruzioni è di 1000 ms, si è sprecato tempo utilizzando l'elaborazione parallela sulla bitmap singola (1200 ms per avere un altro processo di core bitmap).

Se sono presenti molti bitmap, si può guadagnare tempo utilizzando elaborazione in parallelo o fili multipli:

1. Un filo recupera bitmap dal database in memoria (buffer).
2. Un altro thread elabora i bitmap e i negozi in un buffer in uscita.
3. Un terzo processo scrive le bitmap bufferizzate nel database.

Se si prelevano bitmap da un'origine esterna, ad esempio un database, questo I/O sarà il collo di bottiglia. Questa è la parte da ottimizzare o spoolare.

Answer 3

Se le bitmap sono GARANTITE devono essere sempre 4 bit, quindi si inseriranno nei 4 bit inferiori di un carattere e saranno presenti solo 16 valori possibili per qualsiasi bitmap.

Per una particolare espressione booleana, la si valuta quindi per ognuna delle sedici combinazioni di bit possibili, che fornisce un set di sedici bit di risultato. assemblarli in un po 'int sedici: false, false, false, false nel bit pari a zero, false, false, false, true nel bit 1, e così via.

Ora, per una bitmap arbitraria contro un booleano arbitrario, il vostro controllo diventa:

1. Trattare il bitmap come 4 bit int, valutare 1 << (4 bit int).
2. Prendere il risultato di questo turno e utilizzare l'operatore C++ & per verificare il valore int con cache a 16 bit dell'operazione booleana.

Questo restituirà == 0 per false e != 0 per true.

Riducendolo a due istruzioni: uno shift e uno and è il più veloce che posso vedere a farlo.

Questo presuppone che non ci sono abbastanza piccolo numero di operazione booleana che si sta applicando su un over, la messa a punto per test booleano sarà essere costoso, ma dal momento che si sta parlando di miliardi di bitmap, sto supponendo che userai la stessa operazione booleana su molti molti bitmap.