Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
A NOVEL APPROACH TO OPTIMIZATION ALGORITHM FOR VLSI
#1

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, IEE 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. IEE 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, IEE 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, IEE 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, IEE 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.
Reply



Forum Jump:


Users browsing this thread:
1 Guest(s)

Powered By MyBB, © 2002-2024 iAndrew & Melroy van den Berg.