15-03-2012, 11:16 AM
A NOVEL APPROACH TO OPTIMIZATION ALGORITHM FOR VLSI
INTRODUCTION
Evolution of IC technology : SSI(<10), MSI(10-100), LSI(1000).
Very-large-scale integration (VLSI) is the process of creating integrated circuits by combining thousands of transistors into a single chip.
VLSI process steps consist of : generating an idea=> architectural design=> logical design=> physical design=> fabrication=> chip.
VLSI physical design is the process of determining the physical location of active devices and interconnecting them inside the boundary of a VLSI chip
VLSI PHYSICAL DESIGN
The portion of the physical design flow that assigns exact locations for various circuit components within the chip’s core area.
Typical placement objectives include
Total wire length, Timing, Congestion, Power, Area.
PLACEMENT . . .
Two types of placement
i. STANDARD CELL PLACEMENT
Fixed height but different widths
Laid out in rows
Power and ground interconnects run horizontally through the top and bottom of the cells
ii. MACRO CELL PLACEMENT
Block size is variable, both height and width
It can be laid any where in the die
Power and interconnects run horizontally as well as vertically in the top and bottom of the cell
PLACEMENT . . .
Two types of placement algorithm
i. Iterative improvement ii. Constructive placement
Iterative improvement is algorithm based
Constructive placement is based on connectivity rules.
TYPES OF WIRE LENGTH ESTIMATION METHOD
Semi Perimeter Method
Half Perimeter Method
Genetic Algorithm (GA)
Is a search heuristic that mimics the process of natural evolution and is used to generate useful solutions to optimization and search problems.
Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as
Selection
Crossover
Mutation
Inversion
Termed to be the genetic operators
Selection
During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected.
Most functions are stochastic and designed so that a small proportion of less fit solutions are selected. This helps keep the diversity of the population large, preventing premature convergence on poor solutions.
Random selection
roulette wheel selection
tournament selection.
Our steps of Programming
Reading the placement file
Form a row format
Randomness on row format
Identifying the (x,y) co-ordinates.
Selection process
Crossover
Mutation
Result
Performance Comparison
Genetic Algorithm
1.79
3.99
5.05
Fast Place
1.86
4.0
5.11
Project Find outs
Genetic Algorithm implemented for standard cell placement using C-Language is found out to be a better performance tool .
Optimization could still be improved if randomization is avoided for genetic operators.
Certain limitations of C-Language has been found out.
Programs using C usually crash down for wider search space.
Softwares those support multiple compilers should be used.
Larger array declarations should need better performance systems.
Complexity to be reduced in order to run wider search space circuits.
Recommendation: C language should not be used for placement objectives unless provided with better performance systems.
Conclusion
Genetic algorithms are different from other heuristic methods in several ways. The most important difference is that a GA works on a population of possible solutions, while other heuristic methods use a single solution in their iterations Genetic algorithm introduces parallelism, so it is an efficient technique for a search and optimization of problems with a large and varied search space. So GA is found to be an efficient optimization technique for the cell placement problem.
REFERENCE
M. A. Breuer “Min-cut placement” J. Design Automat. Fault Tolerant Comput., vol. l , pp. 343-382, Oct. 1977.
H. Chang and P. Mazumder “Bit-map crossover based genetic algorithm for macro-cell placement” Tech. Rep., CRL-TR-10-89, Dep. Elect. Eng. Comput. Sci., Univ. of Michigan, 1989.
C. Cheng and E. Kuh “Module placement based on resistive network optimization,” IEEE Trans. Computer-Aided Design, vol. CAD-3, pp. 218-225, July 1984.
J. P. Cohoon, W. D. Paris “Genie technical report,’’ Dep. Comput. Sci., Univ. of Virginia, 1986.
F. Darema, S . Kirkpatrick, and V. A. Norton “Parallel techniques for chip placement by stimulated annealing on shared memory systems,” in Proc. IEEE Int. Conf. on Computer Design, pp. 87-90, 1987.
REFERENCE Cont . . .
J . J . Grefenstette, R. Gopal, B. Rosmaita, and D. Van Gucht “Genetic algorithms for the traveling salesman problem.” in Proc. Inr. Con$ on Genetic Algorithms and Their Applications, pp. 160-168.1985.
J. J. Grefenstette “Optimization of control parameters for genetic algorithms,” IEEE Trans. Systems, Man, Cybernet., vol. SMC-16,Jan./Feb. 1986.
J. H. Holland Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan, 1972.
M. Jones and P. Bannerjee “Performance of a parallel algorithm for standard cell placement on the intel hypercube,” in Proc. Design Automation Con$, 1987.
S . Kirkpatrick, C. D. Gelatt and M. P. Vecchi “Optimization by simulated annealing,’’ Sci., vol. 220, no. 4598, pp. 671-680, May 13,1983.
R. M. Kling “Placement by simulated evolution,” M.S. thesis, Coordinated Science Lab, College of Engr., Univ. of Illinois at Urbana-Champaign, June 1987.
REFERENCE cont . . .
S . A. Kravitz and R. A. Rutenbar “Placement by simulated annealing on a multiprocessor,” IEEE Trans. Computer-Aided Design, vol.CAD-6, pp. 534-549, June 1987.
S . Nahar, S. Sahni and E. Shragowitz Experiments with simulated annealing,” in Proc. 22nd Design Automation Conf., pp. 748-752,1985.
I . M. Oliver, D. J. Smith, and J. R. C. Holland “A study of permutation crossover operators on the traveling salesman problem.” In Proc. Int. Con$ on Genetic Algorithms and Their Applications, pp.224-230, 1985.
C. Sechen and A. Sangiovanni-Vincentelli “The Timberwolf placement and routing package,” IEEE J . Solid-State Circuirs, vol. SC-20, pp. 510-522, Apr. 1985.
Stadnyk “Schema recombination in pattern recognition problems,” in Proc. Int. Conf. on Genetic Algorithms and Their Applications,pp. 27-35, 1987.
INTRODUCTION
Evolution of IC technology : SSI(<10), MSI(10-100), LSI(1000).
Very-large-scale integration (VLSI) is the process of creating integrated circuits by combining thousands of transistors into a single chip.
VLSI process steps consist of : generating an idea=> architectural design=> logical design=> physical design=> fabrication=> chip.
VLSI physical design is the process of determining the physical location of active devices and interconnecting them inside the boundary of a VLSI chip
VLSI PHYSICAL DESIGN
The portion of the physical design flow that assigns exact locations for various circuit components within the chip’s core area.
Typical placement objectives include
Total wire length, Timing, Congestion, Power, Area.
PLACEMENT . . .
Two types of placement
i. STANDARD CELL PLACEMENT
Fixed height but different widths
Laid out in rows
Power and ground interconnects run horizontally through the top and bottom of the cells
ii. MACRO CELL PLACEMENT
Block size is variable, both height and width
It can be laid any where in the die
Power and interconnects run horizontally as well as vertically in the top and bottom of the cell
PLACEMENT . . .
Two types of placement algorithm
i. Iterative improvement ii. Constructive placement
Iterative improvement is algorithm based
Constructive placement is based on connectivity rules.
TYPES OF WIRE LENGTH ESTIMATION METHOD
Semi Perimeter Method
Half Perimeter Method
Genetic Algorithm (GA)
Is a search heuristic that mimics the process of natural evolution and is used to generate useful solutions to optimization and search problems.
Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as
Selection
Crossover
Mutation
Inversion
Termed to be the genetic operators
Selection
During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected.
Most functions are stochastic and designed so that a small proportion of less fit solutions are selected. This helps keep the diversity of the population large, preventing premature convergence on poor solutions.
Random selection
roulette wheel selection
tournament selection.
Our steps of Programming
Reading the placement file
Form a row format
Randomness on row format
Identifying the (x,y) co-ordinates.
Selection process
Crossover
Mutation
Result
Performance Comparison
Genetic Algorithm
1.79
3.99
5.05
Fast Place
1.86
4.0
5.11
Project Find outs
Genetic Algorithm implemented for standard cell placement using C-Language is found out to be a better performance tool .
Optimization could still be improved if randomization is avoided for genetic operators.
Certain limitations of C-Language has been found out.
Programs using C usually crash down for wider search space.
Softwares those support multiple compilers should be used.
Larger array declarations should need better performance systems.
Complexity to be reduced in order to run wider search space circuits.
Recommendation: C language should not be used for placement objectives unless provided with better performance systems.
Conclusion
Genetic algorithms are different from other heuristic methods in several ways. The most important difference is that a GA works on a population of possible solutions, while other heuristic methods use a single solution in their iterations Genetic algorithm introduces parallelism, so it is an efficient technique for a search and optimization of problems with a large and varied search space. So GA is found to be an efficient optimization technique for the cell placement problem.
REFERENCE
M. A. Breuer “Min-cut placement” J. Design Automat. Fault Tolerant Comput., vol. l , pp. 343-382, Oct. 1977.
H. Chang and P. Mazumder “Bit-map crossover based genetic algorithm for macro-cell placement” Tech. Rep., CRL-TR-10-89, Dep. Elect. Eng. Comput. Sci., Univ. of Michigan, 1989.
C. Cheng and E. Kuh “Module placement based on resistive network optimization,” IEEE Trans. Computer-Aided Design, vol. CAD-3, pp. 218-225, July 1984.
J. P. Cohoon, W. D. Paris “Genie technical report,’’ Dep. Comput. Sci., Univ. of Virginia, 1986.
F. Darema, S . Kirkpatrick, and V. A. Norton “Parallel techniques for chip placement by stimulated annealing on shared memory systems,” in Proc. IEEE Int. Conf. on Computer Design, pp. 87-90, 1987.
REFERENCE Cont . . .
J . J . Grefenstette, R. Gopal, B. Rosmaita, and D. Van Gucht “Genetic algorithms for the traveling salesman problem.” in Proc. Inr. Con$ on Genetic Algorithms and Their Applications, pp. 160-168.1985.
J. J. Grefenstette “Optimization of control parameters for genetic algorithms,” IEEE Trans. Systems, Man, Cybernet., vol. SMC-16,Jan./Feb. 1986.
J. H. Holland Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan, 1972.
M. Jones and P. Bannerjee “Performance of a parallel algorithm for standard cell placement on the intel hypercube,” in Proc. Design Automation Con$, 1987.
S . Kirkpatrick, C. D. Gelatt and M. P. Vecchi “Optimization by simulated annealing,’’ Sci., vol. 220, no. 4598, pp. 671-680, May 13,1983.
R. M. Kling “Placement by simulated evolution,” M.S. thesis, Coordinated Science Lab, College of Engr., Univ. of Illinois at Urbana-Champaign, June 1987.
REFERENCE cont . . .
S . A. Kravitz and R. A. Rutenbar “Placement by simulated annealing on a multiprocessor,” IEEE Trans. Computer-Aided Design, vol.CAD-6, pp. 534-549, June 1987.
S . Nahar, S. Sahni and E. Shragowitz Experiments with simulated annealing,” in Proc. 22nd Design Automation Conf., pp. 748-752,1985.
I . M. Oliver, D. J. Smith, and J. R. C. Holland “A study of permutation crossover operators on the traveling salesman problem.” In Proc. Int. Con$ on Genetic Algorithms and Their Applications, pp.224-230, 1985.
C. Sechen and A. Sangiovanni-Vincentelli “The Timberwolf placement and routing package,” IEEE J . Solid-State Circuirs, vol. SC-20, pp. 510-522, Apr. 1985.
Stadnyk “Schema recombination in pattern recognition problems,” in Proc. Int. Conf. on Genetic Algorithms and Their Applications,pp. 27-35, 1987.