검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Algorithm for Generating Generic BDDs 일반 BDD 생성을 위한 알고리즘

Tetsushi KATAYAMA, Hiroyuki OCHI, Takao TSUDA

  • 조회수

    0

  • 이것을 인용

요약 :

BDD(이진 결정 다이어그램)는 부울 함수를 그래프로 표현한 것입니다. 특히, Obdd(순서형 BDD)는 표준 표현을 제공하고 효율적으로 조작되므로 많은 상황에서 유용합니다. OBDD를 자동으로 생성하는 BDD 패키지가 개발되어 정형검증, 논리합성 등 논리설계 분야에서 널리 사용되고 있다. 패스 트랜지스터 회로의 합성은 BDD 패키지의 성공적인 응용 중 하나입니다. 패스 트랜지스터 회로는 각 노드를 89개 또는 32개의 패스 트랜지스터로 구성된 선택기에 매핑하여 BDD에서 생성됩니다. 더 작은 BDD에서 회로를 생성하는 경우 생성된 회로는 더 적은 수의 트랜지스터를 가지므로 칩 면적과 전력 소비가 절약됩니다. 본 논문에서는 경로의 가변 순서 및 가변 출현 횟수에 제한이 없는 보다 일반적인 BDD를 GBDD(Generic BDD)라고 하며, 패스 트랜지스터 회로의 합성을 목적으로 GBDD를 생성하는 알고리즘을 제안합니다. 제안하는 알고리즘은 두 단계로 구성된다. 첫 번째 단계에서는 주어진 부울 공식에 대한 구문 분석 트리(PT)가 생성됩니다. 여기서 PT는 부울 공식의 방향성 트리 표현이며 리터럴 노드와 작업 노드로 구성됩니다. 이 단계에서 우리의 알고리즘은 PT의 리터럴 노드 수를 줄이려고 시도합니다. 두 번째 단계에서는 Concatenation Method를 사용하여 PT에 대해 GBDD를 생성하는데, Concatenation Method는 GBDD를 수직으로 연결하여 GBDD를 생성한다. 이 단계에서 우리의 알고리즘은 동형 하위 그래프를 공유하려고 시도합니다. ISCAS'680 및 MCNC 벤치마크 회로에 대한 실험에서 우리 프로그램은 4개의 단일 출력 기능 중 49개의 GBDD를 성공적으로 생성했으며 크기가 크기가 OBDD보다 작은 23.1개의 다중 출력 기능 중 XNUMX개의 GBDD를 성공적으로 생성했습니다. 최적의 경우 GBDD 크기는 OBDD에 비해 XNUMX% 감소합니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.12 pp.2505-2512
발행일
2000/12/25
공개일
온라인 ISSN
DOI
원고의 종류
Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
범주
논리합성

작성자

키워드