Partitioning Algorithm

The CPA partitioning algorithm can briefly be described as follows:

1. Define a set of unprocessed nets. Initially, put all signal nets into this list.
2. Select Net A from the set of unprocessed nets. Mark Net A as valid.
3. Create a "halo" around Net A by specifying the coupling distance, and determine what other nets are nearby. This set of nearby nets is called the neighborhood of A. Mark all of the nets in the neighborhood of A as nonvalid.
4. Set the active neighborhood to be the neighborhood of A.
5. Select Net B from the active neighborhood and mark it as valid. Determine its neighborhood, and add any nets in the neighborhood of B that were not already in the active neighborhood to the active neighborhood. Mark these added nets as nonvalid.
6. If the number of nets in the active neighborhood is less than the user-specified preferred net group size, repeat the previous step. The size of the active neighborhood grows toward your preferred net group size, and may even exceed it. When this happens, proceed to the next step.
7. For each nonvalid Net C in the active neighborhood, check to see if all of the nets in the neighborhood of C are in the active neighborhood. If they are, mark Net C as valid for this partition.
8. The active neighborhood, which consists of both valid and nonvalid nets, becomes a new partition to be sent to the solver. Those nets that were marked valid are removed from the set of unprocessed nets.
9. If any unprocessed nets remain, go back to Step 2. If none remain, the partitioning is complete.
   Note:

   The preferred net grouping size is only a guideline. Actual partition sizes may be somewhat larger.

   The coupling distance you specify greatly influences the size of generated partitions. If it is too large, then the number of nets in each partition may be unnecessarily high.