published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

As the sizes of modern circuit designs become bigger and bigger, implementing those large circuits into FPGA become arduous. The state-of-the-art academic FPGA place-and-route tool, VPR, has good quality but needs around a whole day to complete a placement when the input circuit netlist contains millions of lookup tables, excluding the runtime needed for routing. / To speed up the placement process, we propose a routability-driven placement algorithm for FPGAs, which adopts techniques used in ASIC global placer. Our placer follows the lower-bound-and-upper-bound iterative optimization process in ASIC placers like Ripple. The total half perimeter wirelength (HPWL) of the circuit is used as the objective cost function and it modeled using the Bound2Bound net model. In lower bound computation, a placement solution with the minimum HPWL is determined by the conjugate gradient method. In upper bound computation, an almost-legalized result is produced by spreading cells linearly in the whole placement area. Those positions are then served as fixed-point anchors and fed into the next lower bound computation. Furthermore, global routing will be performed in the upper bound computation to estimate the routing segments usage, as a mean to consider congestion in the placement. The two bounds computations are computed alternatively until their results converge. / We tested our approach using 20 MCNC benchmarks and 16 large benchmarks for performance and scalability. Experimental results show that based on the island-style architecture which VPR is most optimized, our approach can obtain a placement result 8× faster than VPR with 2% more in channel width, or 3× faster with 1% more in channel width when considering congestion either. Our approach is even 20× faster in placing large benchmarks having over 50,000 lookup tables, however, with 10% more in channel width. Based on the Xilinx Virtex-5 architecture from a recent related work, we can out-perform VPR by reducing the channel width by 3% with almost 3× speedup in runtime. / 現今的電路設計得愈來愈大，要把這些巨大的電路實現在現場可程式邏輯門陣列(FPGA)上變得愈來愈困難，由其在布局及布線程序上變得十分耗時。儘管在一般的情況下，現時在學術領域中，最先進的用在FPGA上的布局及布線工具能夠提供高質素的布局結果，但當所需要布局的電路所包含的邏輯元件數達到數百萬個以上時，該工具也要耗費一整天的時間才能完成整個布局程序，其中並未計算之後布線程序所額外需要的時間。 / 有見及此，我們參考了一些應用在特殊應用積體電路(ASIC)設計軟體上的布局方法，並提出了一個專為FPGA而設的偏向優化Routability的布局算法來縮短布局程序所需要的時間。我們的算法以Bound2Bound模型來模擬電路內邏輯元件間的接線，並估算其Half-Perimeter線長(HPWL)來作為我們的目標函數進行優化。我們採用了一些ASIC布局軟體，如Ripple內的上限及下限交互計算的迭代優化程序。在下限的運算過程中，我們在無視節點重疊的情況下，使用了共軛梯度法來找出HPWL的最少值。在上限的運算過程中，我們把在下限計算找到的結果平均散佈在整個可布局的區域內，從而減少節點重疊的情況來得出一接近有效的布局結果。接著，這些節點的位置會被用作定點錨，附加在下一次的下限計算中，並引導它得出一節點重疊相對較少的布局結果。此外，我們可以選擇在上限的運算過程中加入Global Routing程序來估計該布局結果所需的線段數，從而在布局過程中考慮布線過份擁塞的情況。上限及下限的計算會不斷交互進行，直至雙方所得的結果聚合為止。 / 我們使用了20個MCNC基準電路及16個大型基準電路，來測試我們的布局算法的性能和可擴展性。實驗結果指出，針對島狀結構的FPGA，我們的算法能夠比VPR快8倍得出布局結果，但其通道寬度(Channel Width)卻增加了2%。如果在考慮布線擁塞度的情況下，我們的算法能夠比VPR快3倍，但其通道寬度卻增加了1%。再者，對於一些擁有超過50000個邏輯元件的大型基準電路，相比於VPR，雖然我們的算法能夠提供20倍的速度增長，但其布局結果的通道寬度卻增加了10%。如果我們使用在最近的相關研究中使用的Xilinx Virtex-5結構的話，我們的算法能夠比VPR快接近3倍得出布局結果，並且減少約3%的通道寬度。 / Lam, Ka Chun. / Thesis M.Phil. Chinese University of Hong Kong 2014. / Includes bibliographical references (leaves 64-70). / Abstracts also in Chinese. / Title from PDF title page (viewed on 12, October, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.

Chu-Keung Chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 88-92). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation and Aims --- p.1 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Structure of the Thesis --- p.4 / Chapter 2 --- Literature Review --- p.6 / Chapter 2.1 --- Introduction --- p.6 / Chapter 2.2 --- Complete Algorithms --- p.7 / Chapter 2.2.1 --- Parallel Checking --- p.7 / Chapter 2.2.2 --- Mom's --- p.8 / Chapter 2.2.3 --- Davis-Putnam --- p.9 / Chapter 2.2.4 --- Nonchronological Backtracking --- p.9 / Chapter 2.2.5 --- Iterative Logic Array (ILA) --- p.10 / Chapter 2.3 --- Incomplete Algorithms --- p.11 / Chapter 2.3.1 --- GENET --- p.11 / Chapter 2.3.2 --- GSAT --- p.12 / Chapter 2.4 --- Summary --- p.13 / Chapter 3 --- Algorithms --- p.14 / Chapter 3.1 --- Introduction --- p.14 / Chapter 3.2 --- Tree Search Techniques --- p.14 / Chapter 3.2.1 --- Depth First Search --- p.15 / Chapter 3.2.2 --- Forward Checking --- p.16 / Chapter 3.2.3 --- Davis-Putnam --- p.17 / Chapter 3.2.4 --- GRASP --- p.19 / Chapter 3.3 --- Incomplete Algorithms --- p.20 / Chapter 3.3.1 --- GENET --- p.20 / Chapter 3.3.2 --- GSAT Algorithm --- p.22 / Chapter 3.4 --- Summary --- p.23 / Chapter 4 --- Field Programmable Gate Arrays --- p.24 / Chapter 4.1 --- Introduction --- p.24 / Chapter 4.2 --- FPGA --- p.24 / Chapter 4.2.1 --- Xilinx 4000 series FPGAs --- p.26 / Chapter 4.2.2 --- Bitstream --- p.31 / Chapter 4.3 --- Giga Operations Reconfigurable Computing Platform --- p.32 / Chapter 4.4 --- Annapolis Wildforce PCI board --- p.33 / Chapter 4.5 --- Summary --- p.35 / Chapter 5 --- Implementation --- p.36 / Chapter 5.1 --- Parallel Graph Coloring Machine --- p.36 / Chapter 5.1.1 --- System Architecture --- p.38 / Chapter 5.1.2 --- Evaluator --- p.39 / Chapter 5.1.3 --- Finite State Machine (FSM) --- p.42 / Chapter 5.1.4 --- Memory --- p.43 / Chapter 5.1.5 --- Hardware Resources --- p.43 / Chapter 5.2 --- Serial Graph Coloring Machine --- p.44 / Chapter 5.2.1 --- System Architecture --- p.44 / Chapter 5.2.2 --- Input Memory --- p.46 / Chapter 5.2.3 --- Solution Store --- p.46 / Chapter 5.2.4 --- Constraint Memory --- p.47 / Chapter 5.2.5 --- Evaluator --- p.48 / Chapter 5.2.6 --- Input Mapper --- p.49 / Chapter 5.2.7 --- Output Memory --- p.49 / Chapter 5.2.8 --- Backtrack Checker --- p.50 / Chapter 5.2.9 --- Word Generator --- p.51 / Chapter 5.2.10 --- State Machine --- p.51 / Chapter 5.2.11 --- Hardware Resources --- p.54 / Chapter 5.3 --- Serial Boolean Satisfiability Solver --- p.56 / Chapter 5.3.1 --- System Architecture --- p.58 / Chapter 5.3.2 --- Solutions --- p.59 / Chapter 5.3.3 --- Solution Generator --- p.59 / Chapter 5.3.4 --- Evaluator --- p.60 / Chapter 5.3.5 --- AND/OR --- p.62 / Chapter 5.3.6 --- State Machine --- p.62 / Chapter 5.3.7 --- Hardware Resources --- p.64 / Chapter 5.4 --- GSAT Solver --- p.65 / Chapter 5.4.1 --- System Architecture --- p.65 / Chapter 5.4.2 --- Variable Memory --- p.65 / Chapter 5.4.3 --- Flip-Bit Vector --- p.66 / Chapter 5.4.4 --- Clause Evaluator --- p.67 / Chapter 5.4.5 --- Adder --- p.70 / Chapter 5.4.6 --- Random Bit Generator --- p.71 / Chapter 5.4.7 --- Comparator --- p.71 / Chapter 5.4.8 --- Sum Register --- p.71 / Chapter 5.5 --- Summary --- p.71 / Chapter 6 --- Results --- p.73 / Chapter 6.1 --- Introduction --- p.73 / Chapter 6.2 --- Parallel Graph Coloring Machine --- p.73 / Chapter 6.3 --- Serial Graph Coloring Machine --- p.74 / Chapter 6.4 --- Serial SAT Solver --- p.74 / Chapter 6.5 --- GSAT Solver --- p.75 / Chapter 6.6 --- Summary --- p.76 / Chapter 7 --- Conclusion --- p.77 / Chapter 7.1 --- Future Work --- p.78 / Chapter A --- Software Implementation of Graph Coloring in CHIP --- p.79 / Chapter B --- Density Improvements Using Xilinx RAM --- p.81 / Chapter C --- Bit stream Configuration --- p.83 / Bibliography --- p.88 / Publications --- p.93

