정렬 할 배열에는 약 백만 개의 문자열이 있으며 모든 문자열의 길이는 최대 100 만 자까지 가능합니다.GPU 용 문자열 배열 정렬 알고리즘이 있습니까?
GPU를위한 정렬 알고리즘의 구현을 찾고 있습니다.
크기가 약 1MB 인 데이터 블록이 있으며 suffix array을 생성해야합니다. 이제는 백만 가지의 문자열을 실제로 소량의 메모리 안에 둘 수있는 방법을 알 수 있습니다.
GPU 정렬의 최첨단 기술은 특별히 권장하지 않습니다.
32 비트 정수를 정렬하기 위해 2009 년 다음 기사 (Nvidia의 연구자 2 명과 함께)는 4 코어 Yorkfield에서 최고의 CPU 정렬과 비교하여 GTX280의 CUDA를 23 % 향상 시켰습니다.
http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf
이는 GPU에 기수 정렬을 사용하고, 종류에 CPU를 병합합니다. 접미사 배열을 구성하기 위해 비교 기반 정렬이 필요합니다. 따라서 GPU 기수 정렬 대신 GPU 병합 정렬이 가장 적합합니다 (GPU 기수 정렬 속도는 약 1 백만 키) - 즉, CPU 병합 정렬보다 약 40 % 느립니다.가변 길이 키를 추가하면 워프의 스레드가 GPU에서 동기화되지 않을 수 있으므로 GPU의 성능이 CPU보다 떨어집니다.
전반적으로 효율적인 시스템을 만드는 것이 목적이라면이 문제에 대해 CPU 구현을 사용하는 것이 더 빠르고 쉽기 때문에 사용하는 것이 좋습니다.
하지만 당신의 목적은 실험을하거나 GPU에 대해 배울 경우, 당신은 CUDA SDK의 용지에서 병합 정렬의 CUDA 구현을 찾을 수 있습니다
http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html
CUDA의 모든 점이 어쨌든 유휴 상태의 프로세서를 사용하는 것이 아닙니까? CPU를 통한 GPU의 속도 향상이 전혀 없다고해도 여분의 병렬 처리를 효과적으로 사용할 수만 있다면 CPU 사용에 비해 2 배의 향상된 성능을 유지할 수 있습니다. –
@Robert Harvey - 대부분의 CUDA를 사용하면 CPU가 동시에 사용되지 않습니다. 그러나 최근에는 이것이 점점 더 보편화되어 일반적으로 하이브리드 GPU/CPU라고합니다. CPU와 GPU 메모리 사이에 복사해야 할 필요가 있기 때문에 좋은 성능을 얻으려면 상당히 까다로운 경향이 있습니다. 이 경우에는 CPU 속도의 150 %를 달성하는 것이 가장 좋을 것입니다. 두 개의 CPU가있는 시스템에 투자하는 것이 좋습니다. – RD1
답변 해 주셔서 감사합니다. GPU에서 문자열 정렬에 관한 모든 노트에 동의합니다. 같은 방식으로 생각했지만, 내가 놓친 알고리즘이 있기를 기대했습니다. – Kentzo
'1M' 문자 당을 문자열 (평균 '.5M'?),'1M' 문자열, 2 바이트/char (가장 일반적인)은'.5 * 1 * 2 = 1TB' 메모리를 산출합니다. GPU 메모리는 말할 것도없고, 이런 종류의 메모리를 가진 머신이 거의 존재하지 않기 때문에, 이것을 위해 특별한 것을 필요로 할 것입니다 (아마도 데이터베이스입니까?). http://blogs.technet.com/b/markrussinovich/archive/2008/07/21/3092070.aspx – Abel
최대 문자열 길이는 평균에 대해 아무 것도 말하지 않습니다. 문자열이 이미 메모리에 있고 정렬 중이라고 가정하지만 포스터는 작업의 CPU 성능에 만족하지 않습니다. –
데이터 구성 방법을 듣는 것은 유용 할 수 있습니다. '\ 0'에 의해 분리 된 일련의 연속 된 문자열입니까? 문자열 앞에 바이트 수가 들어있는 헤더가 있습니까? 또는 힙에 대한 포인터 배열이 있습니까? ASCII 문자열이나 유니 코드를 사용하고 있습니까? –