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.

A Digital Annealer (DA) is a dedicated architecture for high-speed solving of combinatorial optimization problems mapped to an Ising model. With fully coupled bit connectivity and high coupling resolution as a major feature, it can be used to express a wide variety of combinatorial optimization problems. The DA uses Markov Chain Monte Carlo as a basic search mechanism, accelerated by the hardware implementation of multiple speed-enhancement techniques such as parallel search, escape from a local solution, and replica exchange. It is currently being offered as a cloud service using a second-generation chip operating on a scale of 8,192 bits. This paper presents an overview of the DA, its performance against benchmarks, and application examples.

Boltzmann Machines are recurrent neural networks that have been used extensively in combinatorial optimization due to their simplicity and ease of parallelization. This paper introduces the Permutational Boltzmann Machine, a neural network capable of solving permutation optimization problems. We implement this network in combination with a Parallel Tempering algorithm with varying degrees of parallelism ranging from a single-thread variant to a multi-threaded system using a 64-core CPU with SIMD instructions. We benchmark the performance of this new system on Quadratic Assignment Problems, using some of the most difficult known instances, and show that our parallel system performs in excess of 100 $$\times $$ faster than any known dedicated solver, including those implemented on CPU clusters, GPUs, and FPGAs.

A replica exchange Markov Chain Monte Carlo (MCMC) engine is developed with automatic temperature adjustment for solving combinatorial optimization problems by minimizing the energy of the Ising model. The automatic temperature adjustment scheme ensures that the MCMC process is optimized at every stage of the execution. This approach is performed by dynamically adjusting temperatures of all replicas, based on the properties of any given problem, in addition to the capability of automatically inserting new replicas or removing any existing replicas to achieve the best possible resource efficiency and execution time. The proposed algorithm is integrated with parallel evaluation of energy increment and update scheme. The engine is implemented on the FPGA platform with a capacity of running up to 42 replicas in pipeline, each running 1024 fully-connected Ising spins in parallel. The performance of the hardware is examined with three different classes of problems, Vertex Cover, Maximum-Cut, and Travelling Salesman using the engine in three modes, simulated annealing, with replica exchange while the adjustments are turned on or off. Up to 16x speedup is observed by turning on the replica exchange capability in addition to the advantage of eliminating the challenging process of finding an optimal annealing schedule for simulated annealing process.

We propose a technique to reduce the effective parasitic capacitance of interconnect routing conductors in a bid to simultaneously reduce power consumption and improve delay. The parasitic capacitance reduction is achieved by ensuring routing conductors adjacent to those used by timing critical or high activity nets are left floating - disconnected from either VDD or GND. In doing so, the effective coupling capacitance between the conductors is reduced, because the original coupling capacitance between the conductors is placed in series with other capacitances in the circuit (series combinations of capacitors correspond to lower effective capacitance). To ensure unused conductors can be allowed to float requires the use of tri-state routing buffers, and to that end, we also propose low-cost tri-state buffer circuitry. We also introduce CAD techniques to maximize the likelihood that unused routing conductors are made to be adjacent to those used by nets with high activity or low slack, improving both power and speed. Results show that interconnect dynamic power reductions of up to ~15.5% are expected to be achieved with a critical path degradation of ~1%, and a total area overhead of ~2.1%.

We propose charge recycling (CR) to reduce power consumption in FPGAs. We take advantage of the property that many routing conductors are left unused in any FPGA implementation of an application. Charge recycling via the unused conductors reduces the amount of charge drawn from the supply, lowering energy consumption. We present a routing switch that operates in two modes: normal and CR, and describe the CAD tool changes needed to support CR at the routing and post-routing stages of the flow. Results show that dynamic power in the FPGA interconnect can be reduced by up to ~15-18.4% by the proposed techniques, depending on the performance constraints.