Identifying critical paths

The scope of the profiling tool is not limited to merely visualising the computation and communications patterns at each of the cost-centres, but aims to identify critical cost paths within programs. Critical paths are visualised by shading each of the nodes in the graph with a colour ranging from white to red. A red node corresponds to a bottleneck (or `hot-spot'!) in the program. There are seventeen different critical paths that can be identified by the profiling tool. Five different types of critical path can be selected by pressing one of the following icons:

	synchronisation
	local computation time
	communication time
	computation or communication idle time
	h-relation size

For all but the first of these types of critical path, four different options may be applied:

	Absolute	identifies the nodes with the largest maximum cost.
	Absolute imbalance	identifies the nodes with the largest difference between the maximum and average cost.
	Relative imbalance	identifies the nodes with the largest percentage-wise deviation between maximum and average cost.
	Weighted	identifies the nodes with both the largest difference between the maximum and average cost and the largest percentage-wise deviation between maximum and average cost. Informally, this path combines the prior two critical paths.

The role of the absolute critical path is to identify those nodes that constitute the major components (cost-wise) within the program. In contrast, the absolute imbalance path highlights those nodes that are amenable to improvement due to the underlying imbalance in the maximum and average cost. However, the problem with this metric is that nodes with large cost value and small deviation might be identified as `more critical' than nodes with smaller cost value but larger deviation. As the later of these nodes are more amenable to improvement, the relative imbalance critical path is useful in determining the nodes that are imbalanced, irrespective of their size. Finally, the weighted critical path combines the advantages of the previous two approaches.

In Figure 3 the absolute imbalance in h-relation size is used to identify critical paths. The tool clearly shows that the one-stage algorithm reflects a large amount of imbalance in communication. We quantify this imbalance in terms of the form (12% | 7%). This identifies that the average cost is 12% of the maximum, whereas the minimum is 7%. Clearly, such small percentages for the average and minimum cost identify large imbalances in the algorithm. The tool correctly identifies that there is a similar imbalance in the first superstep of the two-stage algorithm (initial distribution of data)---it is noted that this imbalance is unavoidable. However, it is worth noting that the tool does not identify this imbalance as severe as the imbalance underlying the one-stage algorithm, as it is caused by a smaller h-relation, i.e., an (n/p)(p-1)-relation compared to an n(p-1)-relation. Finally in the last superstep of the two-stage broadcast, there is virtually no imbalance (100% | 100%) within the node labelled bcast.c line 41.