Maidee, Pongstorn2010-02-262010-02-262009-12https://hdl.handle.net/11299/58583University of Minnesota Ph.D. dissertation. December 2009. Major: Electrical Engineering. Advisor: Dr. Kia Bazargan. 1 computer file (PDF); xvi, 142 pages.According to the international technology roadmap for semiconductors (ITRS) predictions, controlling manufacturing yield is going to be a challenging task in future technologies. It was shown that the effective yield of the future field programmable gate arrays (FPGAs) will be too low to make a profit. Several FPGA yield improvement techniques have been proposed such as clustering, spare column and node covering. However, the challenges of future fabrication technologies are so great that these techniques cannot fully address high yield demands of the future. Thus, novel techniques should be explored. We propose three approaches for FPGA yield improvement in this thesis: one adds redundant components to the FPGA architecture to tolerate permanent faults. Another technique speeds up a synthesis technique used in a rewiring engine to allow for replacement or enforcement of faulty wires in a circuit. The third technique uses a search space pruning technique to speedup the optimization of FPGA architecture development. The proposed yield improvement techniques can be applied in conjunction with other existing techniques, resulting in an effective framework for FPGA yield improvement. Chapter 2 addresses fault tolerant FPGA architectures that introduce redundancies in the architecture to replace faulty components. A methodology is proposed for estimating the effectiveness. Effectiveness of existing defect-tolerant schemes such as clustering, spare column and node covering for contemporary FPGA architectures. Furthermore, a number of new schemes to further improve yield are proposed in Chapter 2. Several techniques for tolerating defects in switch boxes were also introduced. The results show that the spare column scheme is very effective in maintaining a satisfactory yield. However, our studies show that to maintain reasonable yields, the number of spare columns must increase in the future. We also show that having redundancy for routing channels increases the absolute yield, but the benefit is outweighed by the area overhead for some types of routing channels. As a result, we show that redundancy must be judicially applied to the routing architecture to result in high yield numbers. Chapter 3 addresses yield improvement at the synthesis level. Circuit rewiring is proposed in this thesis to enhance effectiveness of existing approaches, namely customization and design-specific approaches. The success of rewiring depends on both the quality and speed of the rewiring engine. Among several rewiring techniques that have been purposed, a Set-of-Pairs-of-Functions-to-be-Distinguished (SPFD)-based rewiring was shown to be more effective than the others both in theory and practice. However, due to its longer runtime, it is not a viable rewiring technique. A novel algorithm is proposed to avoid expressing SPFDs explicitly. Instead, a few satisfiability problem (SAT) instances are solved, allowing rewiring of one instance in the order of milliseconds. The experimental results show that our proposed technique's runtime is only a fraction of that of a conventional one and it scales well with the number of candidate wires considered. The existing SPFD-based rewiring approaches also limit where a new wire can be added. We present a theory that allows us to add a new wire virtually anywhere in the circuit structure. An algorithm based on this theory is also presented. Experiments show that the number of wires which can be rewired increases significantly and the number of alternate wires for a given wire also increases. Chapter 4 deals with designing a family of FPGA chips. The goal of this chapter is to minimize area across a large number of designs. Minimizing area in turn helps improve yield. We formulate the family selection process as an FPGA family composition problem and propose an efficient algorithm for solving it. The formulation can capture an increasingly complex specialized functional block selection problem for FPGA families. The technique is applied to an architecture similar to Xilinx Virtex FPGAs. The results show that a smart composition technique can significantly reduce the expected silicon area. The benefit of providing specialized blocks can also be investigated using the technique and thus it can be used as an important tool for determining the benefits of specialized blocks for future FPGAs.en-USCircuit rewiringFPGAYield improvementElectrical EngineeringThesis or Dissertation