거대한 정수를 병렬 처리 할 수 ​​있습니까?

Question

부호없는 256 메가 비트 정수를 2 억 번 추가해야합니다. 운반은 추가적으로 분명히 중요하며 하위 비트가 추가 될 때까지 기다리지 않고 결정할 수 없기 때문에 숫자를 여러 부분으로 나누고 나중에 운반하는 것과 같은 멀티 코어 CPU 기능으로 인해 성능이 향상됩니까?

Answer 1

확실히 많은 부분으로 분리 할 수 ​​있습니다. 예를 들어, 다음 두 숫자를 사용하십시오.

12345 
+ 67890 

이제 우리는 세 번째 숫자 인 수백과 열 사이에 나눕니다. 이것은 당신이이 경우, 두 자리 꺼져 다진 얼마나 많은 숫자 알 필요가 설정 왼쪽 숫자에 각

123  45 
+ 678 + 90 
------------- 
    801  135 

의 결과를 계산, 그래서 다시 두 개의 0을 추가 우리에게

123  45 
+ 678 + 90 

을 제공합니다 801의 끝 부분에 80100을줍니다. 135를 추가하면 80235가됩니다.

훨씬 더 큰 수와 원하는만큼 나누어서이 작업을 수행 할 수 있습니다. 이 방법을 사용하면 운반이 발생하지 않습니다.

큰 숫자를 재결합 할 때 물론 큰 추가가 남아 있습니다. 당신은 아마 얼마나 많은 자릿수가 나왔는지 알 수있을 것입니다, 그리고 그 작은 양을 당신의 왼쪽 번호에 추가하십시오.

예를 들어 위의 예에서 우클릭의 숫자는 2 열에서 3 열로 바뀌며 결과는 135가됩니다. 따라서 추가 열은 휴대 될 번호이며 작은 수에 더하고 작은 수를 더하고 문자열처럼 두 숫자를 연결하면됩니다.

45 및 90 둘 모두 135를 더한 두 개의 열을 차지합니다. 이 경우 그냥 1을 입력하고 왼쪽 번호 인 801에 추가하십시오.

801 + 1 = 802 
802 concatenated with 35 = 80235 

매우 효율적인 것을 원한다면 uld look-up 32 비트 프로세서가 64 비트 또는 그 이상의 숫자를 추가하는 방법. 나는 그들이 64 비트 숫자에 대해 비슷한 것을하고, 두 개의 32 비트 섹션을 추가하고, 최하위 32 비트에서 가장 중요한 것으로 옮겨야한다고 확신한다.

병렬 처리 측면에서 숫자를 32 비트 쌍으로 분할하여 함께 추가 한 다음 CPU가 한 번에 처리 할 수있는 사용 가능한 스레드 수를 결정한 다음 그만큼의 쌍 목록을 나눠서 각 스레드에 많이. 결과가 계산되면 완성 된 섹션에 넣으십시오.

숫자에 하나의 1 값을 추가해도 다른 숫자로 넘어갈 수 있으므로 모든 결과를 다시 얻은 후에 가장 중요도가 낮은 숫자에서 가장 중요한 숫자로 이동하는 속임수는 까다 롭습니다.

Answer 2

GMP library을 사용하지 않으시겠습니까?

Answer 3

당신이 태그 마우스를 움직일 경우 해당 주제에 관심이 번호 회원에 대한 정보를 찾을 수 있습니다 :

• 멀티 코어 - 118
• 멀티 스레딩 - 2.1K
• C - 11.7k
• C++ - 17K
• 성능 1.3K
• 스핀 - 5
• 원자 - 18

당신은 하나 개의 주제를 선택하고 다음의 수를 좁힐 수 있습니다 다른/다른 사람을 추가하여 질문.

원래 게시물은 멀티 코어를 사용하여보다 효율적인 추가 작업을 수행해야하므로 멀티 코어가 하나의 태그로 선택됩니다. 멀티 스레딩은 멀티 코어를 사용하는 모든 OS 또는 응용 프로그램의 일부이므로이를 선택하십시오. 이제 117 개의 질문이 있습니다. 적은 수보다는 많은 점수로 사용자가 질문을 선택하는 것이 좋습니다. 개별 질문에 대한 태그를 살펴보고 C#, Java 및 .Net을 사용하는 태그는 코드 실행 효율성보다는 코드 생성 효율성에 대한 자세한 내용이므로 피하십시오.

검색 할 수있는 다른 개념은 선호도, 중요 섹션, 채도, 메모리 잠금/장벽, 스레드 안전, rdtsc입니다.

당신이 명심할 수있는 한 가지 사실은 정말 빠른 코드 작성의 실용성이 시행 착오와 관련이 있으며, 발을 젖게하거나 또는 무엇이라고 부르기를 원할 수도 있다는 것입니다. 여기서 찾을 수있는 것은 시도 할 수있는 것에 대한 힌트이며, 당신이 바라는 것이 무엇인지에 대한 힌트입니다.

내 원래 GMP의 답변에 대해서는 author's page을 확인하시기 바랍니다. 여기에는 다른 x86 아키텍처에서 지속적인 명령어 처리량, 정수 곱셈을 사용한 상수 정수로 나누기, Simon Singh 코드 북 도전 과제에서이기는 것과 같은 정보가 포함되어 있습니다. GMP 자체에 대한 성능 정보도 있습니다.