Tsoi Kuen Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 84-92). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Objectives --- p.3 / Chapter 1.3 --- Contributions --- p.3 / Chapter 1.4 --- Thesis Organization --- p.4 / Chapter 2 --- Background and Review --- p.6 / Chapter 2.1 --- Introduction --- p.6 / Chapter 2.2 --- Cryptographic Algorithms --- p.6 / Chapter 2.3 --- Cryptographic Applications --- p.10 / Chapter 2.4 --- Modern Reconfigurable Platforms --- p.11 / Chapter 2.5 --- Review of Related Work --- p.14 / Chapter 2.5.1 --- Montgomery Multiplier --- p.14 / Chapter 2.5.2 --- IDEA Cipher --- p.16 / Chapter 2.5.3 --- RC4 Key Search --- p.17 / Chapter 2.5.4 --- Secure Random Number Generator --- p.18 / Chapter 2.6 --- Summary --- p.19 / Chapter 3 --- The IDEA Cipher --- p.20 / Chapter 3.1 --- Introduction --- p.20 / Chapter 3.2 --- The IDEA Algorithm --- p.21 / Chapter 3.2.1 --- Cipher Data Path --- p.21 / Chapter 3.2.2 --- S-Box: Multiplication Modulo 216 + 1 --- p.23 / Chapter 3.2.3 --- Key Schedule --- p.24 / Chapter 3.3 --- FPGA-based IDEA Implementation --- p.24 / Chapter 3.3.1 --- Multiplication Modulo 216 + 1 --- p.24 / Chapter 3.3.2 --- Deeply Pipelined IDEA Core --- p.26 / Chapter 3.3.3 --- Area Saving Modification --- p.28 / Chapter 3.3.4 --- Key Block in Memory --- p.28 / Chapter 3.3.5 --- Pipelined Key Block --- p.30 / Chapter 3.3.6 --- Interface --- p.31 / Chapter 3.3.7 --- Pipelined Design in CBC Mode --- p.31 / Chapter 3.4 --- Summary --- p.32 / Chapter 4 --- Variable Radix Montgomery Multiplier --- p.33 / Chapter 4.1 --- Introduction --- p.33 / Chapter 4.2 --- RSA Algorithm --- p.34 / Chapter 4.3 --- Montgomery Algorithm - Ax B mod N --- p.35 / Chapter 4.4 --- Systolic Array Structure --- p.36 / Chapter 4.5 --- Radix-2k Core --- p.37 / Chapter 4.5.1 --- The Original Kornerup Method (Bit-Serial) --- p.37 / Chapter 4.5.2 --- The Radix-2k Method --- p.38 / Chapter 4.5.3 --- Time-Space Relationship of Systolic Cells --- p.38 / Chapter 4.5.4 --- Design Correctness --- p.40 / Chapter 4.6 --- Implementation Details --- p.40 / Chapter 4.7 --- Summary --- p.41 / Chapter 5 --- Parallel RC4 Engine --- p.42 / Chapter 5.1 --- Introduction --- p.42 / Chapter 5.2 --- Algorithms --- p.44 / Chapter 5.2.1 --- RC4 --- p.44 / Chapter 5.2.2 --- Key Search --- p.46 / Chapter 5.3 --- System Architecture --- p.47 / Chapter 5.3.1 --- RC4 Cell Design --- p.47 / Chapter 5.3.2 --- Key Search --- p.49 / Chapter 5.3.3 --- Interface --- p.50 / Chapter 5.4 --- Implementation --- p.50 / Chapter 5.4.1 --- RC4 cell --- p.51 / Chapter 5.4.2 --- Floorplan --- p.53 / Chapter 5.5 --- Summary --- p.53 / Chapter 6 --- Blum Blum Shub Random Number Generator --- p.55 / Chapter 6.1 --- Introduction --- p.55 / Chapter 6.2 --- RRNG Algorithm . . --- p.56 / Chapter 6.3 --- PRNG Algorithm --- p.58 / Chapter 6.4 --- Architectural Overview --- p.59 / Chapter 6.5 --- Implementation --- p.59 / Chapter 6.5.1 --- Hardware RRNG --- p.60 / Chapter 6.5.2 --- BBS PRNG --- p.61 / Chapter 6.5.3 --- Interface --- p.66 / Chapter 6.6 --- Summary --- p.66 / Chapter 7 --- Experimental Results --- p.68 / Chapter 7.1 --- Design Platform --- p.68 / Chapter 7.2 --- IDEA Cipher --- p.69 / Chapter 7.2.1 --- Size of IDEA Cipher --- p.70 / Chapter 7.2.2 --- Performance of IDEA Cipher --- p.70 / Chapter 7.3 --- Variable Radix Systolic Array --- p.71 / Chapter 7.4 --- Parallel RC4 Engine --- p.75 / Chapter 7.5 --- BBS Random Number Generator --- p.76 / Chapter 7.5.1 --- Size --- p.76 / Chapter 7.5.2 --- Speed --- p.76 / Chapter 7.5.3 --- External Clock --- p.77 / Chapter 7.5.4 --- Random Performance --- p.78 / Chapter 7.6 --- Summary --- p.78 / Chapter 8 --- Conclusion --- p.81 / Chapter 8.1 --- Future Development --- p.83 / Bibliography --- p.84

