MOCQA: A Multi-Core Optimizer for Constrained Quadratic Assignment

Despite advances in general processing hardware, optimization of NP-hard problems remains a time and compute-intensive task, with the end of Dennard Scaling leading to the increased development of domain-specific hardware in this area. Current research has focused on designing accelerators for solving problems in the NP-complete Quadratic Unconstrained Binary Optimization (QUBO) format due to its simplicity. We review the benefits and drawbacks of QUBO and its relevant hardware accelerators. We then contrast QUBO with the NP-complete Generalized Quadratic Assignment Problem (GQAP) format which, unlike QUBO, provides native support for integer variables and constraints. We propose a Boltzmann Machine Caching based Stochastic Local Search heuristic and use it to build MOCQA: a Multi-Core Optimizer for Constrained Quadratic Assignment problems. We present the system-level architecture of MOCQA, which uses Parallel Tempering in conjunction with multiple Replica Processing Cores to solve GQAP instances. We then detail mapping a MOCQA system to general-purpose hardware along with a circuit-level implementation of a sample MOCQA system on an Intel Stratix 10 FPGA. MOCQA FPGA comprises 32 domain-specific processing cores, supporting GQAPs with up to 255 integer variables, in combination with a Parallel Tempering controller, all operating at 240MHz with a peak FPGA power draw of 37W. We benchmark MOCQA FPGA’s performance across a wide range of GQAP benchmark instances and show that it is, on average, 4.4 times faster and 35 times more efficient than the next best solver.