From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 48F2FBBAF for ; Mon, 21 Dec 2009 14:31:35 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aj4DABcIL0vZSMDqi2dsb2JhbACBSpoIAQEBCgsKBxEFuC+ELgQ X-IronPort-AV: E=Sophos;i="4.47,431,1257116400"; d="scan'208";a="42525954" Received: from fmmailgate03.web.de ([217.72.192.234]) by mail1-smtp-roc.national.inria.fr with ESMTP; 21 Dec 2009 14:31:11 +0100 Received: from smtp08.web.de (fmsmtp08.dlan.cinetic.de [172.20.5.216]) by fmmailgate03.web.de (Postfix) with ESMTP id 2D02D139FC9E4; Mon, 21 Dec 2009 14:31:11 +0100 (CET) Received: from [95.208.117.111] (helo=frosties.localdomain) by smtp08.web.de with asmtp (TLSv1:AES256-SHA:256) (WEB.DE 4.110 #314) id 1NMiLu-0003Of-00; Mon, 21 Dec 2009 14:31:10 +0100 Received: from mrvn by frosties.localdomain with local (Exim 4.69) (envelope-from ) id 1NMiLu-0005Xn-4q; Mon, 21 Dec 2009 14:31:10 +0100 From: Goswin von Brederlow To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: multicore wish [Was: Re: [Caml-list] Re: OCaml is broken] References: <4B2D2BC1.6020204@msu.edu> <200912200443.57698.jon@ffconsultancy.com> Date: Mon, 21 Dec 2009 14:31:10 +0100 In-Reply-To: <200912200443.57698.jon@ffconsultancy.com> (Jon Harrop's message of "Sun, 20 Dec 2009 04:43:57 +0000") Message-ID: <874onko3mp.fsf_-_@frosties.localdomain> User-Agent: Gnus/5.110006 (No Gnus v0.6) XEmacs/21.4.22 (linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: goswin-v-b@web.de X-Sender: goswin-v-b@web.de X-Provags-ID: V01U2FsdGVkX199zKnwOK3HFJm9g8vQFf9pDbjecTd7rVkUafEr 7reN76iceNMFocqAx1ME4JEgZhdBZ9iGoH4qOis/OECTlEDCZe UbQ9TJxSY= X-Spam: no; 0.00; ocaml:01 chunks:01 factory:98 factory:98 mfg:98 caml-list:01 writes:01 chunk:02 chunk:02 seems:03 let:03 size:95 size:95 parallel:05 implement:06 Jon Harrop 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