A dynamic programming approach to the power supply net sizing problem

The author presents a simple dynamic programming approach to find minimum area sizings of power supply nets in VLSI circuits in time O((ΔA)²n), where n is the number of modules and ΔA is the difference between an upper bound of the area and the lower bound resulting from minimum feature size and electromigration constraints. In opposition to known algorithms from literature, this algorithm determines an integer solution and has time and space bounds which can be predicted before running the algorithm. Some heuristics for computing upper bounds and reducing time and space requirements as well as first experimental experiences are included