Zhou Lin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 50-53). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Aims and Contribution --- p.3 / Chapter 1.3 --- Thesis Overview --- p.4 / Chapter 2 --- Field-Programmable Gate Array and Routing Algorithm in VPR --- p.6 / Chapter 2.1 --- Commercially Available FPGAs --- p.6 / Chapter 2.2 --- FPGA Logic Block Architecture --- p.7 / Chapter 2.2.1 --- Logic Block Functionality vs. FPGA Area-Efficiency --- p.7 / Chapter 2.2.2 --- Logic Block Functionality vs. FPGA Delay-Performance --- p.7 / Chapter 2.2.3 --- Lookup Table-Based FPGAs --- p.8 / Chapter 2.3 --- FPGA Routing Architecture --- p.8 / Chapter 2.4 --- Design Parameters of FPGA Routing Architecture --- p.10 / Chapter 2.5 --- CAD for FPGAs --- p.10 / Chapter 2.5.1 --- Synthesis and Logic Block Packing --- p.11 / Chapter 2.5.2 --- Placement --- p.11 / Chapter 2.5.3 --- Routing --- p.12 / Chapter 2.5.4 --- Delay Modelling --- p.13 / Chapter 2.5.5 --- Timing Analysis --- p.13 / Chapter 2.6 --- FPGA Programming Technologies --- p.13 / Chapter 2.7 --- Routing Algorithm in VPR --- p.14 / Chapter 2.7.1 --- Pathfinder Negotiated Congestion Algorithm --- p.14 / Chapter 2.7.2 --- Routing Algorithm Used by VPR --- p.16 / Chapter 3 --- Connection-Switch Box Design --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.2 --- Connection-Switch Box Design Algorithm --- p.19 / Chapter 3.2.1 --- Connection between Logic Pins and Tracks --- p.20 / Chapter 3.2.2 --- Connection between Pad Pins and Tracks --- p.25 / Chapter 3.3 --- Switch Number Comparisons --- p.26 / Chapter 3.4 --- Experimental Results --- p.29 / Chapter 3.5 --- Summary --- p.32 / Chapter 4 --- Optimal MST-Based Graph Algorithm on FPGA Segmenta- tion Design --- p.37 / Chapter 4.1 --- Introduction --- p.37 / Chapter 4.2 --- MST-Based Graph Algorithm on FPGA Channel Segmentation Design --- p.39 / Chapter 4.2.1 --- Net Merging Problem of Row-Based FPGAs --- p.41 / Chapter 4.2.2 --- Extended Net Merging Problem of Symmetrical Array FPGAs --- p.44 / Chapter 4.3 --- Experimental Results --- p.46 / Chapter 4.4 --- Summary --- p.46 / Chapter 5 --- Conclusions --- p.48 / Bibliography --- p.50

