|
As the increasing requirement of high speed circuit, the
performance issue must be addressed at layout compaction.
In this thesis, a new layout compaction approach which aims at
this purpose is considered. This compaction approach consists
of two stages: In the first stage, the upper bound of delay on
a set of timing critical path is minimized; and in the second
stage, the area of the layout is minimized while all the
timing cirtical paths are compelled to the obtained delay
upper bound. This approach considers the performance with
higher priority than the layout size. Both stages in this
approach can be formulated as linear programming (LP)
problems. Although the well -known simplex algorithm can
be used to solve the LP problems, however, the execution
time will be intolerable for practical applications. In order
to handle these problems efficiently, we propose a graph-
based simplex algorithm. This algorithm fully utilizes the
sparse structure of the problem and shift most of the work in
the LP domain into the graph domain. It can be proved that
this algorithm has lower time complexity than the typical
simplex method, and experimental results also show that this
algorithm is quite promising.
|