[ Chapter start ] [ Previous page ] [ Next page ]

---

15.2.1 Methods and Algorithms

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 ₀ so that the running time of the algorithm T ( n ) is less than k f ( n ) for all n > n ₀ [ 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 ² ) nanoseconds might be better than an algorithm that is O ( n ) seconds, for quite large values of n . The notation O ( n ) refers to an upper limit on the running time of the algorithm. A practical example may take less running time—it is just that we cannot prove it. We also have to be careful of the constants k and n ₀ . They can hide overhead present in the implementation and may be large enough to mask the dependence on n , up to large values of n . The function f (n) is usually one of the following kinds:

• f (n)  = constant. The algorithm is constant in time. In this case, steps of the algorithm are repeated once or just a few times. It would be nice if our algorithms had this property, but it does not usually happen in ASIC design.
• f (n)  = log  n . The algorithm is logarithmic in time. This usually happens when a big problem is (possibly recursively) transformed into a smaller one.
• f (n) = n . The algorithm is linear in time. This is a good situation for an ASIC algorithm that works with n objects.
• f (n)  =  n  log  n . This type of algorithm arises when a large problem is split into a number of smaller problems, each solved independently.
• f (n)  =  n ² . The algorithm is quadratic in time and usually only practical for small ASIC problems.

If the time it takes to solve a problem increases with the size of the problem at a rate that is polynomial but faster than quadratic (or worse in an exponential fashion), it is usually not appropriate for ASIC design. Even after subdividing the ASIC physical design problem into smaller steps, each of the steps still results in problems that are hard to solve automatically. In fact, each of the ASIC physical design steps, in general, belongs to a class of mathematical problems known as NP-complete problems. This means that it is unlikely we can find an algorithm to solve the problem exactly in polynomial time.

Suppose we find a practical method to solve our problem, even if we can find a solution we now have a dilemma. How shall we know if we have a good solution if, because the problem is NP-complete, we cannot find the optimum or best solution to which to compare it? We need to know how close we are to the optimum solution to a problem, even if that optimum solution cannot be found exactly. We need to make a quantitative measurement of the quality of the solution that we are able to find. Often we combine several parameters or metrics that measure our goals and objectives into a measurement function or objective function. If we are minimizing the measurement function, it is a cost function. If we are maximizing the measurement function, we call the function a gain function (sometimes just gain).

Now we are ready to solve each of the ASIC physical design steps with the following items in hand: a set of goals and objectives, a way to measure the goals and objectives, and an algorithm or method to find a solution that meets the goals and objectives. As designers attempt to achieve a desired ASIC performance they make a continuous trade-off between speed, area, power, and several other factors. Presently CAD tools are not smart enough to be able to do this alone. In fact, current CAD tools are only capable of finding a solution subject to a few, very simple, objectives.