投影機相機(projector camera)系統近年相當流行，主要原因是它能夠靈活地展示影像，使用戶有更大的自由度作出操作。手提式投影機的技術在過往幾年急速發展、漸見成熟，知名的家用電子産品生産廠閱始推出内置迷你投影機的手機和攝影機。另一方面手機的運算能力正急劇地提升，它們多都配置不同種類且功能强大的周邊設備。 / 本論文提出並討論一種基於現場可编程邏輯閘陣列(Field Programmable Gate Array, FPGA),並適用於嵌入式系统的特殊處理器。該特殊處理器專門處理來自相機的資料串流，透過一系列的象素圖像處理運算如圖像梯度和高斯模糊，去找出相中物件的邊緣，藉此分擔微處器在運算上的負擔。實驗結果明這特殊處理器可實現於低端的FPGA上並和普遍的微處器一起運作。 / 本論文第二個探討的主題是一個利用多模卡爾曼濾波器(Multiple Model Kalman Filter)的直線追踪器，並利用多個直線追踪器去作投影面板的追踪。利用卡爾曼濾波器只需要很低的運算能力的優點,我們的直線追踪器在嵌入式系统實測時能達到每秒200幀的速度。多模卡爾曼濾波器在實驗中有滿意的成績並較單卡爾曼濾波器和擴展卡爾曼濾波器優異。 / Projector-camera (ProCam in short) systems are getting very popular since the user can change the display area dynamically and enjoy more freedom in handling the device. In recent years, the mobile projector technology is becoming mature and manufacturers are shipping mobile phones and digital cameras with projectors. On the other hand, the computation power of a cell phone had dramatically increased and the cell phones are accompanied with large number of powerful peripherals. / In this thesis, the possibility of making an embedded Projector-camera (ProCam) system is investigated. A ProCam system is developed by our research group previously and designed for desktop Personal Computers(PCs). The system uses computer vision techniques to detect a white cardboard as the projection screen and uses particle filter to trace the screen in subsequent frames. The system demands a large computation power, unfortunately the power of low cost embedded system is still not powerful enough to implement the ProCam system.Therefore, specially designed hardware and computationally efficient algorithm are required in order to implement the ProCam system on an embedded system. / An FPGA based special processor to share the workload of the microcontroller in the embedded system is proposed and tested. This special processor will take the data stream of the camera as the inputs and apply pixel-wise image operators such as image gradient and Gaussian blur in order to extract the edge pixels. As a result, the workload of the microcontroller in the embedded system is reduced. The experiments show that the design can be implement on a low-end FPGA with a simple microcontroller. / A line tracker using Multiple Model Kalman lter is also proposed in this thesis. The aim of this tracker is to reduce the time on tracking the board. Benet from the low computation requirement of Kalman filter, the proposed line tracker can run in 200 fps on our testing embedded system. The experiments also show that the robustness of the Multiple Model Kalman filter is satisfactory and it outperforms the line trackers using single Kalman filter or extended Kalman filter alone. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Fung, Hung Kwan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 115-124). / Abstracts also in Chinese. / Abstract --- p.ii / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation and Objective --- p.1 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Thesis Organization --- p.5 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Projector-Camera System --- p.8 / Chapter 2.2.1 --- Static Projector-Screen --- p.9 / Chapter 2.2.2 --- Dynamic Projector-Screen --- p.13 / Chapter 2.3 --- Embedded Vision --- p.15 / Chapter 2.4 --- Summary --- p.25 / Chapter 3 --- System Overview --- p.26 / Chapter 3.1 --- System Design --- p.26 / Chapter 3.2 --- Our Approach --- p.28 / Chapter 3.2.1 --- Projector-camera system --- p.28 / Chapter 3.2.2 --- Smart Camera --- p.31 / Chapter 3.2.3 --- Quadrangle Detection and Tracking Module --- p.32 / Chapter 3.2.4 --- Projection Module --- p.32 / Chapter 3.3 --- Extension --- p.33 / Chapter 4 --- Smart Camera --- p.34 / Chapter 4.1 --- Introduction --- p.34 / Chapter 4.2 --- Hardware Overview --- p.35 / Chapter 4.3 --- Image Acquisition --- p.40 / Chapter 4.4 --- Image Processing --- p.42 / Chapter 4.4.1 --- RGB-to-Gray Conversion Module . --- p.44 / Chapter 4.4.2 --- Image Smoothing Module --- p.45 / Chapter 4.4.3 --- Image Gradient Module --- p.49 / Chapter 4.4.4 --- Non-maximum Suppression and Hysteresis Thresholding --- p.53 / Chapter 4.5 --- Summary --- p.55 / Chapter 5 --- Quadrangle Detection and Tracking --- p.57 / Chapter 5.1 --- Introduction --- p.57 / Chapter 5.2 --- Line Feature Extraction --- p.61 / Chapter 5.3 --- Automatic Quadrangle Detection --- p.62 / Chapter 5.4 --- Real-time Quadrangle Tracking --- p.68 / Chapter 5.4.1 --- Line Tracker --- p.69 / Chapter 5.5 --- Tracking Lose Strategy --- p.76 / Chapter 5.6 --- Recover from Tracking Failure --- p.77 / Chapter 5.7 --- Summary --- p.77 / Chapter 6 --- Implementation and Experiment Result --- p.79 / Chapter 6.1 --- Introduction --- p.79 / Chapter 6.2 --- Smart Camera --- p.79 / Chapter 6.3 --- Line Tracking --- p.87 / Chapter 7 --- Limitation and Discussion --- p.101 / Chapter 7.1 --- Introduction --- p.101 / Chapter 7.2 --- Limitation --- p.101 / Chapter 7.3 --- Summary --- p.105 / Chapter 8 --- Application --- p.107 / Chapter 8.1 --- Introduction --- p.107 / Chapter 8.2 --- Portable Projector-Camera System --- p.107 / Chapter 8.3 --- Summary --- p.110 / Chapter 9 --- Conclusion --- p.112 / Bibliography --- p.115

