Parallelized Code

I will describe the details of the parallelization carried out for the computation of solid partitions. The code is an implementation of the backtracking algorithm of Knuth for this problem. Since this is a program that carries out a search through a tree counting allowed configurations — the idea here is to hard-wire the initial tracks up to some depth. This breaks up the computation into several branches, each of which can be run independent of the other branches. The results of each branch are then collated to give the final result.

Parallelization for the index N=52

At depth 1, one has the following three possibilities:

$(1,1,2),\ (1,2,1),\ (2,1,1)$.

I call these the three trunks. I go up to depth 7 for the $(1,1,2)$ trunk while I got up to depth 6 for the other two trunks. For a fixed index, the number of branches (and hence searches) decreases in this order: $(1,1,2),\ (1,2,1),\ (2,1,1)$. I have broken up each trunk into several runs labelled $A,B,C,\ldots$ with the $A$ having the longer run times and subsequent ones typically having lower run times. This organization of the runs is based on the index at the highest depth (4 or 5 depending on the trunk).

Trunk (1,1,2)

Run A B C D E F G H
No. 1-155 1001-1158
Status Done Done

Trunk (1,2,1)

Run A B C D E F G
No. 201-237 2001-2136
Status Done Done

Trunk (2,1,1)

Run A B C D E F G
No. 401-437 4001-4118
Status Done Done

More details to come

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License