Bagaimanakah Arahan SIMD Boleh Digunakan untuk Mengoptimumkan Fungsi atoi?

Cara Melaksanakan atoi Menggunakan SIMD

Dalam artikel ini, kita akan meneroka algoritma untuk melaksanakan fungsi atoi, yang menukar perwakilan rentetan daripada integer ke dalam nilai berangkanya, menggunakan arahan Single Instruction Multiple Data (SIMD). Dengan menggunakan SIMD, kami berpotensi mencapai peningkatan prestasi yang ketara dengan memproses berbilang elemen secara selari.

Algoritma

Algoritma yang dicadangkan terdiri daripada langkah berikut:

1. Memulakan vektor panjang N: Buat vektor panjang N, dengan N ialah bilangan maksimum digit yang anda mahu sokong. Mulakan vektor dengan nilai yang mewakili kuasa 10 dalam tertib menurun (cth., [10^N, 10^(N-1), ..., 10^1]).
2. Tukar setiap aksara dalam penimbal kepada integer: Tukar setiap aksara dalam rentetan input kepada nilai integer yang sepadan dan simpannya dalam yang lain vektor.
3. Darab digit bererti dengan kuasa 10: Ambil setiap elemen daripada vektor digit bererti dan darabkannya dengan elemen sepadan daripada vektor kuasa 10. Jumlahkan keputusan bagi pendaraban ini untuk mendapatkan nilai berangka rentetan.

Khususnya, untuk setiap digit dalam input rentetan:

• Keluarkan nilai digit (0 hingga 9) dengan menolak kod ASCIInya daripada 48.
• Drab nilai digit dengan kuasa sepadan 10.
• Tambahkan hasil pada jumlah yang dikira sebelumnya nilai.

Pertimbangan Pelaksanaan

Apabila melaksanakan algoritma ini dalam kod SIMD, kita boleh mengambil kesempatan daripada keselarian yang wujud dalam arahan SIMD untuk memproses berbilang digit secara serentak. Kod harus dioptimumkan untuk set arahan SIMD khusus yang digunakan (cth., SSE4.2, AVX2).

Pengoptimuman Potensi:

Adalah mungkin untuk mengoptimumkan lagi algoritma ini dengan menghapuskan keperluan untuk gelung berasingan untuk mendarab digit bererti dengan kuasa 10. Ini boleh dicapai dengan menggunakan teknik yang dipanggil "pengindeksan vektor dengan gabungan darab-tambah." Teknik ini membolehkan kami melakukan kedua-dua pengindeksan dan pendaraban dalam satu arahan, meningkatkan prestasi.

Cadangan Alternatif

Seperti yang dicadangkan oleh Peter Cordes dalam ulasan, alternatif kepada dua arahan tambah xor yang terakhir ialah menggunakan arahan imul (darab integer). Ini berpotensi untuk menjadi lebih cekap dari segi saiz dan prestasi kod.

Pelaksanaan dalam GNU Assembler dengan Intel Syntax

Berikut ialah contoh pelaksanaan algoritma dalam GNU Assembler dengan Intel sintaks:

.intel_syntax noprefix
.data
  .align 64
    ddqDigitRange: .byte  '0','9',0,0,0,0,0,0,0,0,0,0,0,0,0,0
    ddqShuffleMask:.byte  15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 
    ddqFactor1:    .word  1,10,100,1000, 1,10,100,1000  
    ddqFactor2:    .long  1,10000,100000000,0
.text    
_start:
   mov   esi, lpInputNumberString
   /* (**A**) indicate negative number in EDX */
   mov   eax, -1
   xor   ecx, ecx
   xor   edx, edx
   mov   bl,  byte ptr [esi]
   cmp   bl,  '-'
   cmove edx, eax
   cmp   bl,  '+'
   cmove ecx, eax
   sub   esi, edx
   sub   esi, ecx
   /* (**B**)remove leading zeros */
   xor   eax,eax               /* return value ZERO */
  remove_leading_zeros:
   inc   esi
   cmp   byte ptr [esi-1], '0'  /* skip leading zeros */
  je remove_leading_zeros
   cmp   byte ptr [esi-1], 0    /* catch empty string/number */
  je FINISH
   dec   esi
   /* check for valid digit-chars and invert from front to back */
   pxor      xmm2, xmm2         
   movdqa    xmm0, xmmword ptr [ddqDigitRange]
   movdqu    xmm1, xmmword ptr [esi]
   pcmpistri xmm0, xmm1, 0b00010100 /* (**C**) iim8=Unsigned bytes, Ranges, Negative Polarity(-), returns strlen() in ECX */
  jo FINISH             /* if first char is invalid return 0 - prevent processing empty string - 0 is still in EAX */
   mov al , '0'         /* value to subtract from chars */
   sub ecx, 16          /* len-16=negative to zero for shuffle mask */
   movd      xmm0, ecx
   pshufb    xmm0, xmm2 /* broadcast CL to all 16 BYTEs */
   paddb     xmm0, xmmword ptr [ddqShuffleMask] /* Generate permute mask for PSHUFB - all bytes < 0 have highest bit set means place gets zeroed */
   pshufb    xmm1, xmm0 /* (**D**) permute - now from highest to lowest BYTE are factors 10^0, 10^1, 10^2, ... */
   movd      xmm0, eax                         /* AL='0' from above */
   pshufb    xmm0, xmm2                        /* broadcast AL to XMM0 */
   psubusb   xmm1, xmm0                        /* (**1**) */
   movdqa    xmm0, xmm1
   punpcklbw xmm0, xmm2                        /* (**2**) */
   punpckhbw xmm1, xmm2
   pmaddwd   xmm0, xmmword ptr [ddqFactor1]    /* (**3**) */
   pmaddwd   xmm1, xmmword ptr [ddqFactor1]
   phaddd    xmm0, xmm1                        /* (**4**) */
   pmulld    xmm0, xmmword ptr [ddqFactor2]    /* (**5**) */
   pshufd    xmm1, xmm0, 0b11101110            /* (**6**) */
   paddd     xmm0, xmm1
   pshufd    xmm1, xmm0, 0b01010101            /* (**7**) */
   paddd     xmm0, xmm1
   movd      eax, xmm0
   /* negate if negative number */              
   add       eax, edx                          /* (**8**) */
   xor       eax, edx
  FINISH:
   /* EAX is return (u)int value */

Kesimpulan

Pelaksanaan fungsi atoi SIMD yang dioptimumkan ini boleh meningkatkan prestasi dengan ketara apabila memproses sejumlah besar data berangka. Dengan menggunakan keupayaan pemprosesan selari arahan SIMD, kami boleh mencapai masa pelaksanaan yang lebih pantas dan mengendalikan pengiraan berangka dengan lebih cekap.

Atas ialah kandungan terperinci Bagaimanakah Arahan SIMD Boleh Digunakan untuk Mengoptimumkan Fungsi atoi?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!