A Fast Algorithm to Reduce 2-Dimensional Assignment Problems to 1-Dimensional Assignment Problems for FPGA-based Fault Simulation

摘要

In this paper a polynomial time heuristic algorithm developed for the assignment optimization problem is introduced, which leads to an improved usage of field programmable gate array (FPGA) resources for hardware-based fault injection using an FPGA-based logic emulator. Logic emulation represents a new method of design validation utilizing a reprogrammable prototype of a digital circuit. In the past years various approaches to hardware-based fault injection using a hardware logic emulator have been presented. Some approaches insert additional functions at the fault location, while others utilize the reconfigurability of FPGAs. A common feature of each of these methods is the execution of hardware-based fault simulation using the stuck-at fault model at gate level.