MINFLOTRANSIT: min-cost flow based transistor sizing tool

This paper presents MINFLOTRANSIT, a new transistor sizing tool for fast sizing of combinational circuits with minimal cost. MINFLOTRANSIT is an iterative relaxation based tool that has two alternating phases. For a circuit with |V| transistors and |E| wires, the first phase (D-phase) is based on minimum cost network flow, which in our application, has a worst-case complexity of O(|V||E|log(log(|V|))). The second phase (W-phase) has a worst case complexity of O(|V||E|). In practice, during our simulations both the D-phase and W-phase show a near linear run-time dependence on the size of the circuit, comparable to TILOS. Simulation results show excellent run-time behavior for MINFLOTRANSIT on all the ISCAS85 benchmark circuits. For reasonable delay targets MINFLOTRANSIT shows up to 16.5% area savings over a circuit sized using a TILOS-like algorithm.