Field-Programmable Gate-Array-Based Graph Coloring Accelerator

摘要

A hardware methodology is described for implementing a graph coloring for the Latin squares problem that is compatible with more course grain approaches routinely implemented in software. The approach described maximizes the use of local communication and fine-grained parallelism while still ensuring a complete search of the solution domain. An implementation of a graph coloring architecture using field-programmable gate arrays and high-level programming tools is presented. An exploration of the tradeoff among nodes per processor, fill depth, and latency is presented. The use of this hardware-based graph coloring accelerator architecture to the more efficient implementation of routing for wave division multiplexing fiber optic communications systems and multihop radio communications is also discussed.