ottimizzazioni, uso di assembler inline

International Italiano Generale
1

Ho aperto un topic sui display a matrice di led alcuni giorni fa, ma vorrei generalizzare il problema. C'è qualcuno che si sia "scontrato" con le ottimizzazioni spinte per sfruttare la seppur poca potenza di calcolo degli AVR?

Da un paio di giorni sto cercando di capire se il seguente polinomio sia ottimizzabile:

addr = x + 64*(x>>5) + 16*(x>>4) + 64*(y>>3);

...soluzioni migliori non ne trovo in realtà, e così ho cercato di capire se fosse possibile ottimizzare riscrivendo il tutto in assembler inline...

  __asm__ __volatile__ (
    "mov __tmp_reg__, %2"     "\n\t"
    "ldi %0, 0x80"            "\n\t"
    "andi %2, 0x7"            "\n\t"
    "__shift_0:"              "\n\t"
    "asr %0"                  "\n\t"
    "dec %2"                  "\n\t"
    "brpl __shift_0"          "\n\t"
    "mov %2, __tmp_reg__"     "\n\t"

    "lsr %2"                  "\n\t"
    "lsr %2"                  "\n\t"
    "lsr %2"                  "\n\t"

    "ldi %1, 0x40"            "\n\t"
    "mul %1, %2"              "\n\t"
    "movw %1,r0"              "\n\t"

    "add %A1, %3"             "\n\t"
    "adc %B1, 0"             "\n\t"

    "lsr %3"                  "\n\t"
    "lsr %3"                  "\n\t"
    "lsr %3"                  "\n\t"
    "lsr %3"                  "\n\t"
    "ldi r16, 0x10"            "\n\t"
    "mul r16, %3"              "\n\t"

    "add %A1, r0"             "\n\t"
    "adc %B1, r1"             "\n\t"

    "lsr %3"                  "\n\t"
    : "=r" (bitval), "=r" (addr)
    : "r" (y), "r" (x)
    : "r0", "r1", "r16"
  );

Il codice di cui sopra è incompleto, manca la parte riguardante il monomio 16*(x>>4) (mentre la parte iniziale riguarda un'altra operazione, cioè bitval = 128 >> (y&7)). Non l'ho continuato perché procedevo per passi ed eseguivo di volta in volta un benchmark... ottenendo gli stessi risultati che in C. A queste condizioni usare l'assembler è solo una perdita di tempo e complicazione inutile (può essere di esercizio, ammesso che tale esercizio abbia qualche scopo...).

La domanda è: è possibile ottimizzare dei monomi con forma n*(x>>s)? Purtroppo l'AVR ha istruzioni di shift logico o aritmetico che possono eseguire lo shift di un solo bit, quindi l'istruzione va ripetuta o reiterata...

2

Negli assembly che conosco ho sempre trovato le operazioni di shift e/o rotate per singoli bit. Quindi non penso tu possa fare di meglio.

Inoltre ottimizzazioni su operazioni tipo somme, moltiplicazioni e spostamenti di bit sono abbastanza semplici in C quindi la differenza con l'assembly è poca. Casomai l'assembly viene usato in altri campi, dove la massima potenza di calcolo diventa un fattore fondamentale, come ad esempio nella generazione dei segnali video (vedi ad esempio il progetto TvText) oppure in algoritmi basati esclusivamente su operazioni condotte a livello di bit (vedi algoritmi crittografici).

3

leo72:
Negli assembly che conosco ho sempre trovato le operazioni di shift e/o rotate per singoli bit. Quindi non penso tu possa fare di meglio.

Infatti :frowning: Ho provato a dare un'occhiata all'assembler generato dal compilatore e gli shift vengono tradotti in shift di singoli bit reiterati. E' una operazione tempo esponenziale, computazionalmente inefficiente. Peccato non abbiano implementato un secondo parametro negli AVR, sarebbe stato utile nelle operazioni bitwise... in altri RISC è prevista l'entità dello shift.

Comunque sia, sono riuscito a eliminare tutti gli shift:

addr = x + (x & ~15) + 2*(x & ~31) + 8*(y & ~7);

...guadagnando il 50% di efficienza in termini di tempo CPU (per quanto riguarda il programmino nel suo complesso - che pilota un display dot matrix - sono passato da 83fps a 125fps)

Ne rimane ancora uno, ma non trovo soluzione (bitval = 128 >> (y & 7))...

4

lonewolf:
Infatti :frowning: Ho provato a dare un'occhiata all'assembler generato dal compilatore

Non per pedanteria, ma il linguaggio si chiama "assembly"; l'assembler è il software che trasforma l'assembly in linguaggio macchina :wink:

addr = x + (x & ~15) + 2*(x & ~31) + 8*(y & ~7);

Mi spieghi questo codice?
"~" cosa fa esattamente?

5

leo72:

lonewolf:
Infatti :frowning: Ho provato a dare un'occhiata all'assembler generato dal compilatore

Non per pedanteria, ma il linguaggio si chiama "assembly"; l'assembler è il software che trasforma l'assembly in linguaggio macchina :wink:

addr = x + (x & ~15) + 2*(x & ~31) + 8*(y & ~7);

Mi spieghi questo codice?
"~" cosa fa esattamente?

"~" è un not (bitwise, non logico come "!")

Con &~ (and not) applico una bitmask quindi prendo in considerazione solo i bits di x tranne quelli mascherati. In effetti prima eseguivo lo shift prima a destra e poi a sinistra (in effetti moltiplicare per multipli di due o eseguire shift a sinistra è equivalente)... praticamente mascheravo dei bits...
Volendo quelle maschere si possono scrivere come ~15 = 240, ~31 = 224, ~7 = 248 ma sarebbero ancor meno "human readable" :stuck_out_tongue:

6

Ah, ok. Non conosco molto a fondo il C/C++.
Grazie del chiarimento.