Bagaimana untuk melaksanakan atoi dengan cekap menggunakan arahan SIMD?

Bagaimana untuk melaksanakan atoi menggunakan SIMD?

Masalah:
Saya ingin mencuba menulis atoi pelaksanaan menggunakan arahan SIMD, untuk disertakan dalam RapidJSON. Algoritma yang saya hasilkan adalah seperti berikut:

1. Memulakan vektor panjang N mengikut cara berikut:
   [10^N..10^1]
2. Tukar setiap aksara dalam penimbal kepada integer dan letakkannya dalam vektor lain.
3. Ambil setiap nombor dalam vektor digit bererti dan darabkannya dengan nombor yang sepadan dalam vektor nombor dan jumlahkan hasilnya.

Algoritma saya betul? Adakah terdapat cara yang lebih baik? Adakah terdapat pelaksanaan rujukan untuk atoi menggunakan mana-mana set arahan SIMD?

Jawapan:
Algoritma adalah betul dan lengkap. Ia berfungsi untuk int dan uint, daripada MIN_INT=-2147483648 hingga MAX_INT=2147483647 dan dari MIN_UINT=0 hingga MAX_UINT=4294967295.

Pelaksanaan rujukan disediakan, ditulis dalam GNU Assembler>

intel Assembler. 🎜>Sifat-sifat ini kod adalah seperti berikut:

Acara '-' di hadapan menunjukkan nombor negatif (sebagai masuk akal), aksara ' ' di hadapan diabaikan
• Sifar pendahuluan (dengan atau tanpa aksara tanda ) diabaikan
• Limpahan diabaikan - nombor yang lebih besar hanya dibalut
• Hasil rentetan panjang sifar dalam nilai 0 = -0
• Aksara tidak sah dikenali dan penukaran berakhir pada aksara tidak sah pertama
• Sekurang-kurangnya 16 bait selepas sifar pendahuluan terakhir mesti boleh diakses dan kemungkinan implikasi keselamatan membaca selepas EOS diserahkan kepada pemanggil
• Hanya SSE4.2 sahaja diperlukan

Pendekatan algoritma adalah seperti berikut:

• Penunjuk kepada rentetan nombor dijangka dalam ESI
• Semak jika aksara pertama ialah '-', kemudian nyatakan jika nombor negatif dalam EDX (A)
• Semak sifar pendahuluan dan EOS (B)
• Semak rentetan untuk digit yang sah dan dapatkan strlen() aksara yang sah (C)
• Rentetan songsang supaya kuasa
  10^0 sentiasa berada pada BYTE 15
  10^1 sentiasa di BYTE 14
  10^2 sentiasa berada di BYTE 13
  10^3 sentiasa di BYTE 12
  10^4 sentiasa berada di BYTE 11
  ...
  dan tutup semua aksara berikut (D)
• Tolak tepu '0' daripada setiap satu daripada 16 aksara yang mungkin (1)
• Ambil 16 nilai bait berturut-turut dan bahagikannya kepada WORD
  dalam dua XMM-register (2)
  P O N M L K J I | H G F E D C B A ->
  H G F E | D C B A (XMM0)
  P O N M | L K J I (XMM1)
• Darab setiap WORD dengan modulo nilai tempatnya 10000 (1,10,100,1000)
  (faktor yang lebih kecil daripada MAX_WORD, 4 faktor setiap QWORD/separuhXMM)
  (🎜>(🎜> 2) supaya kita boleh secara mendatar gabungkan dua kali sebelum satu lagi darab.Arahan PMADDWD boleh melakukan ini dan langkah seterusnya:
  
Tambahkan secara mendatar PERKATAAN bersebelahan dengan DWORD (
• 3)H
  1000 G 100 F10 E1 | D1000 C100 B10 A1 (XMM0)P
  1000 O100 N10 M1 | L1000 K100 J10 I1 (XMM1)
Tambahkan DWORD bersebelahan secara mendatar daripada XMM0 dan XMM1 kepada XMM0 (
• 4)xmmDst[31-0] = xmm0[63-32] xmm0[31-0]
  xmmDst[63-32] = xmm0[127-96] xmm0[95-64]
  xmmDst[95-64] = xmm1[63-32] xmm1[31-0]
  xmmDst[127-96] = xmm1[127-96] xmm1[95-64]
  
Nilai dalam XMM0 didarab dengan faktor (
• 5)P
  1000 O100 N10 J1 (faktor DWORD 1000000000000 = terlalu besar untuk DWORD, tetapi mungkin berguna untuk rentetan nombor QWORD)L
  1000 K100 J10 I1 (faktor DWORD 10000)
  1000 G100 F10 E1 (faktor DWORD 10000)D
  1000 C100 B10 A1 (faktor DWORD 1)
• Langkah terakhir ialah menambah empat ini DWORD bersama 2

  PHADDD dicontohi oleh 2(PSHUFD PADDD)

  xmm0[31-0] = xmm0[63-32] xmm0[31-0] (
  • 6)xmm0[63-32] = xmm0[127-96] xmm0[95-64]
    (QWORD atas mengandungi perkara yang sama dan diabaikan)
    
  xmm0[31-0] = xmm0[63-32] xmm0[31-0 ] (
  • 7)
Jika nombor itu negatif (ditunjukkan dalam EDX sebanyak 000...0=pos atau 111...1=neg), tolakkannya (
• 8)

Hasil Analisis Throughput Intel-IACA untuk Haswell 32-bit:

Laporan Analisis Laluan

Hasil Sekatan: 16.10 Kitaran Throughput Bottleneck: InterIteration

Pengikatan Port Dalam Kitaran Setiap Lelaran:

| Pelabuhan | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |

| Kitaran | 9.5 0.0 | 10.0 | 4.5 4.5 | 4.5 4.5 | 0.0 | 11.1 | 11.4 | 0.0 |

N - nombor port atau bilangan kitaran konflik sumber menyebabkan kelewatan, DV - Paip pembahagi (pada port 0)
D - Paip pengambilan data (pada port 2 dan 3), CP - pada laluan kritikal
F - Gabungan Makro dengan arahan sebelumnya berlaku

• • arahan micro-ops tidak terikat pada port
    ^ - Micro Fusion berlaku

    - ESP Tracking sync uop telah dikeluarkan

    @ - Arahan SSE mengikut arahan AVX256, berpuluh-puluh kitaran penalti adalah dijangka
    ! - arahan tidak disokong, tidak diambil kira dalam Analisis

| Bilangan | Tekanan pelabuhan dalam kitaran | |

| Ups | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | |

| 0* | | | | | | | | | | xor eax, eax
| 0* | | | | | | | | | | xor ecx, ecx
| 0* | | | | | | | | | | xor edx, edx
| 1 | | 0.1 | | | | | 0.9 |

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan atoi dengan cekap menggunakan arahan SIMD?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!