Pracuję nad biblioteką równoległości dla języka programowania D. Teraz, gdy jestem całkiem zadowolony z podstawowych prymitywów (równoległe foreach, mapa, redukcja i zadania/przyszłość), zaczynam myśleć o kilku równoległych algorytmach wyższego poziomu. Wśród bardziej oczywistych kandydatów do równoległości jest sortowanie.(Kiedy) są praktyczne w zastosowaniach równoległych i jak można pisać wydajne?
Moje pierwsze pytanie to, czy są równoległe wersje algorytmów sortowania przydatnych w rzeczywistym świecie, czy są one w większości akademickie? Jeśli są przydatne, gdzie są przydatne? Osobiście rzadko używałbym ich w mojej pracy, po prostu dlatego, że zwykle kołkiem wszystkie moje rdzenie w 100% przy użyciu znacznie grubszy poziom równoległości niż pojedynczego wywołania sort().
Po drugie, wydaje się, że szybkie sortowanie jest niemal żenująco równoległe w przypadku dużych tablic, ale nie mogę uzyskać prawie liniowych przyspieszeń, które moim zdaniem powinny być osiągane. W przypadku szybkiego sortowania jedyną nieodłączną częścią jest pierwsza partycja. Próbowałem równolegle szybkiego sortowania po, po każdej partycji, równolegle sortować dwie podmary. W uproszczonej Pseudokod:
// 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..$]);
}
}
Nawet dla bardzo dużych tablic, gdzie po raz pierwszy ze strefy jest znikoma, mogę tylko dostać około 30% SpeedUp na podwójnym rdzeniem, w porównaniu z czysto seryjnym wersji algorytmu . Zgaduję, że wąskim gardłem jest dostęp do pamięci dzielonej. Jakiekolwiek spostrzeżenia na temat tego, jak wyeliminować to wąskie gardło, czy jakie może być wąskie gardło?
Edytuj: Moja pula zadań ma ustaloną liczbę wątków, równą liczbie rdzeni w systemie minus 1 (ponieważ główny wątek również działa). Ponadto typ oczekiwania, którego używam, to oczekiwanie na pracę, tj. Jeśli zadanie jest uruchomione, ale nie zostało zakończone, wątek wywołujący workWait() kradnie inne zadania poza pulą i wykonuje je, dopóki nie zostanie zakończona operacja, na którą czeka. Jeśli zadanie nie zostanie uruchomione, zostanie zakończone w bieżącym wątku. Oznacza to, że oczekiwanie nie jest nieefektywne. Dopóki będzie praca do wykonania, wszystkie wątki będą zajęte.
nie wiem jak zrobić quicksort parallelize lepiej, ale nie jest to wariant zwany samplesort który jest z natury znacznie szybciej niż quicksort waniliowym, io ile widzę, to powinien być w równym stopniu zrównoleglony. –