Abstract
Constraint satisfaction problems (CSPs) can be used to model problems in a wide variety of application areas. To solve a CSP means finding appropriate values for its set of variables such that none of the specified constraints on these variables is violated. GENET, developed by Wang and Tsang, is a generic neural network approach for solving CSPs and has been demonstrated to be faster than many other methods for various types of CSPs.In this paper, we describe a novel method of implementing GENET on FPGAs to solve a specific type of CSPs, namely, graph coloring problems. Our implementation uses a ring architecture and is therefore easily scalable. It employs an unbiased selection scheme and avoids oscillatory behaviors that can occur due to synchronous updating of neural networks.A small prototype of the system, consisting of two nodes, operates successfully at 8.3 MHz on a Gigaops G900 board using two Xilinx XC4013E(-3) FPGAs. Moreover, simulation results indicate that, for a standard benchmark, our method offers over two orders-of-magnitude speed-up over other GENET implementations.