Mảng sắp xếp có khoảng một triệu chuỗi, trong đó mỗi chuỗi có thể có độ dài tối đa một triệu ký tự.Có thuật toán sắp xếp mảng chuỗi cho GPU không?
Tôi đang tìm bất kỳ triển khai thuật toán sắp xếp nào cho GPU.
Tôi có khối dữ liệu có kích thước khoảng 1MB và tôi cần phải xây dựng suffix array. Bây giờ bạn có thể thấy làm thế nào nó có thể có một triệu dây bên trong số lượng bộ nhớ thực sự nhỏ.
Trạng thái của tính năng phân loại GPU không đặc biệt đáng khích lệ.
Để phân loại các số nguyên 32 bit từ năm 2009 (với 2 tác giả là nhà nghiên cứu tại Nvidia), chỉ tăng 23% cho loại CUDA tốt nhất trên GTX280 so với loại CPU tốt nhất trên 4 lõi Yorkfield.
http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf
Điều này đã sử dụng phân loại radix trên GPU và hợp nhất sắp xếp trên CPU. Bạn sẽ cần một loại so sánh dựa trên để xây dựng một mảng hậu tố, vì vậy thay vì GPU radix sắp xếp tốt nhất của những người trong bài báo sẽ được sắp xếp GPU sắp xếp, mà đạt được một nửa tốc độ của GPU radix sắp xếp (với 1 triệu phím) - tức là khoảng 40% chậm hơn so với sắp xếp hợp nhất CPU.
Việc thêm các phím có chiều dài thay đổi dường như có khả năng gây ra các chuỗi trong một sợi dọc sẽ bị mất đồng bộ trên GPU, vì vậy sẽ giảm hiệu suất trên GPU nhiều hơn CPU.
Nhìn chung, nếu mục đích của bạn là xây dựng một hệ thống hiệu quả, tôi khuyên bạn nên sử dụng triển khai CPU cho vấn đề này bởi vì nó sẽ nhanh hơn và dễ dàng hơn để viết.
Nhưng, nếu mục đích của bạn là để thử nghiệm hoặc chỉ để tìm hiểu về GPU, sau đó bạn có thể tìm thấy thi CUDA của merge sort từ giấy trong CUDA SDK:
http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html
Không phải toàn bộ điểm của CUDA cũng sử dụng bộ xử lý không hoạt động sao? Ngay cả khi bạn không có cải thiện tốc độ nào trên GPU trên CPU, bạn vẫn sẽ có cải thiện 2X so với chỉ có CPU, miễn là bạn có thể sử dụng hiệu quả tính song song bổ sung này. –
@Robert Harvey - hầu hết các ứng dụng của CUDA không giữ CPU bận rộn cùng một lúc. Tuy nhiên gần đây điều này đã trở nên phổ biến hơn, và thường được gọi là hybrid GPU/CPU. Sự cần thiết phải sao chép vào giữa các kỷ niệm CPU và GPU có xu hướng làm cho nó khá khó khăn để có được hiệu suất tốt mặc dù. Trong trường hợp này, tôi mong đợi tốt nhất bạn sẽ đạt được 150% tốc độ CPU, và bạn nên đầu tư vào một hệ thống với hai CPU. – RD1
Cảm ơn câu trả lời của bạn. Tôi đồng ý với tất cả các ghi chú của bạn về sắp xếp chuỗi trên GPU, tôi nghĩ theo cùng một cách, nhưng tôi đã hy vọng rằng có một thuật toán mà tôi đã bỏ qua. – Kentzo
'1M' ký tự trên mỗi chuỗi (avg '.5M'?),' 1M' chuỗi, 2 byte/char (phổ biến nhất) sản lượng: '.5 * 1 * 2 = 1TB' bộ nhớ. Bạn cần một cái gì đó đặc biệt cho điều này (có lẽ là một cơ sở dữ liệu?), Vì rất ít máy tồn tại với loại bộ nhớ đó, hãy để một mình bộ nhớ GPU. http://blogs.technet.com/b/markrussinovich/archive/2008/07/21/3092070.aspx – Abel
Độ dài chuỗi tối đa không nói gì về mức trung bình. Tôi cho rằng các chuỗi đã có trong bộ nhớ và đang được sắp xếp, nhưng áp phích không hài lòng với hiệu năng của CPU trong nhiệm vụ. –
Có thể có liên quan/hữu ích khi biết cách dữ liệu được cấu trúc. Có phải đó là một chuỗi các chuỗi liền nhau được phân tách bởi '\ 0' không? Các chuỗi có đứng trước tiêu đề chứa số byte không? Hoặc là có một mảng con trỏ vào một đống? Chúng ta đang nói chuỗi ASCII hay Unicode? –