회로 분할을 위한 어댑티드 유전자 알고리즘 연구

국문 초록 (Abstract)

VLSI 설계에서의 분할(partitioning)은 기능의 최적화를 위하여 설계하고자 하는 회로의 그룹화(grouping)하는 단계로서 레이아웃(layout)에서 면적과 전파지연의 최소화를 위해 함께 배치할 소자를 결정하는 문제이다. 이러한 분할 문제에서 해를 얻기 위해 사용되는 알고리즘은 Kernighan-Lin 알고리즘, Fiduccia Mattheyses heuristic, 시뮬레이티드 어닐링, 유전자 알고리즘 등의 방식이 이용된다. 본 논문에서는 회로 분할 문제에 대하여 유전자 알고리즘과 확률 진화 알고리즘을 결합한 어댑티드 유전자 알고리즘을 이용한 해 공간 탐색(solution space search) 방식을 제안하였으며, 제안한 방식을 유전자 알고리즘 및 시뮬레이티드 어닐링 방식과 비교, 분석하였고, 어댑티드 유전자 알고리즘이 시뮬레이티드 어닐링 및 유전자 알고리즘보다 더 효과적으로 최적해에 근접하는 것을 알 수 있었다.

다국어 초록 (Multilingual Abstract)

In VLSI design, partitioning is a task of clustering objects into groups so that a given objective circuit is optimized. It is used at the layout level to find strongly connected components that can be placed together in order to minimize the layout area and propagation delay. The most popular algorithms for partitioning include the Kernighan-Lin algorithm, Fiduccia-Mattheyses heuristic and simulated annealing. In this paper, we propose a adapted genetic algorithm searching solution space for the circuit partitioning problem, and then compare it with simulated annealing and genetic algorithm by analyzing the results of implementation. As a result, it was found that an adaptive genetic algorithm approaches the optimal solution more effectively than the simulated annealing and genetic algorithm.

목차 (Table of Contents)

• 요약
• Abstract
• I. 서론
• Ⅱ. 회로 분할 문제
• Ⅲ. 어댑티드 회로 분할 유전자 알고리즘
• Ⅳ. 시뮬레이션
• Ⅴ. 결론
• 참고문헌

참고문헌 (Reference)

1 D. Goldberg, "loci and the Traveling Salesman Problem" Lawrence Erlbaum Associates 154-159, 1985

2 S. M. Sait, "VLSI Physical Design Automation Theory and Practice" World Scientific Publishing 2001

3 C. Sechen, "Timberwolf3.2 : A new standard cell placement and global routing package" 1 : 432-439, 1986

4 S. kirkpatrick, "Optimization by Simulated Annealing" 220 (220): 671-680, 1983

5 J. Cong, "Net partitions yield better module partitions" 47-52, 1992

6 S. M. Sait, "Iterative Computer Algorithms with Applications in Engineering" 1999

7 M. Gen, "Genetic Algorithms and Engineering Optimization" Wiley-Interscience publication 2000

8 M. Gen, "Genetic Algorithms and Engineering Design" Wiley 1997

9 Z. Michalewicz, "Genetic Algorithm + Data Structure = Evolution Programs" Springer-Verlag 1996

10 T. Bäck, "Evolutionary Algorithms in Theory and Practice" Oxford University Press 1996

11 K. Kozminski, "Benchmarks for layout synthesis – evolution and current status" 265-270, 1991

12 C. Cheng, "An Improved two-way Partitioning algorithm with stable performance" 10 (10): 1502-1511, 1991

13 K. H. Kernighan, "An Efficient Heuristic Procedure for Partitioning Graph" 49 (49): 291-307, 1970

14 J. H. Holland, "Adaptation in Natural Artificial Systems" University of Michigan Press 1975

15 C. M. Fiduccia, "A linear time heuristic for improving network partitiions" 175-181, 1982