aussois_header.png

Algorithmic Advances for Global Routing in VLSI Design
Daniel Blankenburg  1@  
1 : Universität Bonn = University of Bonn

In the first part of the talk, we revisit the (block-angular) min-max resource sharing problem, a well-known generalization of fractional packing and the maximum concurrent flow problem. It consists of finding a resource allocation for every customer such that the maximum resource usage is minimized. Resource sharing has several applications in VLSI design; among others, it is used to model the global routing problem.
We improve upon the currently fastest known FPTAS in various ways—surpassing the previously best-known running times for both the primal and dual problem—and show that the second-highest entry of the computed solution is approximately minimal.

In the second part of the talk, we introduce a novel usage model for tile-internal wire capacity in global routing, capturing local congestion more accurately than existing methods. We present new algorithms tailored to this usage model and discuss experimental results on real-world microprocessors, demonstrating its superiority over a state-of-the-art traditional global router.


Personnes connectées : 2 Vie privée | Accessibilité
Chargement...