SIMD 명령어를 사용하여 atoi를 효율적으로 구현하는 방법은 무엇입니까?

SIMD를 사용하여 atoi를 구현하는 방법은 무엇입니까?

문제:
atoi를 작성해 보고 싶습니다. RapidJSON에 포함될 SIMD 명령어를 사용한 구현입니다. 내가 생각해낸 알고리즘은 다음과 같습니다.

1. 다음 방식으로 길이 N의 벡터를 초기화합니다.
   [10^N..10^1]
2. 변환 버퍼의 각 문자를 정수로 변환하고 이를 다른 벡터에 배치합니다.
3. 유효 숫자 벡터의 각 숫자를 가져와서 숫자 벡터에서 숫자를 일치시키고 결과를 합산합니다.

제 알고리즘이 맞나요? 더 좋은 방법이 있나요? SIMD 명령어 세트를 사용하는 atoi에 대한 참조 구현이 있습니까?

답변:
알고리즘이 정확하고 완전합니다. MIN_INT=-2147483648에서 MAX_INT=2147483647까지, MIN_UINT=0에서 MAX_UINT=4294967295까지 int 및 uint에서 작동합니다.

인텔 구문을 사용하여 GNU Assembler로 작성된 참조 구현이 제공됩니다.

이 코드의 속성은 다음과 같습니다. 다음:

• 앞의 '-' 문자는 음수(합리적임)를 나타내고, 앞의 ' ' 문자는 무시됩니다.
• 앞의 0(기호 문자 유무와 상관없이)은 무시됩니다.
• 오버플로는 무시됩니다. 더 큰 숫자는 그냥 둘러싸게 됩니다.
• 길이가 0인 문자열은 값 0이 됩니다 = -0
• 잘못된 문자가 인식되고 첫 번째 잘못된 문자에서 변환이 종료됩니다.
• 마지막 선행 0 이후 최소 16바이트에 액세스할 수 있어야 하며 EOS 이후 읽기에 보안 영향이 있을 수 있습니다. 호출자
• SSE4.2만 필요합니다

알고리즘의 접근 방식은 다음과 같습니다. 다음:

• ESI에서 숫자 문자열에 대한 포인터가 필요합니다
• 첫 번째 문자가 '-'인지 확인한 다음 EDX에서 음수인지 표시합니다(A)
• 앞에 오는 0과 EOS를 확인하세요(B)
• 문자열이 유효한지 확인하세요 숫자를 입력하고 유효한 문자(C)
• 
  10^0의 거듭제곱이 항상 BYTE 15
  10^1이 되도록 문자열을 역순으로 가져옵니다.
  10^1 BYTE 14
  10^2는 항상 BYTE 13
  10^3은 항상 BYTE 12
  10^4는 항상 BYTE 11
  ... 다음 문자를 모두 마스크합니다(D
)
• 각 문자에서 포화된 '0'을 뺍니다. 16개의 가능한 문자 중 (1
)
• 
  Take 16개의 연속 바이트 값을 두 개의 XMM 레지스터(2)
  에서
  워드로 분할합니다. P O N M L K JI | H G F E D C B A ->
  H G F E | DC B A (XMM0)
P O N M | L K J I (XMM1)
• 
  각 WORD에 자릿값 모듈로 10000(1,10,100,1000)을 곱합니다.
  (MAX_WORD보다 작은 인수, QWORD/halfXMM당 4개의 인수)( 2
  ) 가로로 두 번 결합한 다음 다른 것보다 먼저 결합할 수 있습니다. 곱하기.
PMADDWD 명령으로 이 작업과 다음 단계를 수행할 수 있습니다.
• 인접한 WORD를 DWORD에 수평으로 추가(3
  )H1000G100 에10 에1 | D1000C100B10A
  1(XMM0)P1000O100N10M1 | L1000K100J10 I
1(XMM1)
• XMM0 및 XMM1에서 XMM0까지 인접한 DWORD를 수평으로 추가(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]
• XMM0의 값에 인수(5
  )P1000O100N10M1(DWORD 요소 1000000000000 = DWORD에는 너무 크지만 QWORD 숫자 문자열에는 유용할 수 있음)
  L1000 K100 J10 I1(DWORD 인수 100000000)
  H 1000G100 F10 E1(DWORD 인수 10000)
  D1000 C100 B10 A1(DWORD 인수 1)

• 마지막 단계는 이 네 개의 DWORD를 22로 에뮬레이션된 PHADDD(PSHUFD PADDD)

  • xmm0[31-0] = xmm0[63-32] xmm0[31-0] (6)
    xmm0[63-32] = xmm0[127-96] xmm0[95-64]
    (상위 QWORD에 동일한 내용이 포함되어 무시됨)
  • xmm0[31-0] = xmm0[63-32] xmm0[31-0 ] (7)
• 숫자가 음수인 경우(EDX에서 000...0=pos 또는 111...1=neg로 표시됨) 이를 무효화합니다. (8)

결과 Haswell 32비트에 대한 Intel-IACA 처리량 분석:

처리량 분석 보고서

블록 처리량: 16.10 사이클 처리량 병목 현상: InterIteration

반복당 주기의 포트 바인딩:

| 포트 | 0 - DV | 1 | 2-D | 3 - 디 | 4 | 5 | 6 | 7 |

| 사이클 | 9.5 0.0 | 10.0 | 4.5 4.5 | 4.5 4.5 | 0.0 | 11.1 | 11.4 | 0.0 |

N - 포트 번호 또는 사이클 수 리소스 충돌로 인해 지연이 발생함, DV - 분배기 파이프(포트 0)
D - 데이터 가져오기 파이프(포트 2 및 3), CP - a 임계 경로
F - 이전 명령과의 매크로 융합 발생

• • 지시 micro-ops가 포트에 바인딩되지 않음
    ^ - Micro Fusion 발생

    - ESP 추적 동기화 uop이 발행됨

    @ - SSE 명령이 AVX256 명령을 따랐으며 수십 사이클 페널티가 발생했습니다. 예상됩니다
    ! - 지원되지 않는 명령, 분석에서 고려되지 않음

| 수 | 주기적인 포트 압력 | |

| 웁스 | 0 - DV | 1 | 2-D | 3 - 디 | 4 | 5 | 6 | 7 | |

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

위 내용은 SIMD 명령어를 사용하여 atoi를 효율적으로 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!