Routing wires with non-uniform width and spacing in data paths

Datapath layout designs exhibit special layout properties in that most wires connect one stage to another and are straight wires. Use of track based routing algorithms suffices for the routing needs of the bit-lines. The left edge algorithm (LEA) may be used for this purpose. With the increase in performance requirements for deep sub-micron datapath designs, the use of nonuniform wire widths and spacing is becoming necessary and using LEA is not feasible. This paper defines the datapath bit-line assignment problem. We then present a heuristic algorithm that achieves optimal results in most test cases when the wire widths are nonuniform. The time complexity of our solution is O(NlogN), where N is the number of bit-wire segments to be assigned.