Voltage Island based Floorplanning in VLSI for Area Minimization using Metaheuristic Optimization Algorithm
Floor planning is the primary step of the physical design in the Very Large Scale Integration (VLSI) design flow. It is used to estimate the chip area and wire length prior to the real placement of digital blocks and their interconnections. In the modern physical design of VLSI chips, it is essential to design the chip, which works with multi supply voltages (MSV) To achieve power optimization, MSV circuits are partitioned into voltage islands (VI) where each island occupies an adjoining physical space and operates at one supply voltage. Since, floorplanning is a NP hard problem, many optimization techniques were adopted in literature. In the proposed work, a new two step methodology is used for VI constrained fixedoutline nonslicing floorplanning based on meta heuristic optimization algorithm, with the aim of reducing the total chip area. Here, a music inspired Twin Memory Harmony Search (TMHS) is used as the meta heuristic optimization algorithm. The experimental results show that our proposed approach provides efficient floorplanning with reduced area and wirelength. Experiments on MCNC benchmark circuits validate the effectiveness of our work. keywords: Floorplanning; Voltage Island; Multi Supply Voltage; Harmony Search; Meta heuristic Optimization; Very Large Scale Integration Introduction Floorplanning is the first step of the physical design in the VLSI design flow. It is an essential design step to estimate the chip area by considering the optimal placement of digital blocks and their interconnections. Each block consists of several hundreds or thousands of cells that perform a specific operation. The blocks are of rectangular shape with different aspect ratios. The blocks can be classified into two types based on their shape flexibility. They are hard blocks and soft blocks. Hard block has fixed width and height whereas soft block's width and height can be varied as long as its aspect ratio is within the given range and its area is constant. The aspect ratio of a block is defined as the ratio between the height and the width of a block. To optimize the area of the chip, hard blocks are rotated then the width and height of soft blocks are modified such as without affecting the area of the block. The classical floorplanning methods normally handles only block packing to minimize the total chip area, but modern floorplanning methods could be devised as a fixed outline floorplanning. There are two types of floorplanning methods used in electronic design automation. They are slicing and nonslicing floorplan. In slicing floorplan, the whole block area is first partitioned into two slices of equal or unequal sizes using either a horizontal or vertical line then the individual blocks are again partitioned into by using either horizontal or vertical lines. This process continues until all the blocks are separated. This process of partitioning the block area is called slicing floorplan. The slicing floorplan is represented by a binary tree structure known as slicing tree. If a floorplan is obtained with no recursive through cuts, it is called nonslicing floorplan. Different techniques are used to represent the non slicing structure of a floorplan. They are sequence pair [1] bounded sliceline grid (BSG) [2] O tree [3] and B* tree [4] Classical floorplanning methods deal with the minimization of chip area by optimizing the module positions and their interconnections. In the modern physical design of VLSI era, it is essential to design the chip with small size which consumes less power. In order to reduce routing complexity of power nets, modules with identical voltage source have better to be placed together. This also can reduce the difficulty in insertion of level shifters. MSV circuits are partitioned into Voltage Islands (VI) where, each island occupies an adjoining physical space and operates at one supply voltage. Thus, a designer usually groups up the modules powered by the same voltage source as a VI and ensures that the created groups do not violate timing constraint or induce routing congestion. The VI driven floorplanning problem is more difficult than the classical floorplanning problem. The objective of any optimization algorithm is to minimize or maximize the objective function. Optimization algorithms are mostly used in all engineering problems. Since VLSI floorplanning is a NP hard problem which is to be optimized, in this work music inspired Twin Memory Harmony Search (TMHS) algorithm is used for VLSI floorplanning. The rest of this paper is organized as follows: the next section reviews the recent and related work in the field of VLSI floorplanning. Then the proposed framework is described, followed by the experimental setup and discussion of obtained results. Finally the conclusion is given with possible scope for further explorations. International Journal of Applied Engineering Research ISSN 0973 4562 Volume 11, Number 5 (2016) pp 3469 3477 (c) Research India Publications. http:/www.ripublication.com 3470 Related Works Many researchers have focused on optimization algorithms for floorplanning in both slicing and non slicing structures. O tree representation is proposed by Guo et al [3] based on a nonslicing floorplan. Ma et al [5] implemented the boundary constraint algorithm for general floorplan by extending the Corner Block List (CBL) algorithm, which is an efficient topology representation for non slicing floorplan. For non slicing VLSI floorplanning, a Genetic Algorithm (GA) has also been presented by Gwee and Lim [6] Xu et al [7] applied Tabu search algorithm to solve module placement problem. Initially, all the modules are merged into some clusters according to the ratio connectivity of circuit modules. The placement of the large modules is represented by sequence pairs. The searching of optimal solution of placement is performed by the Tabu search algorithm. Tang and Sebastian [8] scheduled a GA to tackle the VLSI floorplanning problem using O tree representation. Particle swarm optimization (PSO) [9] was introduced into the floorplanning problem to find the potential optimal placement solution. This structure is unable to solve problems that optimize the area and wirelength simultaneously. A memetic algorithm (MA) for a non slicing and hard module VLSI floorplanning problem was presented by Tang and Yao [10] Pradeep Fernando and Srinivas Katkoori [11] proposed a multi objective genetic algorithm for floorplanning that simultaneously minimizes area and total wirelength. The proposed genetic floorplanner is the first to use nondomination concepts to rank solutions. Chen et al [12] proposed a novel floorplanning algorithm based on Discrete PSO (DPSO) algorithm, in which integer coding based on module number was adopted. The principles of mutation and crossover operator in the GA are also incorporated into the proposed PSO algorithm to achieve better diversity and escape from local optima. Chen et al [13] used a PSO algorithm for floorplanning where area and wirelength are considered as the fitness function. A new heuristic method [14] was proposed that applied hybrid simulated annealing (HSA) to represent a non slicing floorplan with an objective function by restricting the area and wirelength. Sengupta et al [15] used a sequence pair approach to represent non slicing floorplans with a smaller search space. Shanavas et al [16] proposed a method that combines a hierarchical design technique like genetic algorithm and constructive technique like Simulated Annealing for local search to solve VLSI partitioning and floorplanning problem. Chen et al [17] proposed a co evolutionary multi objective particle swarm optimization (CMOPSO) algorithm to solve a VLSI floorplanning problem which is a multi objective combinatorial optimization and has been proved to be a NPhard problem. The algorithm imports the concept of coevolutionary algorithm and elitist strategy into basic PSO algorithm. It takes both the layout area and total interconnection wirelength into consideration simultaneously. An approach based on iterative prototypes optimization with evolved improvement (POEMS) algorithm was proposed by Singha et al [18] It uses a genetic algorithm (GA) for local search and adopted a non slicing structure B* tree for the placement of rectangle modules. Hoo et al [19] used a VOAS (Variable Order Ant System) for area optimization based on the ant algorithms. This method uses the models that are derived from the observation of real ants' behavior, and uses as a source of inspiration for the design of novel algorithms for the solution of optimization and distributed control problems. Sivaranjani and Senthil Kumar [20] proposed a smart decision making PSO GA based hybrid method for thermal aware non slicing VLSI floorplanning. B* tree representation is used in this method. VLSI floorplanning is a NP hard problem. The solution space will increase exponentially with the growth of circuits scale, thus it is difficult to find the optimal solution by exploring the global solution space. Proposed Methodology Harmony Search Algorithm The Harmony Search (HS) method is a meta heuristic optimization algorithm proposed by Geem et al [21] It mimics a musical improvisation process in which the musicians in an orchestra/band try to find a perfect state of harmony through musical improvisations. When musicians compose harmonies, they usually try various possible combinations of the music pitches stored in their memory. This algorithm was designed to mimic the way a musician uses short term memory and the past experiences to lead his/her to the note that results in the most pleasing harmony when played together with the other musicians. HS is easy to implement and can easily be applied to solve almost any problem that can be designed as the minimization or maximization of an objective function. This kind of efficient search for a perfect state of harmonies is related to the procedure of finding the optimal or ne