Jon Harrop <j...@ffconsultancy.com> writes: > We've discussed the problems with that before. Writing a parallel generic > quicksort seems to be a good test of a decent multicore capable language > implementation. Currently, F# is a *long* way ahead of everything open > source.
How do you implement it? 1) divide at the top and then let each core sort its smaller array Say you have 2^n cores then the first n splits in merge sort would first sort the values into the 2 regions and then start a thread for each region (start a new one, do the other part in this thread). After n splits you would switch to a uni-core quicksort. For this you need to split well so each core ends up with a roughly equal sized chunk. 2) factory/worker approach Each core runs a factory/worker thread waiting on a job queue. You start by dumping the full array into the job queue. Some random core picks it up, splits it into 2 regions and dumps one into the job queue. If the job gets too small (PAGE_SIZE? cache line size? total size / cores^2?) the factory/worker switches to normal uni-core quicksort and sorts the whole chunk. The job queue should probably be priority based so larger chunks are sorted before smaller. Here the quality of each split is not so important. If a chunk is smaller, and therefore faster, the core just picks up the next job in the queue. But you need more syncronization between the cores for the job queue. On the other hand you aren't limited to 2^n cores. Any number will do. MfG Goswin _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs