The proposed method is a combination of the non-optimal and optimal solutions. At first, the design space is reduced by using heuristic approach. Next, the best solution form the reduced search space is extracted. The pseudo-code of the proposed algorithm is shown in Figure 1.
Function SelectPaths(U, NSPC)
1:Find the correlations between the paths
2: Prune the paths
3: Generate correlation Matrix
4: Sort the items in the Matrix
5: Prune the Matrix
6: Write ILP formulation
Figure 1- The pseudo-code of the proposed selection method
In the first step, the correlation between each two paths of the U, is calculated. The correlation between two paths of i and j, Cij, is equal to the percent of the gates of ith path which are shared by the path j. If Cij is equal to 1, it means that path i is completely inside path j. In this case, if jth path violates the TC, ith path violates too. Hence, in this case ith path is removed from the U. Also, in the case where the Cij=Cji=1, the path, ith or jth path, with the larger slack time is removed. By this pruning some paths are removed from U, which we call it U' in this case. The number of items in U' is expressed by n'.
Next, a n'×n' matrix, M, is generated where the (i,j)th element of M is a tuple which its first item is j and its second item is the correlation between ith and jth paths (Cij). Hence, the ith row of this matrix shows the correlation of ith path with all other paths in U'. Note that -1 is considered as the value of Cii. Therefore, the matrix M will be
M=[■((1,-1)&…&(n^',C_(1,n^' ))@⋮&⋮&⋮@(n^',C_(n^',1))&…&(n^',-1))] (1)
Next, each row of the matrix is sorted separately based on the value of Cij of tuples from the high to low. After sorting, the tuples which contain the largest Cij values among the other tuples in their corresponding row are placed in the first column, while the smallest Cij are placed in the last column. The tuples in the small column indexes of ith row address paths which if ith path violates the TC, these paths violate the TC with high probability. Hence, selecting ith path instead of these paths may be a good choice. On the other hand, the larger column index belong to the paths which TC violation by them and ith path in a chip is small, hence, selecting ith path instead of them is not an efficient selection. Therefore, considering the paths in the small and large indexes columns are important for path selection. Hence, to reduce the search space and decreasing the selection runtime, M is pruned by removing intermediate column. Additionally, the last column which contains (i,-1) tuple is removed. The new matrix, M^', is an n^'×2m, where m is a user define parameter which provides the number of columns which should remain from the first columns and last columns separately.
Now, by using ILP, the best paths from M' is selected. The objective function of the proposed path selection during the optimal selection is formulated by