From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?Q?Linus_Bj=C3=B6rnstam?= Newsgroups: gmane.lisp.guile.user Subject: Re: Limiting parallelism using futures, parallel forms and fibers Date: Wed, 08 Jan 2020 09:11:50 +0100 Message-ID: References: <04cb0461-18a1-ef17-4db7-2475c7c806e6@posteo.de> Mime-Version: 1.0 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="145160"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Cyrus-JMAP/3.1.7-731-g1812a7f-fmstable-20200106v2 To: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Wed Jan 08 09:16:13 2020 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1ip6SK-000Dsb-RB for guile-user@m.gmane.org; Wed, 08 Jan 2020 09:12:45 +0100 Original-Received: from localhost ([::1]:39458 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ip6SJ-0005oT-L8 for guile-user@m.gmane.org; Wed, 08 Jan 2020 03:12:43 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:51069) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ip6Rt-0005lV-QQ for guile-user@gnu.org; Wed, 08 Jan 2020 03:12:19 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ip6Rs-0000Z7-El for guile-user@gnu.org; Wed, 08 Jan 2020 03:12:17 -0500 Original-Received: from wout4-smtp.messagingengine.com ([64.147.123.20]:48343) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ip6Rr-0000Xn-UC for guile-user@gnu.org; Wed, 08 Jan 2020 03:12:16 -0500 Original-Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.west.internal (Postfix) with ESMTP id 62F9B539 for ; Wed, 8 Jan 2020 03:12:13 -0500 (EST) Original-Received: from imap1 ([10.202.2.51]) by compute1.internal (MEProxy); Wed, 08 Jan 2020 03:12:13 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fastmail.se; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type:content-transfer-encoding; s=fm2; bh=GbvjF hAzLc13VG6vCqtOgmsdMCtdVYKjM3QIt9LocIw=; b=SnpgGVftKfvfNf/I5MRWH 9h5sgQEjyHV78juqHib1uyKWxG6kY/4UUe96MHx6o2NfQEY89NwqVdKMFimzOnDE /6VgmlwZhVcTa9eAms4cevSQHgYsi4UuUmizXrm5KUgSh6/i/9RPtEKtPd0nMNIS xHbVZSrm1H4RrVY9mJjxGB7GF4rs3WDLRGSXR7NQqJ0agHy3P1AQ71XY8Ss1sTlh /gdxO/6sbpoSIkBIBpZVnQzN6CIVwNwp2Z6RTmBjDPmUuUNvG417dfS1yTpIh30f 2V00WN1A+vk2EqyLbyAG3TaPW27TJdnPL+isqMI6qnZu6RdxxW9pa/Lyu74LmNvZ g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm1; bh=GbvjFhAzLc13VG6vCqtOgmsdMCtdVYKjM3QIt9Loc Iw=; b=RMsO2tcehaZnCXSfoBuMn9sRQRykAj4yFaKkMUlatmmBK5M/JEfPtl4MH t9m7YGGqw7r6eOpB2+1VbWpWzU1SIrGWLjvGCnzPayXA5faH2uZ2rrk30dkhpyCx fvxzudQm2nwK3nt1jl0UwPPfxvJeqtAk5VMi4Mw6chsuwCHQ1g2syLGbmT5N6nrx iLLDxv3DocdXlZ4ShTFBAQ/3NpGxxtyrdtvwH5NVt1PJssIhRVRdfrj3ZGZ0NUFH VKdwevRa18VwDjYpfAAbz6TxOGMxw0Mbf9CEw7dMCQqETMgOKIx3wmYRrlHBkGzc qYM07utZijMS+Zon5Xf2wbY6xy9+g== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedufedrvdehjedguddujecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgfgse htqhertderreejnecuhfhrohhmpefnihhnuhhspgeujhpnrhhnshhtrghmuceolhhinhhu shdrihhnthgvrhhnvghtsehfrghsthhmrghilhdrshgvqeenucffohhmrghinhepnhhoth grsghughdrohhrghenucfrrghrrghmpehmrghilhhfrhhomheplhhinhhushdrihhnthgv rhhnvghtsehfrghsthhmrghilhdrshgvnecuvehluhhsthgvrhfuihiivgeptd X-ME-Proxy: Original-Received: by mailuser.nyi.internal (Postfix, from userid 501) id A5C12C200A4; Wed, 8 Jan 2020 03:12:12 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface In-Reply-To: <04cb0461-18a1-ef17-4db7-2475c7c806e6@posteo.de> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 64.147.123.20 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.org gmane.lisp.guile.user:16008 Archived-At: Hi!=20 I don't have much more input than to say that futures use a built in thr= ead pool that is limited to (current-processor-count) threads. That coul= d maybe be modified using setaffinity ? Hope this helps. --=20 Linus Bj=C3=B6rnstam On Wed, 8 Jan 2020, at 08:56, Zelphir Kaltstahl wrote: > Hello Guile users! >=20 > I thought about what I need for parallelizing an algorithm I am workin= g > on. Background: I am working on my decision tree implementation > (https://notabug.org/ZelphirKaltstahl/guile-ml/src/wip-port-to-guile),= > which is currently only using a single core. Training the model splits= > the tree into subtrees, which is an opportunity for running things in > parallel. Subtrees can subsequently split again and that could again > result in a parallel evaluation of the subtrees. >=20 > Since it might not always be desired to use potentially all available > cores (blocking the whole CPU), I would like to add the possibility fo= r > the user of the algorithm to limit the number of cores used by the > algorithm, most likely using a keyword argument, which defaults to the= > number of cores. Looking at futures, parallel forms and the fibers > library, I've had the following thoughts: >=20 > 1. fibers support a ~#:parallelism~ keyword and thus the number of > fibers running in parallel can be set for ~run-fibers~, which creates = a > scheduler, which might be used later, possibly avoiding to keep track = of > how many threads are being used. It would probably be important when > using fibers, to always make use of the same scheduler, as a new > scheduler might not know anything about other schedulers and the limit= > for parallelism might be overstepped. Schedulers, which are controlled= > by the initial scheduler are probably OK. I will need to re-read the > fibers manual on that. >=20 > 2. With parallel forms, there are ~n-par-map~ and ~n-par-for-each~, > where one can specify the maximum number of threads running in paralle= l. > However, when recursively calling these procedures (in my case > processing subtrees of a decision tree, which might split into subtree= s > again), one does not have the knowledge of whether the processing of t= he > other recursive calls has finished and cannot know, how many other > threads are being used currently. Calling one of these procedures agai= n > might run more threads than specified on a upper level call. >=20 > 3. With futures, one cannot specify the number of futures to run at > maximum directly. In order to control how many threads are evaluating > code at the same time, one would have to build some kind of construct > around them, which keeps track of how many futures are running or coul= d > be running and make that work for recursive creation of further future= s > as well. >=20 > 4. One could also do something ugly and create a globally defined acti= ve > thread counter, which requires locking, to keep track of the number of= > in parallel running threads or futures. >=20 > 5. I could just assume the maximum number of currently used cores, by > giving the tree depth as argument for recursive calls and calculating > from that, how many splits and thus evaluations might be running in > parallel at that point. However, this might be inaccurate, as some > subtree might already be finished and then I would not use the maximum= > user specified number of parallel evaluations. >=20 > So my questions are: >=20 > - Is there a default / recommended way to limit parallelism for > recursive calls to parallel forms? >=20 > - Is there a better way than a global counter with locking, to limit t= he > number of futures created during recursive calls? I would dislike very= > much to have to do something like global state + mutex. >=20 > - What do you recommend in general to solve this? >=20 > Regards, > Zelphir >=20 >=20 >