複合式用戶可規劃閘陣列之技術映射

Abstract

本論文探究複合式(complex)用戶可規劃閘陣列(Field-Programmable Gate Arrays, FPGAs)之技術映射(technology mapping)問題，並提出演算法。 用戶可規劃閘陣列已被廣泛地應用在積體電路的原型(prototype)設計，複合式用戶可規劃閘陣列進一步提供了更快的速度和更高的密度，它的架構包含了硬繞線(hard-wired)、非同質性(non-homogeneous)和有限利用扇出(limited accessible fanouts)等特性，本論文針對這些特性提出兩個全新演算法，分別針對面積和速度進行最佳化。 在面積最佳化演算法中，我們利用多扇出樣本圖庫(multiple-fanout pattern graph library)來表示複合式邏輯區架構(logic block architecture)，並運用預先映射(pre-mapping)的技巧來動態(dynamically)產生主題圖(subject graph)。我們也為主題圖涵蓋(subject graph covering)問題提出新的匹配(matching)及涵蓋(covering)演算法。 在速度最佳化演算法中，我們針對硬繞線和非同質性用戶可規劃閘陣列提出一個保證速度最佳化的技術映射演算法，為了讓傳統的標記-映射(labeling-mapping)演算法能夠處理硬繞線的特性，我們提出二維標記(two-dimensional labeling)的方法和複合節點分割(complex node cut)演算法。

This dissertation explores the technology mapping problem for complex Field-Programmable Gate Arrays (FPGAs). FPGAs have been widely used for implementing prototypes of ASICs for their short turnaround time. Complex FPGAs further support faster speed and higher density. Its architecture features hard-wired connections, non-homogeneous logic blocks, and limited accessible fanouts. This dissertation proposes two new technology mapping algorithms for optimizing for area and delay respectively. In the area-driven algorithm, we use a multiple-fanout pattern graph library to model the complex logic block architecture and a pre-mapping technique to generate the subject graph dynamically. A new matching algorithm and a new covering algorithm are also developed for the subject graph covering. In the delay-driven algorithm, we present a guaranteed delay optimal technology mapping algorithm for hard-wired non-homogeneous FPGAs. To handle the hard-wired features with traditional labeling-mapping algorithm, we propose a two-dimensional labeling approach and a complex node cut algorithm.