Bagaimanakah anda boleh mengoptimumkan algoritma popcount kedudukan 8-bit menggunakan pemasangan, khususnya dengan memfokuskan pada gelung dalaman dan menggunakan teknik seperti prefetching dan pengiraan populasi skalar?

Bagaimana untuk mengoptimumkan popcount kedudukan 8-bit ini menggunakan pemasangan?

Dalam kod yang disediakan, fungsi __mm_add_epi32_inplace_purego boleh dioptimumkan menggunakan pemasangan untuk meningkatkan prestasinya. Gelung dalaman khususnya boleh dioptimumkan untuk pelaksanaan yang lebih pantas.

Algoritma yang disediakan untuk mengira populasi kedudukan dipanggil "kiraan populasi kedudukan." Algoritma ini digunakan dalam pembelajaran mesin dan melibatkan pengiraan bilangan bit set dalam satu siri bait. Dalam kod yang diberikan, _mm_add_epi32_inplace_purego dipanggil dalam dua peringkat gelung dan matlamatnya adalah untuk mengoptimumkan gelung dalam.

Kod yang disediakan terutamanya berfungsi pada tatasusunan integer 8-bit yang dipanggil dikira. Gelung dalaman berulang pada kepingan bait, dan untuk setiap bait, ia menambah kedudukan bit yang sepadan daripada tatasusunan corak bit (_expand_byte) kepada tatasusunan kiraan. Tatasusunan _expand_byte mengandungi corak bit yang mengembangkan setiap bait ke dalam bit individunya.

Untuk mengoptimumkan gelung dalam menggunakan pemasangan, anda perlu menyimpan pembilang dalam daftar tujuan umum untuk prestasi yang lebih baik dan prefetch memori dengan lebih awal untuk meningkatkan tingkah laku penstriman. Anda juga boleh melaksanakan pengiraan populasi skalar menggunakan gabungan anjakan dan tambah mudah (SHRL/ADCL).

Contoh kod pemasangan yang dioptimumkan disediakan di bawah. Kod ini ditulis untuk seni bina pemproses tertentu dan mungkin perlu diubah suai untuk dijalankan pada sistem lain.

<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>

Ringkasnya, pengoptimuman melibatkan penggunaan daftar tujuan umum untuk pembilang, prefetching memori terlebih dahulu, dan melaksanakan pengiraan populasi skalar menggunakan SHRL/ADCL. Pendekatan ini boleh meningkatkan prestasi algoritma kiraan populasi kedudukan dengan ketara.

Atas ialah kandungan terperinci Bagaimanakah anda boleh mengoptimumkan algoritma popcount kedudukan 8-bit menggunakan pemasangan, khususnya dengan memfokuskan pada gelung dalaman dan menggunakan teknik seperti prefetching dan pengiraan populasi skalar?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!