Algorithms for Conflict Resolution

Algorithms for conflict resolution is presented in this section. The input is a resource binding consisting of a number of instance operation sets. The instance op tion sets in / are selected in turn. For a given instance operation set O, its operation clusters are first identified using standard graph techniques 

Identify the orientation Vc- The orientation is obtained by categorizing the edges based on the sign of their weights. The roots and leaves 

Select a polarization Pc( 0- particular polarization with root r and leaf / is selected. If a cycle exists in the polarization or if the polarization violates the condition in Theorem 7.2.4, then it is discarded and another polarization is selected. If all polarizations are invalid, then the resource conflicts fm the given operation cluster cannot be resolved under timing constraints. 

Apply exact ordering algorithm. A branch-and-bound ord g algorithm is applied if the heuristic fails to find a solution. The exact algorithm is guaranteed to find a solution if one exists. Theorem 7.2.5 is used as the cost function to prune the branch-and-bound search. 

After the operations within each clusters have been serialized, the clusters are linearly ordered compatible with the original partial order. This linear order can be constructed in linear-time with respect to the number of clusters. The order in which the clusters are visited and resolved is important Therefore, if the above steps fail to find a valid ordering, then this order can be changed and the above steps repeated. By Theorem 6.2.1 and Lemma 6.2.3, a solution to conflict resolution implies that a valid relative schedule exists. In this case, the binding is known to be valid and the iterative incremental scheduling algorithm can be performed to compute the time offsets. 

---