Due to rapid advances in VLSI design technology during the last decade, the complexity and size of circuits have been rapidly increasing, placing a demand on industry for faster and more efficient CAD tools. Physical design is a process of converting the physical description into geometric description. Physical design process is subdivided into four problems: 1.Partitioning, 2. Floor planning 3. Placement and 4.Routing. Placement phase determines the positions of the cells. Placement constrains are wire-length, area of the die, power minimization and delay. For the area and wire length optimization a modern placer need to handle the large–scale design with millions of object. This thesis work aims to develop an efficient and low time complexity algorithms for placement. This can be achieved by the use of a problem specific genotype encoding, and hybrid, knowledge based techniques, which support the algorithm during the creation of the initial individuals and the optimization process. In this paper a novel hybrid genetic algorithm, which is used to solve standard cell placement problem is presented. These techniques are applied to the multithread of the VLSI cell placement problem where the objectives are to reduce power dissipation and wire length while improving performance (delay).

1. C.J. Alpert and A.B. Kahng. Netlist Partitioning: A Survey. Integration, the VLSI Journal, pages 64–80, 1995
2. S. Areibi. Iterative Improvement Heuristics for the Standard Cell Placement: A Comparison. In 5th World Multi Conference on Systemics, Cybernetics and Informatics, pages 89–94, Orlando, Florida, July 2001.
3. S. Areibi, M. Moussa, and H. Abdullah. A Comparison of Genetic/Memetic Algorithms and Other Heuristic Search Techniques. In International Conference on Artificial Intelligence, pages 660–666, Las Vegas, Nevada, June 2001.
4. S. Areibi, M. Thompson, and A. Vannelli. A Clustering Utility Based Approach for ASIC Design. In 14th Annual IEEE International ASIC/SOC Conference, pages 248–252, Washington, DC, September 2001. IEEE, ACM.
5. J.P. Blanks. Near Optimal Quadratic Based Placement for a Class of IC Layout Problems. IEEE Circuits and Devices, 1(6):31–37, September, 1985.
6. H. Chang, L. Cooks, and M. Hunt. Surviving the SOC Revolution. Kluwer Academic Publishers, London, 1999.
7. W.E Donath. Complexity theory and design automation. In 17th Design Automation Conference, pages 412–419, 1980.
8. H. Etawil, S. Areibi, and T. Vannelli. Convex Programming based Attractor-Repeller Approach for Global Placement. In IEEE International Conference on CAD, pages 20–24, San Jose, California, November 1999. ACM/IEEE
9. M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco CA, 1979.
10. S. Goto and E. Kuh. An approach to the two-dimensional placement problem in circuit layout. IEEE Trans,Circuits System, CAS, 25(4):208–214, 1976.
11. P.N. Parakh, R.B. Brown, and K.A. Sakallah. Congestion Driven Quadractic Placement. In Design Automation Conference, pages 275–278, June 1998.
12. B.M. Riess, K. Doll, and F.M Johannes. Partitioning very large circuits using analytical placement techniques.In Proceedings of DAC, pages 646–651, Las Vegas, Nevada, 1994. ACM/IEEE.
13. W. Sun and C. Sechen. Efficient and Effective Placement for Very Large Circuits. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 14(3):349–359, march 1995.
14. M. Wang, X. Yang, and M. Sarrafzadeh. Congestion Minimization During Placement. IEEE Transactionson Computer Aided Design, 19(10):1140–1148, 2000.
15. Z. Yang and S. Areibi. Global Placement Techniques for VLSI Circuit Design. Technical report, School ofEngineering, University of Guelph, Jul 2002.
16. Z. Yang and S. Areibi. Global Placement Techniques for VLSI Physical Design Automation. In 15th International Conference on Computer Applications in Industry and Engineering, San Diego, California, November2002. ISCA.

VLSI design physical design placement standard cell multithread