Design and Analysis of Physical Design Algorithms


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: [email protected]) 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. Here we will look at several algorithm design and analysis tools and concepts. The methods and concepts that we will point out in this paper are used less frequently in physical design tools. This paper is organized as follows. In Section 2, it is shown how problem transformation is used to devise a new algorithm. Section 3 explains how proof of NP-Completeness of hard problems is useful in generating efficient algorithms to solve those problems. In Section 4, we explain how to obtain the power of a greedy method through the proof of its correctness. In Section 5, we describe that more global view to a problem can help improve the greedy algorithms. Approximation algorithms and advantages of analyzing the performance of heuristic methods are explained in Section 6. In Section 7, probabilistic algorithms and their ability to provide solution quality bounds are presented. In Section 8, some conclusions are given. 2. ON PROBLEM TRANSFORMATION: UPPER-BOUND ANALYSIS Problem transformation is an effective methodology for solving a problem. Mathematicians have used transformation for many years and more recently by algorithm designers. Problem transformation can be used to devise a new algorithm (upper- bound) or to prove the complexity of a problem (lower-bound). In this section we will give an example ...

Loading Unlocking...


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

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.


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

Already a member?