Heuristic-hardware Co-design for Large-scale Optimization Problems

PASSCODE: 508477

Many real-world optimization problems possess combinatorial nature. Heuristic algorithms, trading off accuracy for time-to-solution, are crucial for their solvability. However, as the problem size increases, time becomes the critical factor and solving these problems motivates the development of more elaborate techniques.

 In my thesis, I adopt the approach of synergistic co-design of heuristics and computing platforms. I propose a novel class of custom computing machines aimed at solving large quadratic unconstrained binary optimization (QUBO) problems via continuous relaxations.

 As the first part of my talk, I present an analog QUBO machine that solves a relaxed maximum-cut problem using analog computing methods. The entire machine is designed at the transistor level to mimic physics-inspired dynamics of network of non-linearly coupled continuous spins.

 Next, I present a multi-core QUBO machine comprising a scalable ring of 1024 processors implemented on a multi-FPGA system. The machine provides solutions to weighted QUBO, by simultaneously solving the relaxed QUBO and the subsequent optimal rounding problems, in a massively parallel fashion. As a demonstration of the machine’s capabilities, I apply it to solve discrete inverse tomography.

 This work introduces a novel class of dynamical computing machines that accelerate QUBO in a self-contained manner, without pre-, intermediate- or post-processing.

Co-Chairs: Professor Pinaki Mazumder & Dr. Mikhail Erementchouk