Cheung Chak Chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 101-114). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.iii / Vita --- p.v / Table of Contents --- p.vi / List of Figures --- p.x / List of Tables --- p.xiv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Aims and Contribution --- p.4 / Chapter 1.3 --- Thesis Overview --- p.5 / Chapter 2 --- VLSI Design Cycle --- p.6 / Chapter 2.1 --- Logic Synthesis --- p.7 / Chapter 2.1.1 --- Logic Minimization --- p.8 / Chapter 2.1.2 --- Technology Mapping --- p.8 / Chapter 2.1.3 --- Testability --- p.8 / Chapter 2.2 --- Physical Design Synthesis --- p.8 / Chapter 2.2.1 --- Partitioning --- p.9 / Chapter 2.2.2 --- Floorplanning & Placement --- p.10 / Chapter 2.2.3 --- Routing --- p.11 / Chapter 2.2.4 --- "Compaction, Extraction & Verification" --- p.12 / Chapter 2.2.5 --- Physical Design of FPGAs --- p.12 / Chapter 3 --- Alternative Wiring --- p.13 / Chapter 3.1 --- Introduction --- p.13 / Chapter 3.2 --- Notation and Definitions --- p.15 / Chapter 3.3 --- Application of Rewiring --- p.17 / Chapter 3.3.1 --- Logic Optimization --- p.17 / Chapter 3.3.2 --- Timing Optimization --- p.17 / Chapter 3.3.3 --- Circuit Partitioning and Routing --- p.18 / Chapter 3.4 --- Logic Optimization Analysis --- p.19 / Chapter 3.4.1 --- Global Flow Optimization --- p.19 / Chapter 3.4.2 --- OBDD Representation --- p.20 / Chapter 3.4.3 --- Automatic Test Pattern Generation (ATPG) --- p.22 / Chapter 3.4.4 --- Graph Based Alternative Wiring (GBAW) --- p.23 / Chapter 3.5 --- Augmented GBAW --- p.26 / Chapter 3.6 --- Logic Optimization by using GBAW --- p.28 / Chapter 3.7 --- Conclusions --- p.31 / Chapter 4 --- Multi-way Partitioning using Rewiring Techniques --- p.33 / Chapter 4.1 --- Introduction --- p.33 / Chapter 4.2 --- Circuit Partitioning Algorithm Analysis --- p.38 / Chapter 4.2.1 --- The Kernighan-Lin (KL) Algorithm --- p.39 / Chapter 4.2.2 --- The Fiduccia-Mattheyses (FM) Algorithm --- p.42 / Chapter 4.2.3 --- Geometric Representation Algorithm --- p.46 / Chapter 4.2.4 --- The Multi-level Partitioning Algorithm --- p.49 / Chapter 4.2.5 --- Hypergraph METIS - hMETIS --- p.51 / Chapter 4.3 --- The GBAW Partitioning Algorithm --- p.53 / Chapter 4.4 --- Experimental Results --- p.56 / Chapter 4.5 --- Conclusions --- p.58 / Chapter 5 --- Optimum FPGA Switch-Box Designs - HUSB --- p.62 / Chapter 5.1 --- Introduction --- p.62 / Chapter 5.2 --- Background and Definitions --- p.65 / Chapter 5.2.1 --- Routing Architectures --- p.65 / Chapter 5.2.2 --- Global Routing --- p.67 / Chapter 5.2.3 --- Detailed Routing --- p.67 / Chapter 5.3 --- FPGA Router Comparison --- p.69 / Chapter 5.3.1 --- CGE --- p.69 / Chapter 5.3.2 --- SEGA --- p.70 / Chapter 5.3.3 --- TRACER --- p.71 / Chapter 5.3.4 --- VPR --- p.72 / Chapter 5.4 --- Switch Box Design --- p.73 / Chapter 5.4.1 --- Disjoint type switch box (XC4000-type) --- p.73 / Chapter 5.4.2 --- Anti-symmetric switch box --- p.74 / Chapter 5.4.3 --- Universal Switch box --- p.74 / Chapter 5.4.4 --- Switch box Analysis --- p.75 / Chapter 5.5 --- Terminology --- p.77 / Chapter 5.6 --- "Hyper-universal (4, W)-design analysis" --- p.82 / Chapter 5.6.1 --- "H3 is an optimum (4, 3)-design" --- p.84 / Chapter 5.6.2 --- "H4 is an optimum (4,4)-design" --- p.88 / Chapter 5.6.3 --- "Hi is a hyper-universal (4, i)-design for i = 5,6,7" --- p.90 / Chapter 5.7 --- Experimental Results --- p.92 / Chapter 5.8 --- Conclusions --- p.95 / Chapter 6 --- Conclusions --- p.99 / Chapter 6.1 --- Thesis Summary --- p.99 / Chapter 6.2 --- Future work --- p.100 / Chapter 6.2.1 --- Alternative Wiring --- p.100 / Chapter 6.2.2 --- Partitioning Quality --- p.100 / Chapter 6.2.3 --- Routing Devices Studies --- p.100 / Bibliography --- p.101 / Chapter A --- 5xpl - Berkeley Logic Interchange Format (BLIF) --- p.115 / Chapter B --- Proof of some 2-local patterns --- p.122 / Chapter C --- Illustrations of FM algorithm --- p.124 / Chapter D --- HUSB Structures --- p.127 / Chapter E --- Primitive minimal 4-way global routing Structures --- p.132

