栅阵列排序的一个有效算法

An Effective Algorithm for Gate Matrix Layout

栅阵列排序问题已被证明是一个ＮＰ一完全问题，该文提出一个新的启发式算法。该算法通过建立层函数的概念，将栅阵列的排序问题转化为求层函数的最小值的优化问题。算法的时间复杂度为Ｏ（ｎｘｐ３），其中ｎ为线网的个数，ｐ为主栅的个数。

A heuristic algorithm for gate matrix layout which had been proved to be anNp-complete problem is put forward in this paper.The concept of“layer”function is established,therefore the problem of gate matrix layout is converted into finding the optimum solution of“layer”function in the algorithm. The time complexity of this algorithm isO(nxp3),here n is the number of nets and p is the number of dominant gates.