[Idea] prospr for HPC

[rubenhorn]

When solving a large quantity of small instances, many many-core systems can be used by running several prospr processes in parallel.
However, solving very large instances remains intractable due to job timeouts.
Therefore, at least one algorithm (e.g., depth_first_bnb) should be implemented, which leverages multiple cores (across multiple nodes¹) to solve these instances in parallel.

A naive approach could work like this:

1. Determine the number of available ranks.
2. Iterate algorithm to a matching depth in the tree (#subtrees $\ge$ #ranks).
3. Clone state and solve subtree on each rank.
4. Reduce subtree results. ²

A better approach would be to use master-worker paradigm³ using non-blocking MPI:

1. The root rank generates "jobs" (partial solution, state, optimum) or quit message (receive request from any).
2. Other ranks request jobs from root and send back new jobs (recursion) or subtree optima.
3. The root rank must sort jobs by subtree depth to enforce a global depth-first criterion, and can also prune non-optimal partial results.

Note: This second approach results in a lot of communication. Therefore, a worker should solve the whole subtree if it is rather shallow (e.g., depth = 7).

Footnotes

1. Consider using include guards around these code regions to keep supporting systems without MPI support. ↩

2. Guard critical section to avoid race conditions. ↩

3. cf. Borisenko and Gorlatch (2016) ↩

[okkevaneck]

Great idea! I'm wondering if it's maybe better to create a set of parallel algorithms instead of changing existing algorithms. So it's easier for the user to select whether they want to run multiple prospr processes in parallel or create a parallel instance for a single protein.