Thesis (M.S.)--Brigham Young University. Dept. of Electrical and Computer Engineering, 2006. / Includes bibliographical references (p. 63-71).

FPGA clock frequencies are slow enough that only a fraction of the interconnect’s bandwidth is used. By exploiting this bandwidth, the transfer of large amounts of data can be greatly accelerated. Alternatively, it may also be possible to save area on fixed-bandwidth links by using on-chip serial signaling. For datapath-intensive designs which operate on words instead of bits, this can reduce wiring congestion as well. This thesis proposes relatively simple circuit-level modifications to FPGA interconnect to enable high-bandwidth communication. High-level area estimates indicate a potential interconnect area savings of 10 to 60% when serial links are used. Two interconnect pipelining techniques, wave pipelining and surfing, are adapted to FPGAs and compared against each other and against regular FPGA interconnect in terms of throughput, reliability, area, power, and latency. Source-synchronous signaling is used to achieve high data rates with simple receiver design. Statistical models for high-frequency power supply noise are developed and used to estimate the probability of error of wave pipelined and surfing links as a function of link length and operating speed. Surfing is generally found to be more reliable and less sensitive to noise than wave pipelining. Simulation results in a 65nm process demonstrate a throughput of 3Gbps per wire across a 50-stage, 25mm link.

Thesis (M.S.)--University of North Texas, August, 2009. / Title from title page display. Includes bibliographical references.