|
In this thesis,a performance-driven globla router called POPAR
(Path-Oriented Performance-Aimed global Router) is proposed.In
digital systems,the clock rate of a digital system is
determined by the sowest of all possible signal propagation
paths.Such a path is called the critical path.In order to
reduce the delay along every critical path, the algorithm is
divided into two phases.In the first phase, the main
consideration is the circuit performance.The algorithm tries to
minimize the delay upper-bound among likely critical paths.In
the second phase,the algorithm completes all the partial routed
or unrouted nets.The objectives of this phase are to reduce the
total wire length and to improve routability. In this system
POPAR ,it firstly finds an initial solution, and reroutes some
nets or subpaths to reduce the capacity violatios based on some
heuristic methods.Rerouting a net each time not only reduces
the number of rerouting, but also avoids cycles.If there exists
a solution,the proposed algorithm will find it in polynominally
bounded number of steps.If, for some iterations, a solution
does not exist,then an escape procedure is applied and the
process continues until a solution is obtained or no solution
is reported.Experimental results show that POPAR improves the
performance of global routing effectively.
|