動態可重組態現場可程式閘陣列結構與電腦輔助設計

Abstract

近來動態可重組態現場可程式閘陣列（DRFPGAs）已經獲得很大的關注，因其可利用時間共享（time-sharing）方式來增進邏輯效能。在動態可重組態現場可程式閘陣列中，一個較大的電路設計，被分割成許多部份(stages)來共用較小的實體裝置(physical device)，這比用傳統的現場可程式閘陣列需較小的實體裝置。 動態可重組態現場可程式閘陣列的繞線資源，包含預先製造好的導線段(segments)和可程式開關(switches)，動態可重組態現場可程式閘陣列的繞線，就是程式化其開關來連接這些導線段，而這些開關通常具有高電阻、高電容的特性，並佔很大的面積，所以在面積和延遲時間(delay)的限制下，如何設計高可繞度的開關模組是很重要的課題。 因為在動態可重組態現場可程式閘陣列中，一個電路邏輯是時序多工的(time-multiplexed)，所以他的分割問題(partitioning)和放置問題(placement)是與傳統的分割問題和放置問題不一樣的，其最主要的不同是，電路中的元件有一定的先後執行順序。然而，分割和放置的方法會決定一個動態可重組態現場可程式閘陣列中所需連接線的個數，且會對繞線有直接的影響，因此設計一個好的分割和放置的方法來減少所需連接線的個數是非常重要的事。 本論文著眼於動態可重組態現場可程式閘陣列中兩個重要的問題：結構和電腦輔助設計演算法。 □ 結構︰ 在動態可重組態現場可程式閘陣列中有兩種開關模組︰開關方塊(switch block)和開關矩陣(switch matrix)。在本篇論文中我們提出近似萬用(quasi-universal)開關矩陣，其在所有相同面積開關矩陣中具有最高可繞度。緊接著我們針對三維的現場可程式閘陣列，提出一種設計和分析萬用開關方塊的技巧。 □ 電腦輔助設計演算法︰ 在這論文中，我們提出一般性的整數線性規劃(integer linear programming)的方法來解決多階(multi-stage)順序限制(precedence-constrained)分割問題，此方法相當彈性，它能很快速的應用到類似的分割問題。緊接著，我們提出一個新的放置問題，其動機是來自於動態可重組態現場可程式閘陣列的特殊結構。針對這個放置問題，我們提出一個有效的測度標準，它能同時考慮繞線長度、記憶體需求、電能的消耗量。在這個新的測度標準考量下我們提出一個三階段的方案，包含：分割、初始化的放置和精煉放置，來解決此一新的放置問題。

Improving logic efficiency by time-sharing, Dynamically Reconfigurable FPGAs (DRFPGAs) have attracted much attention recently. In a DRFPGA, a virtual large design is partitioned into multiple stages (or partitions) to share the same smaller physical device than that occupied by a traditional FPGA. DRFPGAs interconnection resources consist of pre-fabricated wire segments and programmable switches. Routing in DRFPGAs is performed by programming the switches to connect the wire segments. The switches usually have high resistance and capacitance, and consume a large amount of area. It is thus of particular importance to design switch modules that maximize routability under the area and delay constraints. Because the logic and interconnect needed for a circuit is time-multiplexed on a DRFPGA, its partitioning and placement problems are different from their traditional ones. The major difference is that the execution order of circuit elements must follow the precedence and capacity constraints in the DRFPGAs. The partitioning and placement algorithms determine the number of interconnections needed by a DRFPGA and greatly affect routing. Thus it is desirable to develop effective partitioning and placement to minimize the interconnection cost. This thesis focuses on two important issues for DRFPGAs: architectures and CAD algorithms. □ Architectures: There are two types of switch modules: switch matrices and switch blocks. In this thesis, we present quasi-universal switch matrices which have the maximum possible routing capacities among all switch matrices of the same size. Next, we propose methods for designing and analyzing universal switch blocks which are cheapest for three-dimensional FPGAs. □ CAD algorithms: In this thesis, we present generic integer linear programming (ILP) formulations for the multi-stage precedence-constrained partitioning problems. The ILP-based formulations are so flexible that they can readily apply to the partitioning problems with various objectives and constraints. Next, we introduce a new placement problem motivated by the special DRFPGA architectures. For the placement, we develop an effective metric that can consider wirelength, storage requirement, and power consumption simultaneously. With the considerations of the new metric and the precedence constraints, we then present a three-stage scheme of partitioning, initial placement generation, and placement refinement to solve the new placement problem.