A fast and efficient FPGA-based implementation for solving a system of linear interval equations

This paper addresses the problem of solving a system of linear interval equations (an NP-hard problem), wherein the co-efficients on the LHS and the RHS are all represented using intervals. This problem is transformed into a global optimization problem and a modified branch and bound algorithm suited for an FPGA-based implementation is proposed. This algorithm is modified to extract parallelism and further speed-up is achieved by pipelining the implementation. The implementation was designed using Xilinx 1SE 6.1 and VHDL was the design entry language. A speed-up of 14 for a Xilinx Virtex 2P30 FPGA over a 1.5 GHz Intel Centrino processor based implementation was obtained.