We present novel and efficient methods for built-in self-test (BIST) of field-programmable gate arrays (FPGAs) for detection and diagnosis of permanent faults in current, as well as emerging, technologies that are expected to have high fault densities. Our basic BIST methods can be used in both online and offline testing scenarios, although we focus on the former in this paper. We present 1- and 2-diagnosable BISTer designs that make up a ROving TEster (ROTE). Due to their provable diagnosabilities, these BISTers can avoid time-intensive adaptive diagnosis without significantly compromising diagnostic coverage-the percentage of faults correctly diagnosed. We also develop functional testing methods that test programmable logic blocks (PLBs) in only two circuit functions that will be mapped to them as the ROTE moves across a functioning FPGA. We extend our basic BISTer designs to those with test-pattern generators (TPGs) using multiple PLBs to more efficiently test the complex PLBs of current commercial FPGAs and to also prove the diagnosabilities of these designs. Simulation results show that our 1-diagnosable functional-test-based BISTer with a three-PLB TPG has very high diagnostic coverages-for example, for a random-fault distribution, our nonadaptive-diagnosis methods provide diagnostic coverages of 96% and 88% at fault densities of 10% and 25%, respectively, whereas the previous best nonadaptive-diagnosis method of the STAR-3 × 2 BISTer has diagnostic coverages of about 75% and 55% at these fault densities.

We present a very effective on-line interconnect built-in-self-test (BIST) method I-BIST for FPGAs that uses a combination of the following novel techniques: a track-adjacent and a switch-adjacent (also called "mirror adjacent") pairwise net comparison mechanism that achieves high detectability, a carefully designed set of only five net-configurations that cover all types and locations of wire-segment and switch faults, a 2-phase global-detailed testing approach, and a divide-and-conquer technique used in detailed testing to quickly narrow down the set of potential suspect interconnects that are then detail-diagnosed. These techniques result in I-BIST having provable detectability in the presence of an unbounded number of multiple faults, very high diagnosability of 99-100% even for high fault densities of up to 10% that are expected in emerging nano-scale technologies, and much lower test times or fault latencies than the previous best interconnect BIST techniques. In particular, for application to on-line testing, our method requires 2n roving-tester (ROTE) configurations to test an entire n times n FPGA, while the previous best online interconnect BIST technique requires n2configurations. Thus, I-BIST is an order of magnitude more time- as well as power-efficient, and scale well with rapidly increasing FPGA device sizes that are expected in emerging technologies

We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits. FlowPlace includes: a) a timing-driven (TD) analytical global placer TAN that uses accurate delay functions and minimizes a combination of linear and quadratic objective functions; b) a network flow based detailed placer TIF that has new and effective techniques for performing TD incremental placement and satisfying rowlength (white space) constraints. We have obtained results on three sets of benchmarks: i) TD versions of the ibm benchmark suite that we have constructed; ii) benchmarks used in TD-Dragon; iii) the Faraday benchmarks. Results show that starting with Dragon-placed circuits, we are able to obtain up to 34 % and an average of 18 % improvement in critical path delays, at an average of 17.5 % of the run-time of the Dragon placer. Starting with a state-of-the-art TD placer TD-Dragon, for the TD-Dragon benchmarks we obtain up to about 10 % and an average of 4.3 % delay improvement with 12 % of TD-Dragon’s run times; this is significant as we are extracting performance improvements from a performanceoptimized layout. Wire length deterioration on the average over all benchmark suites is less than 8%. 1.

We tackle the problem of fault-free assumptions in current PLB and interconnect built-in-self-test (BIST) techniques for FPGAs. These assumptions were made in order to develop strong BIST methods for one class of components (PLBs or interconnects) while assuming that the other class is fault-free. This results in a cyclical conundrum that renders current PLB and interconnect BIST techniques impractical, since current deepsubmicron FPGAs as well as those of emerging single-digit nanometer technologies are expected to have a profusion of hard (permanent) PLB as well as interconnect faults. We address this issue here and develop a novel method M-BIST that uses a combination of (i) iterative bootstrapping that without any knowledge of the state of any PLB or interconnect determines a minimum contingent of fault-free test circuit components with high probability, and (ii) mixed testing of PLBs and interconnects in an interleaved manner that identifies fault-free components that are used in subsequent testing phases until the entire FPGA is tested. This approach is overlaid on current state-of-the-art PLB and interconnect BIST techniques. Simulation results obtained for faults present in both PLBs and interconnects show significant improvements in both fault coverage and false positives yielded by M-BIST compared to the PLB-only and interconnect-only BIST techniques used within the M-BIST wrapper that make fault-free assumptions about the other component type

We develop a novel on-line built-in self-test (BIST) technique for testing FPGAs that has a very high diagnosability, even in presence of clustered faults, a fault pattern for which previous BIST methods proved ineffective. Unlike previous BIST methods which unrealistically assume that the test circuitry used for testing PLBs is fault-free, our method, via an iterative bootstrapping process, first finds this fault-free test circuitry and then starts testing the PLBs. Also, unlike previous methods, our fault detection process does not require any unrealistic assumptions of fault-free status of some components or the existence of only some fault patterns (and the exclusion of others) in the FPGA. Our adaptive fault diagnosis process is more time efficient than its previous counterparts as it does not require testing of all the PLBs of a faulty BIST area, and its design is simpler in the sense that it does not require multiple modifications of the testing area for its implementation. We also analyze the probability of correct diagnosis in the presence of multiple faults. Our BIST technique gives excellent fault coverage and fault latency results, and supports the theoretical analysis.

We present novel and efficient methods for on-line testing in FPGAs. The testing approach uses a ROving TEster (ROTE), which has provable diagnosabilities and is also faster than prior FPGA testing methods. We present 1- and 2-diagnosable built-in self-tester (BISTer) designs that make up the ROTE, and that avoid expensive adaptive diagnosis. To the best of our knowledge, this is the first time that a BISTer design with diagnosability greater than one has been developed for FPGAs. We also develop functional testing methods that test PLBs in only two circuit functions that will be mapped to them (as opposed to testing PLBs in all their operational modes) as the ROTE moves across a functioning FPGA. Simulation results show that our 1-diagnosable BISTer and our functional testing technique leads to significantly more accurate (98% fault coverage at a fault/defect density of 10%) and faster test-and-diagnosis of FPGAs than achieved by previous work. The fault coverage of ROTE is also expected to be high at fault/defect densities of up to 25% using our 1-diagnosable BISTer and up to 33% using our 2-diagnosable BISTer. Our methods should thus prove useful for testing current very deep submicron FPGAs as well as future nano-CMOS and molecular nanotechnology FPGAs in which defect densities are expected to be in the 10% range.