x64 어셈블러의 속도를 높입니다.

저는 매우 긴 정수 (10 진수 약 10,000 자리)를 곱하기 위해 산술 연산을하고 있습니다. 내 도서관의 일환으로 2 개의 긴 번호를 추가하겠습니다.x64 어셈블러의 속도를 높입니다.

프로파일 링은 내 코드가 add() 및 sub() 루틴에서 시간의 최대 25 %까지 실행된다는 것을 보여주기 때문에 최대한 빨리 수행해야합니다. 그러나 나는 아직 많은 가능성을 보지 못했다. 어쩌면 당신은 나에게 도움, 조언, 통찰력 또는 아이디어를 줄 수 있습니다. 나는 그들을 시험 할 것이고 당신에게 돌아갈 것이다.

지금까지 내 추가 루틴은 몇 가지 설정을 수행 한 후 8 배 풀려 루프를 사용하여 다른 오프셋 (offset)를

mov rax, QWORD PTR [rdx+r11*8-64] 
mov r10, QWORD PTR [r8+r11*8-64] 
adc rax, r10 
mov QWORD PTR [rcx+r11*8-64], rax

7 개 블록을 따라 다음 루프.

이전에 메모리에서 값을로드하려고 시도했지만 도움이되지 않았습니다. 나는 그것이 좋은 prefetching 때문이라고 생각합니다. 나는 Intel i7-3770 Ivy Bridge 4 코어 CPU를 사용합니다. 하지만 현대의 CPU에서 잘 작동하는 코드를 작성하고 싶습니다.

편집 : 몇 가지 타이밍을 수행했습니다. 약 2.25 cycles/word로 1k 단어를 추가합니다. ADC를 제거하면 MOV 만 남아 있으므로 약 1.95 cycles/word가 걸립니다. 따라서 주요 병목 현상은 메모리 액세스 인 것 같습니다. 라이브러리 memcpy()은 약 0.65 cycles/word에서 작동하지만 입력이 하나 뿐이며 두 개가 아닙니다. SSE 레지스터를 사용하기 때문에 훨씬 빠릅니다.

몇 가지 질문 :

