VLSI Circuit Partitioning Using Ants Colony Optimization

Abstract

The VLSI design automation is one of the most computational expensive and complicated processes with significant impact into computer chips manufacturing, especially at the physical layout design cycle. The recent VLSI evolution in multiple chip modules design has introduced new challenges at the physical layout steps (partitioning, floorplanning, placement, routing, compaction, etc). VLSI circuit partitioning problem is an NP hard problem. The potential of Ants colony optimization has been used to solve many computationally hard problems (NP hard problems). Existing conventional methods are unable to perform the required breakthrough in terms of complexity, time and cost. This report deals with the problem of partitioning of a VLSI circuit. An evolutionary approach based on Ants colony Optimization (ACO) is presented, which exploits the behavior of artificial ants modeled from real ants to solve the problem. Imitating the behavior of a colony of ants, clusters are formed. The idea of the algorithm is for each species of animats to form a colony consisting of a set of vertices that are highly connected to each other but highly disconnected from the other colony. Exploiting the massive parallelism and behavior of animates, colonies are formed with a lower cut size and in polynomial time. Results are shown to represents the effectiveness of the algorithm.