零偏斜時脈樹繞線系統實作

Abstract

本文提出並介紹摘在高速度超大型積體電路下處理並發展時脈繞線的一些技術，包含了BB(Balanced Bipartition) 和DME (Deferred-Merge Embedding) 兩個主要的演算法，是由Dr. K. D. Boese, Dr. A. B. Kahng, Dr. T.-H. Chao, Dr. Y.-C. Hsu, Dr. J-M. Ho提出的，此平面繞線的結構包含三個主要的部分，第一個部分是使用了DME(Deferred-Merge Embedding)的繞線演算法，用來建構一個平面時脈樹的相對拓樸，因此第二個部分則為BB(Balanced Bipartition)的繞線演算法，用來將一群點集分隔幾乎擁有相同負載的兩個子集合，第三部份則是處理實際細部繞線的演算法，上述的方法可快速且有效率的建構出所需的平面時脈繞線結果。

This thesis presents a set of techniques for developing a zero skew clock routing system with a BB partitioning method and a DME heuristic method proposed by Dr. K. D. Boese, Dr. A. B. Kahng, Dr. T.-H. Chao, Dr. Y.-C. Hsu, and Dr. J.-M. Ho in high-speed VLSI designs. The clock routing framework has three key components. The first component employs a DME (Deferred-Merge Embedding) algorithm to construct a clock tree topology and to determine best internal node locations. The routing construction is based on a balanced partitioning method. Thus the second component is a partitioning method called BB to separate a group into two subgroups which have almost the same loads. The third component will process the part of detailed routing. These schemes together give a good enhancement in convenient usage and performance to build a zero clock routing result.