Efficient Algorithms for Fractional Load Balancing and Applications to VLSI Global Routing

Abstract

This thesis studies global routing in chip design, and its generalization, the Load Balancing Problem: finding a minimum-norm element of a structured set built from many "customer" subproblems, each accessible only through a linear minimization oracle. <br/> For the fractional relaxation, we give a new randomized algorithm that samples customers according to a dynamically evolving cost budget and combines non-uniform sampling with a martingale argument to guarantee fast convergence. This requires constructing stable norm approximations via entropic regularization, which are optimal for ordered norms and rely on certain structural properties of a the generalized KL projection to suitable dual spaces. Together these give the first efficient algorithm with a number of oracle calls that is near linear in the number of customers and resources for a broad class of norms beyond the ℓ_∞ norm. <br/> For the integral problem, we show that a simple greedy algorithm, routing each net once in random order, achieves approximation guarantees that asymptotically math those of randomized rounding. <br/> These algorithms are implemented in BonnRouteGlobal, and shown to outperform ts default routing method. The thesis also presents an improved congestion model and a random sub-grid technique that speeds up path search by more than 10x on large instances with almost no notable loss in quality.