유전자 알고리즘을 이용한 이진결정도의 최소화 = Minimizing Binary Decision Diagrams based on Genetic Algorithms

국문 초록 (Abstract)

이진결정도(Binary Decision Diagrams)는 부울 함수(Boolean function)를 비순환 방향 그래프(Directed Acyclic Graph)로 나타낸 것이다. 이진결정도를 이용하면, 부울 함수를 간결하고 유일하게 나타낼 수 있기 때문에, 이진경결정도는 논리 회로 합성, 설계 검증, 테스트 패턴 생성, 고장 시뮬레이션 등의 다양한 분야에 이용된다.
이진결정도의 크기는 입력 변수의 배열 순서에 따라 민감하게 변하므로, 이진결정도의 크기를 최소화 할 수 있는 변수 배열 순서를 결정하는 일은 대단히 중요하다. 더우기 DCVS (Differential Cascode Voltage Switch) 회로의 합성과 같은 문제에 이진결정도를 이용할 경우, 이진결정도의 크기가 회로 구현에 직결되기 때문에 최종적인 이진결정도의 크기를 줄이는 것이 최우선 관심사이다.
최적의 변수 배열 순서를 결정하는 일은 co-NP complete 문제이므로, 양호한 변수 배열 순서를 결정하기 위한 여러가지 휴리스틱 알고리즘(heuristic algorithm)이 제안되었다. 그러나 한가지 휴리스틱 알고리즘만으로 언제나 다른 휴리스틱 방법에 비해 더 나은 변수 순서를 결정할 수 있는 것은 아니다. 본 논문에서는 유전자 알고리즘을 이용한 변수 배열 순서 방식을 제안하였고, 수용할 만한 결과를 얻었다. 즉, 최적화 문제의 해결에 유용한 특성을 지닌 유전자 알고리즘을 이용하여, 근사 최적 변수 순서(near-optimal variable ordering)를 가진 이진결정도를 생성한다.

다국어 초록 (Multilingual Abstract)

Binary Decision Diagrams (BDDs) represent Boolean functions as directed acyclic graphs (DAG). Using BDDs, we can represent Boolean functions uniquely and compactly. Hence, BDDs have become widely used for CAD applications, such as logic synthesis, design verification, test pattern generation, and fault simulation.
The size of the BDDs representation for a function is very sensitive to the choice of orderings on the input variables. Therefore, it is very important to find good variable orderings which minimize the size of the BDDs. Furthermore, in case where we apply BDDs to such as the synthesis of differential cascode voltage switch, reducing the size of the BDDs is the primary concerns.
Since finding an optimal ordering is co-NP complete, several heuristic algorithms have been proposed to find good variable orderings. Nevertheless, no single heuristic algorithms always provide good variable orderings than other heuristics.
In this paper, we propose a variable ordering method based on the genetic algorithms. We apply genetic algorithms which are very useful in solving the problems of optimization to the variable orderings in BDDs to find near-optimal variable orderings. And we get acceptable results.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 이진결정도와 유전자 알고리즘
• 3. 실험 결과
• 4. 결론
• 참고문헌
• 저자소개