그것은 구조를 "부하, 부하, 저장소를 추가"또는 "부하가, 추가로 메모리"도움이 될 것이다 사용하는 것이 유용하다? 지금까지 내 테스트는 어떤 이점도 보이지 않았습니다.
평상시처럼 SSE (2,3,4)의 도움을받을 수 있습니까?
어드레싱 (스케일 된 인덱스 + 기본 플러스 오프셋)이 심하게 영향을 줍니까? 대신 ADD r11, 8을 사용할 수 있습니다.
루프 언 롤링은 어떻게됩니까? 나는 언 롤링이 샌디 브릿지 아키텍처 (Agner Fog http://www.agner.org/optimize/)에 좋지 않다고 읽었습니다. 그것이 선호되거나 피할 수 있습니까?
(편집) SSE 레지스터를 사용하여 큰 덩어리의 단어를 메모리에서로드하고 저장하고 범용 레지스터 및 SSE 레지스터와 효율적으로 단어를 교환 할 수 있습니까?

매우 고맙게 생각합니다.

출처

2012-12-20 cxxl

매우 큰 숫자를 곱하는 가장 빠른 방법은 빠른 푸리에 변환입니다. http://en.wikipedia.org/wiki/Multiplication_algorithm 어셈블러에서 로직을 구현하려 한 적이 없었습니다. Apperantly Prime95는 x86 어셈블리 로직에서 고속 푸리에 변환을 포함하고 있으며, 거기에서 (자유롭게) 취할 수 있습니다. –

감사합니다. 지금은 빨리 추가하고 싶습니다. – cxxl

GMP 소스를 살펴볼 수 있습니다. – zch

먼저 데이터를 미리 가져 와서 (x64 레지스터에 더 많은 데이터 블록을 먼저 읽은 다음 계산을 시도 할 수 있음) 데이터가 메모리에 제대로 정렬되어 있는지 확인하고 16에 맞춰 레이블에 루프 코드를 넣어보십시오. SIB는

당신은 또한 당신의 코드를 단축을 시도 할 수 있습니다 주소 제거 :

mov rax, QWORD PTR [rdx+r11*8-64] 
adc rax, QWORD PTR [r8+r11*8-64] 
mov QWORD PTR [rcx+r11*8-64], rax

출처

2012-12-20 14:18:18

나는 그 모든 것을 시도해 보았고, 때로는 더 나쁜 타이밍을 얻지 못했다. 주요 시간은 메모리 액세스에서 손실 된 것 같습니다. – cxxl

가장 어려운 의존성이 모든 메모리 블록 사이 캐리의 전파이다; 우선 그 장치를 다루는 방법을 시도하려고합니다.

다음 조각은 캐리 전파를 시뮬레이트하지만 캐리 플래그를 사용하지 않는 "이점"이 있습니다. 이은 세 개 또는 네 개의 개별 스레드에 대해 병렬 처리 할 수 있으며 각 스레드는 약 반 25,000 자릿수 (또는 10000 바이트)를 나눕니다.그런 다음 단 하나의 바이트, 단어, dword 등에 영향을주는 그러한 확률은 점근 적으로 0에 도달합니다.

long long carry=0; 
for (int i=0;i<N;i++) { 
    carry += (long long)*a++ + (long long)*b++; 
    *c++ = carry; carry>>=32; 
}

내 프로파일에 따르면, XMM을 사용 carryless 또한이 ~ 걸릴 것 550ms (1E9 단어), 시뮬레이션 캐리 ~ 1020ms 및 4 방향 병렬 버전 (모든 어셈블러 최적화없이) ~ 820ms를 취할 것입니다 걸릴 것이다.

아키텍처 최적화에는 잉여 시스템을 사용하는 것이 포함될 수 있습니다. 여기에서는 항상 캐리를 전파 할 필요가없고 캐리 계산을 거의 무한정 연기 할 수 있습니다.

출처

2012-12-20 15:07:46

memcpy는 다음 작업을 수행하기 전에 가져 오는 데이터에 대한 의존성이 없기 때문에 더 빠릅니다.

가이 같은 않도록 당신은 당신의 코드를 정렬 할 수 있습니다 경우

mov rax, QWORD PTR [rdx+r11*8-64] 
mov rbx, QWORD PTR [rdx+r11*8-56] 
mov r10, QWORD PTR [r8+r11*8-64] 
mov r12, QWORD PTR [r8+r11*8-56] 
adc rax, r10 
adc rbx, r12 
mov QWORD PTR [rcx+r11*8-64], rax 
mov QWORD PTR [rcx+r11*8-56], rbx

를 i를 -56의 오프셋 100 % 확실하지가 코드에 맞는이지만, 개념은 "입니다 해요 권리".

또한 캐시 적중/캐시 충돌을 고려할 것입니다. 예 : 세 개의 데이터 블록이있는 경우 [캐쉬에있는 동일한 오프셋에 정렬되지 않았는지 확인하십시오. 나쁜 예는 모든 블록을 캐시 크기의 배수, 즉 캐시의 동일한 위치에서 할당하는 것입니다. 초과 할당 및 서로 다른 데이터 블록이 적어도 512 바이트만큼 오프셋되었는지 확인하십시오 [4K 초과 할당, 4K 경계 시작 주소 반올림, 두 번째 버퍼에 512 추가, 세 번째 버퍼에 1024 추가]

데이터가 충분히 크면 (L2 캐시보다 큼) MOVNT를 사용하여 데이터를 가져 오거나 저장할 수 있습니다. 그러면 캐시로 읽는 것을 피할 수 있습니다. 매우 큰 데이터가있을 때만 이점이 있습니다. 다음 읽기에서는 단순히 캐시에서 쫓겨나는 "유용함"을 발견 할 뿐이며, 캐시에서 값을 저장하기 전에 다시 캐시에 저장해야합니다. 따라서 캐시에 값을 저장하면 실제로 도움이되지 않습니다. ...

편집 : SSE 또는 유사 항목을 사용하면 여기에서 다루는대로 도움이되지 않습니다. Can long integer routines benefit from SSE?

출처

2012-12-20 15:29:20

x64 어셈블러의 속도를 높입니다.

답변

관련 문제