engleski

Basic Algorithms for Circuit Partitioning

The partitioning methodology has proven to be very useful in solving VLSI design automation problem occuring in all stages of the IC design process. Today's circuits are so complex and large and must be partition into several subcircuits. In our work we will be focused on a problem of circuit partitioning. The basic algorithms, Kernighan-Lin (K-L) and Simulated Annealing (SA), are discussed and compared on a few simple examples. Both algorithms give good, sometimes even the best solution. The K-L algorithm, depending on an initial solutionm, can be trapped in a local minimum ; we show this on a simple example. The SA algorithm can released itself from a local minimum, and find a global minimum. This is also illustrated in our work on a few examples.

circuit partitioning; Kernighan-Lin; Simulated Annealing

nije evidentirano