閘矩陣配置演算法則

Abstract

最近幾年發展出了一種CHIP LAYOUT STYLE ，稱為GATE MATRIX 。所謂GATE MATRIX 它是由一些行和一些列相交組合而成。在GATE MATRIX 上，通常水平的長度是固定的 ，所以垂直的長度決定了整個GATE AMTRIX 所需的面積，我們的問題就是在於如何重 排GATE MATRIX 上行的順序，使得GATE MATRIX 所佔用的軌道（HORIZONTAL TRACK） 數目最少，以節省所需的面積。在本篇論文中，我們將提出一個CLUSTERING的ALGORI THM 來做GATE MATRIX LAYOUT。這個ALGORITHM 會把CONNECTION GRAPH撕成一些碎片 以決定行的挑列順序。此外我們也IMPLEMENT 了LI的ALGORITHM 和一個RECURSIVEP A RTITIONING的ALGORITHM 。 我們選了40組INPUT DATA 來測試以上的ALGORITHM ，實 驗結果看來，我們所提的CLUSTERRING 的ALGORITHM 還相當不錯。