| Author | Thida Aye |
| Call Number | AIT Thesis no.CS-95-09 |
| Subject(s) | Integrated circuits--Very large scale integration
|
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of
Engineering |
| Publisher | Asian Institute of Technology |
| Abstract | Channel Routing Problem (CRP) is an NP-hard optimization problem in detailed
routing phase of the VLSI physical design. Genetic Algorithms are a new class of heuristic
search and optimization strategies which have been applied successfully to find good solutions
to several optimization problems. We have designed and implemented a genetic algorithm-based
system to solve the CRP. Several well-known benchmark CRPs were solved using our
GA-based router. It was shown that our system can produce solutions to the benchmark CRPs
with the minimum number of used tracks as obtained by theory and other traditional non-GA
routers. The fitness function of our system considers both the number of used tracks and the
total length of vertical segments as the optimization objectives. By carefully adjusting the cost
factors for these two objectives, solutions were obtained with the optimal values of total
vertical length. We have also implemented two other non-GA channel routers based on some
straightforward heuristics. By comparing the solutions obtained by non-GA routers with those
of GA-based router, results from the GA-based system were verified. |
| Year | 1995 |
| Type | Thesis |
| School | School of Engineering and Technology (SET) |
| Department | Department of Information and Communications Technologies (DICT) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Yulu, Qi; |
| Examination Committee(s) | Batanov, Dentcho N.;Murai, Shunji; |
| Scholarship Donor(s) | The Government of Finland; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 1995 |