Tôi đang làm việc trên thư viện song song cho ngôn ngữ lập trình D. Bây giờ tôi khá hài lòng với các nguyên thủy cơ bản (song song foreach, bản đồ, giảm và nhiệm vụ/tương lai), tôi bắt đầu nghĩ về một số thuật toán song song cấp cao hơn. Trong số các ứng cử viên rõ ràng hơn cho song song là phân loại.(Khi) là loại thực tế song song và cách bạn viết một cách hiệu quả?
Câu hỏi đầu tiên của tôi là, là các phiên bản song song của thuật toán sắp xếp hữu ích trong thế giới thực hay chúng hầu hết là học thuật? Nếu chúng hữu ích, chúng hữu ích ở đâu? Cá nhân tôi hiếm khi sử dụng chúng trong công việc của tôi, đơn giản bởi vì tôi thường cố định tất cả các lõi của mình ở mức 100% bằng cách sử dụng mức độ song song thô hơn nhiều so với một cuộc gọi() duy nhất. Thứ hai, nó có vẻ như sắp xếp nhanh chóng là gần như lúng túng song song cho mảng lớn, nhưng tôi không thể có được tốc độ gần như tuyến tính tôi tin rằng tôi nên nhận được. Các tính năng chính Để sắp xếp nhanh, phần nối tiếp vốn chỉ là phân vùng đầu tiên. Tôi đã thử song song một sắp xếp nhanh chóng, sau mỗi phân vùng, phân loại hai subarrays song song. Trong giả đơn giản:
// I tweaked this number a bunch. Anything smaller than this and the
// overhead is smaller than the parallelization gains.
const smallestToParallelize = 500;
void quickSort(T)(T[] array) {
if(array.length < someConstant) {
insertionSort(array);
return;
}
size_t pivotPosition = partition(array);
if(array.length >= smallestToParallelize) {
// Sort left subarray in a task pool thread.
auto myTask = taskPool.execute(quickSort(array[0..pivotPosition]));
quickSort(array[pivotPosition + 1..$]);
myTask.workWait();
} else {
// Regular serial quick sort.
quickSort(array[0..pivotPosition]);
quickSort(array[pivotPosition + 1..$]);
}
}
Ngay cả đối với các mảng rất lớn, nơi mà thời gian phân vùng đầu tiên diễn là không đáng kể, tôi chỉ có thể nhận được khoảng một tăng tốc 30% trên một lõi kép, so với một phiên bản hoàn toàn serial của thuật toán . Tôi đoán nút cổ chai là quyền truy cập bộ nhớ dùng chung. Bất kỳ cái nhìn sâu sắc về làm thế nào để loại bỏ nút cổ chai này hoặc những gì khác nút cổ chai có thể được?
Chỉnh sửa: Nhóm tác vụ của tôi có một số chuỗi cố định, bằng số lõi trong hệ thống trừ 1 (vì chuỗi chính cũng hoạt động). Ngoài ra, loại chờ đợi tôi đang sử dụng là chờ đợi công việc, tức là nếu nhiệm vụ được bắt đầu nhưng không hoàn thành, chủ đề gọi workWait() sẽ đánh cắp các công việc khác ngoài hồ bơi và thực hiện chúng cho đến khi công việc chờ đợi xong. Nếu tác vụ không được bắt đầu, nó sẽ được hoàn thành trong chuỗi hiện tại. Điều này có nghĩa là chờ đợi không hiệu quả. Miễn là có công việc phải làm, tất cả các chủ đề sẽ được giữ bận rộn.
Tôi không biết làm thế nào để làm cho quicksort bạn parallelize tốt hơn, nhưng có một biến thể gọi là samplesort mà vốn dĩ là nhanh hơn nhiều so với một quicksort vani, và như xa như tôi có thể thấy, nó nên song song nhau. –