一般性萬用開關區塊之設計與分析

Abstract

對於一個每邊寬度為W個接腳的開關區塊 (switch block) 而言，若符合此開關區塊每邊寬度限制 (dimension constraint，換言之，每邊的繞線個數不能超過W) 的任何一組繞線皆能同時在此開關模組上繞線成功，我們便稱此開關區塊為“萬用” (universal)。在本論文中，我們提出一個演算法用以建構每邊寬度為W個接腳的N邊形萬用開關區塊。我們所建構的萬用開關區塊的彈性係數 (flexibility) 為N-1，而每個區塊含N(N-1)W/2個開關。我們證明要建構一個萬用的開關區塊，所需要使用的開關數量絕不能少於N(N-1)W/2個。除此之外，我們亦可利用萬用開關區塊的可分解性質（decomposition property），在實際製作開關區塊時，獲取較小面積的佈局設計。在本論文中，我們比較幾種不同結構的開關區塊，實驗結果顯示我們的萬用開關區塊確實能夠在晶片層 (chip level) 上增進可繞度。依據實驗結果，我們也分析開關區塊結構與繞線之間的交互作用，並且對此交互作用的最佳化提供幾項見解。

A switch block M with W terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of M is at most W) is simultaneously routable through M. In this thesis, we present an algorithm to construct N-sided universal switch blocks with N(N-1)W/2 terminals on each side. Each of our universal switch blocks has N(N-1)W/2 switches and switch-block flexibility N-1. We prove that no switch block with less than W switches can be universal. Further, the decomposition property of a universal switch block provides a key insight into its layout implementation with a smaller silicon area. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. Experimental results demonstrate that our universal switch blocks improve routability at the chip level. Based on extensive experiments, we also explore the interactions between switch-block architectures and routing and provide several suggestions for optimization of the interactions.