parallele-programmierung/u08-2/README.md

Problem 8.2: Recursive counting using Callable vs. ForkJoinTask

Class TreeSumSequential in the source code folder on the server builds a binary tree with a random structure with each node containing a random number. Then it sequentially computes for each node the number of prime numbers up to the number in this node (this computation is performed in two parts in order to simulate that it may become clear only during the processing of a node that some further computation effort is necessary – see method countPrimesInTree). Finally, the total number of prime numbers over all nodes it printed.

Extend this program by two more implementations of this tree-wide prime number counting:

• a concurrent one that uses a Callable for each node and a ThreadPoolExecutor
• a concurrent one that uses a ForkJoinTask for each node and the ForkJoinPool.commonPool()

The tasks for child nodes should be created and submitted about in the middle of processing the parent node, quite as in countPrimesInTree.

Compare the run times of the three implementations – if you like, also for different values of the configuration constants MAX_NUMBER_IN_NODE (corresponds to the size of a task) und MAX_NODES (an upper limit for the number of tasks which is reached provided that SUBTREE_THRESHOLD_PERCENT is large enough). The run time of a task depends on the depth of its node in the tree.

Since all three implementations compute the sum for the same tree, all three must print the same total number; you may thus use a comparison to the sequentially computed number as a correctness check of your concurrent implementations.