[ Chapter start ] [ Previous page ] [ Next page ]
| ||
In order to develop a CAD tool it is necessary to convert each of the physical design steps to a problem with well-defined goals and objectives. The goals for each physical design step are the things we must achieve. The objectives for each step are things we would like to meet on the way to achieving the goals. Some examples of goals and objectives for each of the ASIC physical design steps are as follows:
There is no magic recipe involved in the choice of the ASIC physical design steps. These steps have been chosen simply because, as tools and techniques have developed historically, these steps proved to be the easiest way to split up the larger problem of ASIC physical design. The boundaries between the steps are not cast in stone. For example, floorplanning and placement are often thought of as one step and in some tools placement and routing are performed together.
A CAD tool needs methods or algorithms to generate a solution to each problem using a reasonable amount of computer time. Often there is no best solution possible to a particular problem, and the tools must use heuristic algorithms, or rules of thumb, to try and find a good solution. The term algorithm is usually reserved for a method that always gives a solution.
We need to know how practical any algorithm is. We say the complexity of an algorithm is O ( f ( n )) (read as order f ( n )) if there are constants k and n 0 so that the running time of the algorithm T ( n ) is less than k f ( n ) for all n > n 0 [ Sedgewick, 1988]. Here n is a measure of the size of the problem (number of transistors, number of wires, and so on). In ASIC design n is usually very large. We have to be careful, though. The notation does not specify the units of time. An algorithm that is O ( n 2 ) nanoseconds might be better than an algorithm that is O ( n ) seconds, for quite large values of n . The notation O (