  In VLSI physical design, many algorithms require the solution of difficult
combinatorial optimization problems such as max/min-cut, max-flow problems etc.
Due to the vast number of elements typically found in this problem domain,
these problems are computationally intractable leading to the use of
approximate solutions. In this work, we explore the Ising spin glass model as a
solution methodology for hard combinatorial optimization problems using the
general purpose GPU (GPGPU). The Ising model is a mathematical model of
ferromagnetism in statistical mechanics. Ising computing finds a minimum energy
state for the Ising model which essentially corresponds to the expected optimal
solution of the original problem. Many combinatorial optimization problems can
be mapped into the Ising model. In our work, we focus on the max-cut problem as
it is relevant to many VLSI physical design problems. Our method is inspired by
the observation that Ising annealing process is very amenable to fine-grain
massive parallel GPU computing. We will illustrate how the natural randomness
of GPU thread scheduling can be exploited during the annealing process to
create random update patterns and allow better GPU resource utilization.
Furthermore, the proposed GPU-based Ising computing can handle any general
Ising graph with arbitrary connections, which was shown to be difficult for
existing FPGA and other hardware based implementation methods. Numerical
results show that the proposed GPU Ising max-cut solver can deliver more than
2000X speedup over the CPU version of the algorithm on some large examples,
which shows huge performance improvement for addressing many hard optimization
algorithms for practical VLSI physical design.
