Abstract
隨著超大型積體電路(VLSI) 複雜度的增加，測試所佔的成本也跟著愈來 愈高，甚至到了超過設計所佔的成本。把測試的成本控制在一個可接受的 範圍內變得非常重要，而考慮測試度的設計 (design for testability ； DFT)方式，是達到這個目標的一種途徑。在順序性電路(sequential circuit) 加入掃描正反器的設計，已經是一種風行的 DFT 方法。掃描設 計(scan design) 在電路上加入測試模式的控制訊號，在測試模式將正反 器串結成一移位暫存器，可以讓這個移位暫存器的狀態變成可控制及可觀 察。部分掃描(partial scan) 的設計同時有較低的測試複雜度及面積成 本，是一種很風行的掃描設計方法。在次微米技術的時代，繞線( routing) 已變成積體電路面積，時序(timing)和功率消耗(power consumption) 的主要因素。在本論文中，我們探討如何將掃描正反器作 鏈結，來達到最小的繞線區域。首先在邏輯設計層次來決定串結掃描正反 器的順序，為了能決定更正確的決定掃描正反器順序，要佈局資訊的考量 來串結正反器。我們將串結掃描正反器的問題描述成 traveling salesman problem(TSP)，有兩種啟發性的 (heuristic) 的方法：貪婪 法(greedy method) 及配對式演算法(matched-based algorithm)來解決 TSP 問題。在加入佈局資訊的串結正反器中，作不同的成本定義方式，當 考慮擺置和繞線資訊，而且動態的更新資訊可以得到最好的結果。 In an era of sub-micron technology, routing is becoming a dominant factor in area, timing and power consumption. In this paper, we study the problem of scan flip-flops chaining with the objective of achieving minimum routing area overhead. The first attempt is to chain the flip-flops in logic level. In order to make more accurate decision on chaining flip-flops, the second attempt is to perform the chaining of scan flip- flops taking layout information into consideration. Specifically, we show that chaining problem is a traveling salesman problem (TSP). Then, two heuristics, greedy and matching-based algorithms, are proposed to solve the TSP problem. Various cost functions will be defined which take layout information into account. Benchmarking results show that the cost function achieves the best results when it considers placement and routing information and is dynamically updated.