Catalan CnC
Catalan CnC is a really simple example problem that I wrote up using the Intel Concurrent Collections for C/C++ framework.
where each arrow denotes a dependence. Every number represents a computation node, with the exception of 0, which is the environment.
The calculation at each node is defined as follows:
if (n==0){
result[n] = 1;
}else{
result[n] = sum of results of predecessors;
}
This calculation is actually one that figures out the number of monotonic paths from node 1 to node 25 in this example. Monotonic means that given you can take only paths leading either down or to the right.
There is an equation to check correctness:
catalan(n) := nCr(2*N, N) / (N+1);
Therefore:
catalan(5) = nCr(10,5)/6 = 42
The predecessors for a given node are calculated as follows:
row = floor(n/5);
col = (n-1) % 5;
if ( row > 0 )
{ cur.addpred((row-1)*5+col+1); }
else
{ cur.addpred(0); }
if ( col > 0 )
{ cur.addpred(row*5+col); }
else
{ cur.addpred(0); }
| 