guile-ml/notes.org

Parallelism abstraction ideas

Where parallel evaluation could happen

The obvious place to introduce parallelism into the decision tree algorithm is, where the algorithm branches off into subtrees, which potentially will branch off into subtrees themselves.

Profiling under Racket has shown, that the exhaustive search for the best split of a dataset of a subtree is, what takes the most time. This is another place, where parallelism can happen: One could split the search into multiple parts and start multiple, in parallel running units of evaluation, which each find the best split for one part of the data.

Parallelism constructs

• Different Scheme dialects might support different parallelism constructs or possibly no parallelism constructs. So the abstraction should consider the fact, that for some Scheme dialect, there might not be a simple way to evaluate expressions in parallel.
• It might not always be desired to run the maximum possible number of tasks or jobs in parallel. The decision, how many jobs should run in parallel should be up to the user of the algorithm. It should be configurable, probably via a keyword argument for the fit procedure.

About various ways of parallelizing the algorithm

• 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.
• I need to check, whether it is possible to introduce more running fibers than a top level scheduler specifies, by spawning new fibers in fibers.
• 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 processing one subtree, one does not have the knowledge of whether the processing of the other subtree has finished and thus 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 or previous level in the tree. The same issue might occur with fibers.
• See /reference-manual/guile/Parallel-Forms.html
• with futures, one cannot specify the number of futures to run at maximum.
• 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.
• One could 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.
• As the count of threads running at the same time is limited to a maximum given by (current-processor-count), maybe the number can be reduced from outside the program, by using taskset (fibers manual mentions it: https://github.com/wingo/fibers/wiki/Manual#Parallelism). Perhaps also setaffinity can be used to specify on what cores threads must run.

Idea about using fibers recursively

• If at tree depth 0, use run-fibers with #:parallelism .
• If not at tree depth 1, use run-fibers with #:parallelism 1.
• Problem: might not spawn enough fibers then.