• 6.4.1 Initialization - Flattening the User Specified Graph
• 6.4.2 Absorb and Merge
• 6.4.3 Cluster Iterator Classes

The class Cluster is derived from the DynamicGalaxy and as such manages its own memory. The Cluster classes use ClusterPorts which are derived from GalPort. The main difference between the ClusterPorts and GalPorts is that ClusterPorts maintain a farSidePort pointer. We need this change in ClusterPort in order to easily iterate over the Clusters at any level of the clustering hierarchy. A ClusterPort::farSidePort pointer will only be NULL if the ClusterPort is aliased to a Star PortHole connected at higher level of the clustering hierarchy.

6.4.1 Initialization - Flattening the User Specified Graph

After the internals of the top-level Galaxy have been flattened, Clusters are constructed around each individual atomic Block. In that way, the scheduler writer can treat all the Blocks at each level (except the innermost level) as a Cluster. This property is maintained through any sequence of merge/absorb calls. An example initializeForClustering invocation is shown in figure 6-1, frames 1 and 2.

A facility for restoring the internal Ptolemy representation back to the original user-specified hierarchy is detailed in section 6.6.

6.4.2 Absorb and Merge

The basic clustering mechanisms are implemented with the virtual methods: Cluster::merge and Cluster::absorb. Both of these methods can take up to two arguments. The first argument is the Cluster to absorb/merge and the second argument(optional) specifies whether or not to remove the absorbed or merged Cluster from the original parent Galaxy.

The Cluster::merge method takes the contents of the Cluster being merged and moves them into the Cluster pointed to by the this pointer. A merge operation is communicative. A series of merge steps is shown in figure 6-1 frames 3 and 4.

The Cluster::absorb method takes the Cluster being absorbed and moves it into the Cluster pointed to by the this pointer. Unlike merge, absorb is not communicative as shown in figure 6-1 frames 5 and 5'.

The absorbed or merged Cluster is removed from the original parent Galaxy by default when Cluster::merge or Cluster::absorb is called. We provide three ways to update the graph after a clustering operation with differing levels of efficiency. These methods are detailed in the table 6-1. We first list some variable definitions:

• Let be defined as the number of Clusters in the parent Galaxy
• Let be defined as the number of PortHoles in this Cluster
• Let be defined as the number of PortHoles in the Cluster to absorb or merge

  TABLE 6-1: Complexity cost of absorb/merge step.

  Deletion/Update Method	Complexity to update at each clustering step
  Using merge/absorb in their default mode of operation. This is the most inefficient way to do clustering.
  GalTopBlockIter::remove We can use this method if the Cluster to absorb/merge was found using a GalTopBlockIter (or derived iterator class) on the parent Galaxy. The scheduler writer needs to do two things: remove the absorbed/merged cluster using from the parent Galaxy using the iterator's remove method. delete the removed Cluster using the C++ operator delete. This is the most efficient way of updating the graph after a clustering operation - but it is not always possible because we may be traversing the graph in some other way such as using a SuccessorIter.
  cleanupAfterCluster (defined in Cluster.{h,cc}) If we cannot use the previous method, we can leave the Cluster in the parent Galaxy list (it will be marked invalid automatically). The Cluster iterator classes automatically skip these invalid Clusters. Periodically (but not at each clustering step), the cleanupAfterCluster function should be invoked to remove and delete the invalid Clusters. This function will cost to execute, but since it is not done at each clustering step - the result on the overall complexity will be additive versus being multiplicative. For an example of how this is done, refer to: $PTOLEMY/src/domains/cg/hierScheduler/HierScheduler.cc.

6.4.3 Cluster Iterator Classes