quotEVOLUTIONARY ALGORITHMICAL APPROACH FOR VLSI PHYSICAL DESIGNquot

Abstract

newline quotThe task of VLSI physical design is to produce the layout of an integrated circuit. newlineThe layout problem in VLSI-design can be broken up into the subtasks newlinepartitioning, floor planning, placement and routing. Physical design is the process newlineof determining the physical location of active devices and interconnecting them newlineinside the boundary of the VLSI chip the earliest and the most critical stage in newlineVLSI layout design is the placement. The background is the rectangle packing newlineproblem: given a set of rectangular modules of arbitrary sizes, place them without newlineoverlap on a plane within a rectangle of minimum area. The VLSI placement newlineproblem is to place the object in the fixed area of die with out overlap and with newlinesome cost constrain. Such as the wire length and area of the die. The wire length newlineand the area optimization is the major task in the physical design. We first newlineintroduced about the major technique involved in the algorithm.Next,Routing can newlinebe classified into two types. One is Global routing and another one is detailed newlinerouting. In detailed routing, the Connections between blocks or cells, newlinerespectively,have to be generated under consideration of certain constraints, e.g., newlinedifferent Nets are not allowed to intersect because such intersections produce short newlinecircuits. As routing is NP-complete, in general it cannot be solved exactly within newlinereasonable time bounds for large Problem instances. Some problems are arises newlineduring the routing process .The routing constraints are Minimize total wire length, newlineMinimize knees in path, Meet timing budget. To overcome these problems newlineMemetic algorithm has been used. Combining global and local search is a strategy newlineused by many successful hybrid optimization approaches. Memetic Algorithms newline(MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to newlinefurther improve the fitness of individuals in the population. Memetic Algorithms newlinehave been shown to be very effective in solving many hard combinatorial newlineoptimization problems. This algorithm combines Genetic A