MAQO: A Scalable Many-Core Annealer for Quadratic Optimization on a Stratix 10 FPGA

Quadratic Assignment Problems are a class of NP-hard combinatorial optimization problems with a wide range of real-world applications such as Vehicle Routing and FPGA Block Placement. Despite technological advances, solvers that target Quadratic Assignment Problems still require significant computing resources and time, especially as problem sizes grow; with the end of Dennard Scaling leading to the increased development of domain-specific hardware for such tasks. This paper presents MAQO: a hardware architecture for a scalable many-core annealer for quadratic optimization, implemented on an Intel Stratix 10 FPGA. MAQO is comprised of 32 domain-specific processing cores, supporting Quadratic Assignment Problems with up to 200 integer variables, in combination with a Parallel Tempering controller, all operating at 220MHz with a maximum FPGA power draw of 40W. We benchmark MAQO's performance, via solving some of the most difficult known Quadratic Assignment Problem instances, and show that it is, on average, 2.5 times faster than the next best competing solver with 22 times better performance-per-watt.