Title :
Pad minimization for planar routing of multiple power nets
Author :
Ho, Jan-Ming ; Sarrafzadeh, Majid ; Vijayan, G. ; Wong, C.K.
Author_Institution :
Inst. of Inf. Sci., Acad. Sinica, Taipei, Taiwan
fDate :
4/1/1990 12:00:00 AM
Abstract :
The problem of minimizing the number of power pads, in order to guarantee the existence of a planar routing of multiple power nets, is discussed. A general lower bound is derived, and a heuristic for the general problem is discussed. Several important special cases, including the case of three power nets, are examined, and optimal strategies for pad placement are presented. It is also shown that the general pad minimization problem is NP-complete
Keywords :
VLSI; circuit layout CAD; computational complexity; graph theory; minimisation; network topology; NP-complete; VLSI theory; general lower bound; general pad minimization problem; heuristic; multiple power nets; pad placement; planar routing; Atherosclerosis; Design automation; Information science; Pins; Power supplies; Routing; Very large scale integration; Voltage;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
