Buffer placement in distributed RC-tree networks for minimal Elmore delay

Abstract

An algorithm is presented for choosing the buffer positions for a wiring tree such that the Elmore delay is minimal. For given required arrival times at the sinks of the wiring tree, the algorithm chooses buffers such that the required departure time at the source is as late as possible. The topology of the wiring tree, a Steiner tree, is assumed to be given, as well as the possible (legal) positions of the buffers. The algorithm uses a depth first search on the wiring tree to construct a set of time/capacitance pairs that correspond to different choices. The complexity of the algorithm is O(B2), where B is the number of possible buffer positions. An extension of the basic algorithm allows minimization of the number of buffers as a secondary objective.