From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Zelphir Kaltstahl Newsgroups: gmane.lisp.guile.user Subject: Limiting parallelism using futures, parallel forms and fibers Date: Wed, 8 Jan 2020 08:56:11 +0100 Message-ID: <04cb0461-18a1-ef17-4db7-2475c7c806e6@posteo.de> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="146384"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Icedove/52.9.1 To: Guile User Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Wed Jan 08 08:57:34 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 1ip6Ct-000ICX-BQ for guile-user@m.gmane.org; Wed, 08 Jan 2020 08:56:47 +0100 Original-Received: from localhost ([::1]:39306 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ip6Cs-0006yq-5I for guile-user@m.gmane.org; Wed, 08 Jan 2020 02:56:46 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:43320) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ip6CP-0006yi-U9 for guile-user@gnu.org; Wed, 08 Jan 2020 02:56:19 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ip6CO-0006Vl-Kt for guile-user@gnu.org; Wed, 08 Jan 2020 02:56:17 -0500 Original-Received: from mout02.posteo.de ([185.67.36.66]:38069) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ip6CO-0006UN-2h for guile-user@gnu.org; Wed, 08 Jan 2020 02:56:16 -0500 Original-Received: from submission (posteo.de [89.146.220.130]) by mout02.posteo.de (Postfix) with ESMTPS id AD1A72400FC for ; Wed, 8 Jan 2020 08:56:13 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1578470173; bh=T/nqA9yTjPIHrCO/khsx/sEYoqeLNkaRm2bMgk2ZHc0=; h=To:From:Subject:Date:From; b=H13MjB3iCRWjX3FrZM8D6Y1RLHjd6PjXjNwBYD8OmnvnIJ78/BD+BzHs5te8Y3V/D Weig1Eqd3tZkhM3grkrM+tIGNktEYimrT8m9EFhMMm6AwSXeZFSuE4PSirU5BMwofs sk73yys9MT+ixgqKMxZ0ylAesDkIa5244y9U+qSdmp2YPTvo46Nj3nKXPGAxx4yiXR EKaJJ2ggQ24iXcS/t8oDoGE1TVyNqZnx09+32YzCG8EaAQKokRvss0Mlb9g6FOfcA0 ChPBB52EmP6WsJnlRnNCmkPrjowFlZbljfhmuM4d/U3MYQnWx/rKjLViw/vJPGVcBC QFBfykH/4hkMw== Original-Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 47t1lc6tCqz9rxK for ; Wed, 8 Jan 2020 08:56:12 +0100 (CET) Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 185.67.36.66 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:16007 Archived-At: Hello Guile users! I thought about what I need for parallelizing an algorithm I am working 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. Since it might not always be desired to use potentially all available cores (blocking the whole CPU), I would like to add the possibility for 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: 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. 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 parallel. However, when recursively calling these procedures (in my case processing subtrees of a decision tree, which might split into subtrees again), one does not have the knowledge of whether the processing of the other recursive calls has finished and cannot know, how many other threads are being used currently. Calling one of these procedures again might run more threads than specified on a upper level call. 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 could be running and make that work for recursive creation of further futures as well. 4. One could also do something ugly and create a globally defined active thread counter, which requires locking, to keep track of the number of in parallel running threads or futures. 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. So my questions are: - Is there a default / recommended way to limit parallelism for recursive calls to parallel forms? - Is there a better way than a global counter with locking, to limit the number of futures created during recursive calls? I would dislike very much to have to do something like global state + mutex. - What do you recommend in general to solve this? Regards, Zelphir