Design and Analysis of Physical Design Algorithms




2 views

Unformatted text preview:

Design and Analysis of Physical Design Algorithms Majid Sarrafzadeh Elaheh Bozorgzadeh Ryan Kastner Ankur Srivastava Computer Science Department University of California Los Angeles Los Angeles California 90095 1596 Contact majid cs ucla edu ABSTRACT We will review a few key algorithmic and analysis concepts with application to physical design problems We argue that design and detailed analysis of algorithms is of fundamental importance in developing better physical design tools and to cope with the complexity of present day designs 1 INTRODUCTION Problems in physical design are getting more complex and are of fundamental importance in solving present day design problems Full understanding of the problems and algorithm analysis of them are essential to making progress Whereas problems are getting harder e g by need for concurrent optimization finer geometries and larger problems algorithms to cope with them have not been designed at the same rate A number of fundamental physical design algorithms have been developed in the past three decades Examples are maze running and KL FM partitioning 7 8 23 24 They are both in the heart of current CAD tools A number of existing techniques used heavily in current CAD tools have not been fully analyzed For example quadratic programming and hierarchical placement are used purely as a heuristic and their analysis is still open Yet there are problems that are far from being understood Researchers have started only very recently to study them Examples are congestion estimation and minimization during placement A heuristics is a good starting point for solving a problem however it normally fails to perform well in a changing or a more complex scenario e g hot spot removal by annealing To continue making effective CAD tools we need to study problems deeper analyze them thoroughly and base the proposed heuristics on the performed analysis This work was partially supported by NSF under Grant CCR0090203 Permission to make digital or hard






Loading Unlocking...
Login

Join to view Design and Analysis of Physical Design Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Design and Analysis of Physical Design Algorithms and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?