EECS 298-11: CAD Seminar
Wednesday, April 16, 1997, 5pm
Cory Hall--Hogan Room

	Speeding Up Technology-Independent Timing Optimization 
			by Network Partitioning
			
			Rajeev Murgai
		    Fujitsu Labs of America

Technology-independent timing optimization is an important problem in
logic synthesis. Although many promising techniques have been proposed
in the past, unfortunately they are quite slow and thus impractical
for large networks. A long outstanding problem has been to quickly
generate timing-optimized networks, whose delays are comparable to
those of the networks generated by state-of-the-art timing
optimizers. In this talk, I will describe DEPART, a delay-based
partitioner-cum-optimizer, which purports to solve this problem. Given
a combinational logic network that is to be optimized for timing,
DEPART divides it into sub-networks using timing information and a
constraint on the maximum number of gates allowed in a single
sub-network. These sub-networks are then dispatched, one by one, to a
standard timing optimizer. The optimized sub-networks are re-glued,
generating an optimized network. The partitioning technique is
timing-driven and simple yet effective.

We evaluate DEPART against speed_up -- a state-of-the-art timing
optimization tool, and various partitioning techniques on a suite of
large industrial circuits and ISCAS benchmarks. On more than half the
benchmarks, DEPART yields run-time improvements of 20 to 40 times over
a normal invocation of speed_up. On average, the run-time goes down by
a factor of over 8 times and the solution quality is not compromised
either. Other partitioning methods such as min-cut based and region
growing perform poorly in terms of the final circuit delay.

This work was done with Rajat Aggarwal and Masahiro Fujita.