CDROM Home PageICCAD98Front MatterTable of ContentsSession IndexAuthor IndexABSTRACT - This paper presents an optimal algorithmfor solving the problem of simultaneous fanout optimiza-tion and routing tree construction for an ordered set ofcritical sinks. The algorithm, which is based on dynamicprogramming, generates a rectilinear Steiner tree routingsolution containing appropriately sized and placed buff-ers. The resulting solution, which inherits the topology ofLT-Trees and the detailed structure of P-Trees, maxi-mizes the signal required time at the driver of the givenset of sinks. Experimental results on benchmark circuitsdemonstrate the effectiveness of this simultaneousapproach compared to the sequential methods.1. INTRODUCTIONThe current deep-submicron (DSM) process technologieshave increased the contribution of the interconnect delay tothe total path delay in digital circuits. At the same time, theexisting design flows and tools have had limited, and onlymarginal, success in incorporating interconnect planning andoptimization early in the design process. This situation hasforced IC designers to re-evaluate the existing computer-aided design (CAD) methodologies and techniques. To address the DSM design challenges, one can eitherincrease the lookahead capability of high-level tools ordevelop new algorithms for solving larger portions of theoverall design problem simultaneously. This latterunification-based approach is, in our view, more promising.Indeed, the nature of IC design problems and the currentstate of CAD solutions have reached a point where it is bothnecessary and possible to combine some steps of thesynthesis and physical design processes. The unification-based algorithms are capable of capturing existinginteractions among the ‘merged’ design steps and producinghigher-quality implementations by systematically searchinga much larger solution space (see [SLP98] and [LSP97]).The algorithm proposed in this paper integrates two majordesign steps: fanout optimization and routing treegeneration. Each of these two optimization steps has beenvery effective in reducing the circuit delay, in one case byboosting the transmitted signals via insertion of sized buffersand in the other case by generating suitable wire structures.The goal of this work is to optimally integrate these twosteps and thereby provide a uniform framework foroptimizing the nets of a placed circuit to achieve fasterimplementations.The proposed dynamic programming based algorithmgenerates and propagates a set of buffered routing treestructures in the form of two dimensional (required timeversus input load) solution curves. The resulting wiringstructure is guaranteed to inherit the topology of LT-Trees[To90] and the detailed physical implementation of P-Trees[LCLH96]. This algorithm takes a given order for the sinksand, starting from the higher indexed sinks, combines theminto groups which are to be driven by buffers. For eachgroup, proper routing structures and buffer locations areexamined to generate a set of possible solutions for thatsubset of ordered sinks. Only the solutions which are notdominated by other solutions are kept. These two steps arerepeated in a dynamic programming fashion until the wholeset of sinks are combined together. Experimental resultsreported in this paper demonstrate the effectiveness of thismethod versus conventional flows that sequentially performrouting tree generation and fanout optimization.The remainder of the paper is organized as follows. Insection 2, background and motivation are given. Section 3introduces the proposed algorithm. In sections 4 and 5, ourexperimental results and concluding remarks are presented.2. BACKGROUND AND MOTIVATION2.1 Fanout OptimizationFanout optimization, an operation performed in the logicdomain, addresses the problem of distributing a signal to aset of sinks with known loads and required times so as tomaximize the required time at the signal driver. Interconnectdelay is not incorporated in this operation because thelocations of the buffers are not known at this stage. Thegeneral fanout optimization problem is NP-hard [To90],however its restriction to some special families of topologiesis known to have polynomial complexity.Among the many existing works on fanout optimizationproblem, we are interested in the algorithm proposed by[To90]. That work introduces a special class of treetopologies, called LT-Trees, for which the fanout problem issolved with polynomial complexity. The LT-Tree of type-I(in this paper referred to as LT-Tree) is a tree that permits atmost one internal node among the immediate children ofevery internal node in the tree. Touati in [To90] proposed adynamic programming based algorithm for the fanoutoptimization problem where the buffer structure is restrictedto the LT-Tree topology and sinks with larger required times*This work was funded in part by SRC under contract no. 98-DJ-606 and bya NSF PECASE award (contract no. MIP-9628999).A Simultaneous Routing Tree Construction and Fanout Optimization Algorithm*Amir H. Salek, Jinan Lou, Massoud PedramDepartment of Electrical Engineering - SystemsUniversity of Southern CaliforniaLos Angeles, CA 90089{amir, jlou, massoud}@zugros.usc.eduare placed further from the root of the tree. His algorithmfirst sorts the sinks in non-decreasing required time orderand then starting from the least critical sink, it enumeratesall rightmost groupings of the sinks to be driven by a buffer.Finally for each grouping, it enumerates all possible ways ofadding either zero or one buffer to drive the rightmostsubset of the sinks. Touati gives sufficient conditions for hisLT-Tree construction algorithm, LTTREE, to be optimal. Lemma 1: LTTREE works optimally with respect to thesignal required time at the root (driver) if all the sinks haveequal load capacitances and are sorted in non-decreasingrequired times [To90].Lemma 2: LTTREE has O(n2) polynomial complexitywhere n is the number of sink nodes [To90].2.2 Routing Tree GenerationPerformance-driven interconnect design, an operationperformed in the physical domain, addresses the problem ofconnecting a source driver to a set of sinks with knownloads, required times and positions so as to maximize therequired time at the driver. The inherent complexity of thisproblem has forced researchers to either solve itheuristically or to impose constraints on the structure of theresulting interconnect. For an overview of the existingperformance-driven