New M.E. Thesis Submitted from ECE Student


Partitioning is the critical area of VLSI CAD. In order to build complex digital logic circuits it is often essential to subdivide multi-million transistor circuit designs into manageable pieces. So, Partitioning, on the one hand, is a design task to break a large system into pieces to be implemented on separate interacting components and on the other hand it serves as an algorithmic method to solve difficult and complex combinatorial optimization problems as in logic or layout synthesis.
Partitioning is done keeping in mind certain objectives which may be implemented independently or collectively. In this dissertation, two objectives – First, minimizing the Cut-Set between the partitions and second, minimizing the delay between the partitions are taken. The Objectives may be optimized using an Optimization technique such as Ant Colony Optimization, Particle Swarm Optimization, Stimulated Annealing Technique etc.
Optimization technique used in this dissertation is Particle Swarm Optimization (PSO). The algorithm is developed to implement the PSO technique for circuit partitioning and finding the global best position, i.e. least cut-set. The second phase of the work is done on - finding the critical paths of the circuit and optimizing the delay objective. The algorithm is developed to find the critical paths of the circuit and then, selecting the K-critical paths which contribute to the delay significantly. After that, shifting of the nodes of the critical paths is done from one partition to the other just to neutralize the critical path affect. If all the nodes of the critical path lie in the same partition then it does not affect the delay and other parameters during the partitioning process. The compromise has to be done for cut-set and delay as optimizing delay may not optimize the cut-set or vice-versa.
The Standard ISPD98 benchmark formatted Net List files are used for testing and simulation. The simulation and algorithms are implemented in MATLAB Software. The results so obtained are compared with the results that are available on UCLA Bookshelf at the site of University of southern California, San Diego. We are able to get the better results except for certain circuits for cut-set. As the future scope of this work, these algorithms cam be implemented on multi-million transistor circuits and CPU execution time can also be taken into account and as an additional parameter to optimize.

Leisure Readings :