Wie können Sie einen 8-Bit-Positions-Popcount-Algorithmus mithilfe von Assembler optimieren, indem Sie sich insbesondere auf die innere Schleife konzentrieren und Techniken wie Prefetching und skalare Populationszählung verwenden?

Wie optimiert man diesen 8-Bit-Positions-Popcount mithilfe von Assembly?

Im bereitgestellten Code kann die Funktion __mm_add_epi32_inplace_purego mithilfe von Assembly optimiert werden seine Leistung verbessern. Insbesondere die innere Schleife kann für eine schnellere Ausführung optimiert werden.

Der bereitgestellte Algorithmus zum Zählen der Positionspopulation wird als „Positionspopulationszählung“ bezeichnet. Dieser Algorithmus wird beim maschinellen Lernen verwendet und beinhaltet das Zählen der Anzahl gesetzter Bits in einer Reihe von Bytes. Im angegebenen Code wird _mm_add_epi32_inplace_purego in zwei Schleifenebenen aufgerufen, und das Ziel besteht darin, die innere Schleife zu optimieren.

Der bereitgestellte Code funktioniert hauptsächlich mit einem Array von aufgerufenen 8-Bit-Ganzzahlen zählt. Die innere Schleife durchläuft ein Byte-Slice und fügt für jedes Byte die entsprechenden Bitpositionen aus einem Array von Bitmustern (_expand_byte) zum Counts-Array hinzu. Das _expand_byte-Array enthält Bitmuster, die jedes Byte in seine einzelnen Bits erweitern.

Um die innere Schleife mithilfe von Assembly zu optimieren, müssen Sie die Zähler für eine bessere Leistung in Allzweckregistern behalten und Rufen Sie den Speicher rechtzeitig vorab ab, um das Streaming-Verhalten zu verbessern. Sie können die skalare Populationszählung auch mithilfe einer einfachen Shift-and-Add-Kombination (SHRL/ADCL) implementieren.

Ein Beispiel für optimierten Assemblercode finden Sie unten. Dieser Code wurde für eine bestimmte Prozessorarchitektur geschrieben und muss möglicherweise geändert werden, um auf anderen Systemen ausgeführt zu werden.

<code class="assembly">#include "textflag.h"

// func PospopcntReg(counts *[8]int32, buf []byte)
TEXT ·PospopcntReg(SB),NOSPLIT,-32
    MOVQ counts+0(FP), DI
    MOVQ buf_base+8(FP), SI     // SI = &buf[0]
    MOVQ buf_len+16(FP), CX     // CX = len(buf)

    // load counts into register R8--R15
    MOVL 4*0(DI), R8
    MOVL 4*1(DI), R9
    MOVL 4*2(DI), R10
    MOVL 4*3(DI), R11
    MOVL 4*4(DI), R12
    MOVL 4*5(DI), R13
    MOVL 4*6(DI), R14
    MOVL 4*7(DI), R15

    SUBQ , CX            // pre-subtract 32 bit from CX
    JL scalar

vector: VMOVDQU (SI), Y0        // load 32 bytes from buf
    PREFETCHT0 384(SI)      // prefetch some data
    ADDQ , SI            // advance SI past them

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R15            // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R14            // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R13            // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R12            // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R11            // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R10            // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R9         // add to counter
    VPADDD Y0, Y0, Y0       // shift Y0 left by one place

    VPMOVMSKB Y0, AX        // move MSB of Y0 bytes to AX
    POPCNTL AX, AX          // count population of AX
    ADDL AX, R8         // add to counter

    SUBQ , CX
    JGE vector          // repeat as long as bytes are left

scalar: ADDQ , CX            // undo last subtraction
    JE done             // if CX=0, there's nothing left

loop:   MOVBLZX (SI), AX        // load a byte from buf
    INCQ SI             // advance past it

    SHRL , AX         // CF=LSB, shift byte to the right
    ADCL , R8         // add CF to R8

    SHRL , AX
    ADCL , R9         // add CF to R9

    SHRL , AX
    ADCL , R10            // add CF to R10

    SHRL , AX
    ADCL , R11            // add CF to R11

    SHRL , AX
    ADCL , R12            // add CF to R12

    SHRL , AX
    ADCL , R13            // add CF to R13

    SHRL , AX
    ADCL , R14            // add CF to R14

    SHRL , AX
    ADCL , R15            // add CF to R15

    DECQ CX             // mark this byte as done
    JNE loop            // and proceed if any bytes are left

    // write R8--R15 back to counts
done:   MOVL R8, 4*0(DI)
    MOVL R9, 4*1(DI)
    MOVL R10, 4*2(DI)
    MOVL R11, 4*3(DI)
    MOVL R12, 4*4(DI)
    MOVL R13, 4*5(DI)
    MOVL R14, 4*6(DI)
    MOVL R15, 4*7(DI)

    VZEROUPPER          // restore SSE-compatibility
    RET</code>

Zusammenfassend lässt sich sagen: Die Optimierung umfasst die Verwendung von Allzweckregistern für Zähler. Speicher vorab abrufen und skalare Bevölkerungszählung mit SHRL/ADCL implementieren. Dieser Ansatz kann die Leistung des Positionspopulationszählalgorithmus erheblich verbessern.

Das obige ist der detaillierte Inhalt vonWie können Sie einen 8-Bit-Positions-Popcount-Algorithmus mithilfe von Assembler optimieren, indem Sie sich insbesondere auf die innere Schleife konzentrieren und Techniken wie Prefetching und skalare Populationszählung verwenden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!