四分樹資料結構在CAD應用上之研究

Abstract

隨著積體電路(IC)愈來愈複雜，電腦輔助設計系統(CAD system)在積體電 路設計的過程中，已是不可或缺的工具。積體電路設計者往往需要藉助電 腦輔助設計系統，才能夠快速完成他所要設計的線路。在輔助設計系統中 ，交談式佈局編輯器(layout editor )，設計規則檢查程式(design rule checking)，佈局擠壓器(layout compactor)，是設計者常常會使用 到的軟體。這些軟體均需要在二維空間上作區域搜尋，以找出一些特定的 物件(object)。四分樹(quad tree)是一個很普遍用以支援區域搜尋的資 料結構。支援區域搜尋的資料結構有三個效能目標(performance goal)： 快速大區域搜尋，快速小區域搜尋及經濟的記憶體使用量。就我們所知， 目前所提出的資料結構，沒有一個能夠同時達到上述三個目標。基於 這個因素，本論文即對四分樹作深入的探討。首先我們提出四分樹的可塑 性問題(adaptability problem)。四分樹是藉由反覆的分割二維空間區域 而建成的。它分割區域(quad)的條件如下:只要此區域中物件個數超過低 限值(threshold)，此區域就等分成四塊大小相等的正方形。 he quad tree is a widely used data structure for region queries . Quad trees normally perform reasonably efficient on the majority of layout data, but could perform very poor on certain extreme data. This demonstrates the quad tree's deficiency in its adaptability to peculiar layout data. We address two aspects of the adaptability problem. On the one hand, the threshold of a quad tree is allowed to change in order to match the global complexity of the layout. On the other hand, a new quad subdivision criterion is developed which adapts a quad tree to the nonuniform distribution of objects with various sizes. Experiments have indicated that the two techniques are indeed useful in coping with the peculiarity of extreme layout data. esides the adaptability problem, the design of efficient region query data structure is also studied.