Aug 20 (Wed) @ 10:00am: "Accelerating Combinatorial Optimization using the Potts Model," William Whitehead, ECE PhD Defense

Research Area: Computer Engineering
Research Keywords: Probabilistic Computing, Combinatorial Optimization, P-bits
Location: Harold Frank Hall (HFH), Room 4110B | https://ucsb.zoom.us/j/83513900660

Abstract

New approaches for accelerating combinatorial optimization are presented, extending Ising-based hardware methods to the more general Potts model. The Potts model, which has “spins” that can take on multiple discrete states, provides a more natural representation of some optimization problems compared to the binary Ising model but introduces additional challenges in hardware design.

Techniques for mapping optimization problems into Potts Hamiltonians will be presented, highlighting both the representational benefits and the limitations of this approach. For example, while the Potts model can naturally encode problems such as graph coloring, scaling to real-world tasks like FPGA placement reveals inherent challenges in expressing complex constraints and large solution spaces. 

To create insights into hardware solver architectures, algorithmic experiments using a proposed work-per-flip (WPF) metric are conducted to predict the performance of hardware design features. Using the performance predictions as a guide, a resource-efficient digital annealing machine was designed.

Bio

William Whitehead is a PhD candidate advised by Professor Luke Theogarajan. He received a B.S. from UCLA in 2020, where he worked on neuromorphic computing and deep learning for image segmentation. Here at UCSB he has experimented across applications, algorithms, and hardware to understand if the Potts model is a viable framework for solving combinatorial optimization problems.

Hosted By: ECE Professor Luke Theogarajan

Submitted By: William Whitehead <williamwhitehead@ucsb.edu>