Pin permutation algorithm for improving over-the-cell channel routing

In standard cell design, some of the cell terminals and gates are permutable. Therefore, it is important for an over-the-cell channel router to take advantage of this so as to obtain better results. A dynamic programming based algorithm is presented to determine proper gate and terminal positions such that, when over-the-cell routers are used, the area above and below the channel can be utilized more effectively and the channel density can be greatly reduced. Experimental results show that our proposed algorithm indeed considerably reduces the channel density.