Title: Multilevel Optimization for Circuit Placement


			       Tony Chan 
		        Department of Mathematics
			         UCLA
                      Email: TonyC@college.ucla.edu
           (Joint work with Jason Cong, Joe Shinnerl, Kenton Sze)
	              (UCLA CS and Math Departments)


Abstract:
 I'll give a description of the multilevel optimization algorithms
that our group at UCLA has developed for large scale circuit
placement. I'll describe the approaches we have taken for each of the
key components of the multilevel framework: coarsening, relaxation,
interpolation and V-cycle iterations. Ideas and concepts from
continuous PDE-based multilevel algorithms can be applied to
this class of problems to some extent, but their effective adaptation
requires subtle considerations and presents serious challenges. Results
for standard benchmark circuits, as well as comparisons with other
multilevel circuit placement algorithms, will be presented.