From the parallel-execution graph we can also extract the profile of active tasks and busy links during parallel execution on the abundant clique. This profile reveals characteristics inherent to the algorithm at hand and is not influenced by partitioning and mapping to a specific multiprocessor. Figure 4 presents such a profile for a parallel execution of the Fast Multipole Method on a problem instance with 15,000 particles distributed according to the uniform distribution, fifteen particles per quadtree-leaf, and a ten coefficient approximation. This is followed by a long period during which the available parallelism is very low. The execution ends in a third, long phase where the number of active tasks is high.
Similar remarks hold for the channel utilizations in the abundant clique.
As the algorithm moves towards the root, the number of internal nodes decreases logarithmically and thus the number of parallel tasks drops very quickly. In the second phase, the algorithm moves from the root of the tree to its nodes, exchanging messages between nodes belonging to the same neighborhoods. The available parallelism is very small initially and increases as the algorithm approaches the quadtree leaves. Another interesting observation relates to resource utilization of the abundant clique. For instance, the parallel-execution graph of the above example has clusters and therefore, the corresponding abundant clique would have processors and unidirectional links.