인버터 그래프

And-inverter graph

AIG(And-inverter graph)는 회로나 네트워크의 논리적 기능성에 대한 구조적 구현을 나타내는 지시된 반복 그래프다.AIG는 논리적 결합을 나타내는 2입력 노드, 변수 이름으로 표시된 터미널 노드 및 선택적으로 논리적 부정을 나타내는 마커를 포함하는 에지로 구성된다.로직 함수의 이러한 표현은 대형 회로의 경우 구조적으로 효율적인 경우는 드물지만 부울함수의 조작을 위한 효율적인 표현이다.일반적으로 추상 그래프는 소프트웨어에서 데이터 구조로 표현된다.

f(x1, x2, x3) 함수에 대해 구조적으로 서로 다른 두 AIG = x2 *(x1 + x3)

논리 게이트 네트워크에서 AIG로의 전환은 빠르고 확장 가능하다.모든 게이트는 AND 게이트와 인버터 단위로만 표현하면 된다.이 변환은 메모리 사용과 런타임의 예측할 수 없는 증가로 이어지지 않는다.이것은 AIG를 이진 결정도표(BDD) 또는 "제품 총합"(σOo) 형태,[citation needed] 즉 부울대수에서 이항 정규 형태(DNF)와 비교하여 효율적인 표현으로 만든다.BDD와 DNF도 회로로 볼 수 있지만, 그것들은 확장성을 박탈하는 형식적인 제약조건을 포함한다.예를 들어, σOπs는 최대 두 레벨의 회로인 반면, BDD는 표준적인 회로인 반면, 모든 경로에서 입력 변수를 동일한 순서로 평가해야 한다.

AIGs를 포함한 단순한 게이트로 구성된 회로는 "고전적인" 연구 주제다.AIGs에 대한 관심은 그가 낸드 게이트의 무작위 훈련 가능한 네트워크를 설명한 신경망에 관한 앨런 튜링의 1948년 논문으로[1] 시작되었다.관심은 1950년대[2] 후반까지 이어졌고, 다양한 지역 변혁이 전개된 1970년대에도 이어졌다.이러한 변환은 합성 중 면적을 개선하고 지연시키기 위해 회로를 감소시키거나 공식적인 동등성 검사를 가속화하기 위해 회로를 줄이는 대링거 외 및 스미스 외와 같은 몇 가지 로직 합성 및 검증 시스템에서 구현되었다.[3][4]IBM에서는 현재 구조 해싱으로 알려진 다중 입력 논리 표현과 하위 표현들을 결합하고 재사용하는 것과 같은 몇 가지 중요한 기술들이 초기에 발견되었다.

최근 종합과 검증에서 다양한 작업의 기능적 표현으로서 AIG에 대한 관심이 새롭게 대두되고 있다.그 이유는 1990년대에 인기 있었던 표현(예: BDD)이 대부분의 애플리케이션에서 확장성의 한계에 도달했기 때문이다.[citation needed]또 다른 중요한 발전은 훨씬 더 효율적인 부울 만족도(SAT) 해결사들의 최근 출현이었다.AIGs를 회로 표현으로 결합하면 다양한 부울 문제를 해결하는 데 있어 놀라운 속도 향상을 이끈다.[citation needed]

AIGs는 다양한 EDA 애플리케이션에서 성공적인 사용을 발견했다.AIGs와 부울 만족도의 잘 조화된 조합은 모델 확인과 동등성 검사를 모두 포함한 공식 검증에 영향을 미쳤다.[5]또 다른 최근의 연구는 AIG를 사용하여 효율적인 회로 압축 기술을 개발할 수 있다는 것을 보여준다.[6]기능 속성(대칭 등)[7]과 노드 유연성을 계산하는 시뮬레이션과 부울만족도를 이용해 논리합성 및 물리적 합성 문제를 해결할 수 있다는 이해(예: 관리하지 않는 용어, 재분배, SPFD)가 증가하고 있다.[8][9][10]미셴코 외 연구진은 AIGs가 로직 합성, 기술 매핑, 물리적 합성, 형식 검증 등을 연결할 수 있는 유망한 단일화 표현임을 보여준다.이는 동일한 데이터 구조를 공유하기 위해 재작성, 시뮬레이션, 매핑, 배치, 검증 등이 가능한 AIGs의 단순하고 균일한 구조로 인해 크게 볼 수 있다.

조합 논리 외에도 AIG는 순차 논리 변환과 순차 변환에도 적용됐다.구체적으로는, 구조 해싱의 방법을 확장해 메모리 요소(일반적으로, 알 수 없는 초기 상태의 D형 플립플롭스와 같은)를 가진 AIG에 대해 작용하도록 하여, 리티밍과 관련된 애플리케이션에 특별히 맞춘 데이터 구조를 만들었다.[11]

현재 진행 중인 연구에는 AIG를 기반으로 한 현대적 논리합성 시스템을 완전히 구현하는 것이 포함된다.ABC라고 불리는 프로토타입은 AIG 패키지, 여러 AIG 기반 합성 및 동등성 검사 기법, 그리고 순차 합성의 실험적 구현을 특징으로 한다.그러한 기법 중 하나는 기술 매핑과 레티밍을 단일 최적화 단계로 결합한 것이다.이러한 최적화는 임의 게이트로 구성된 네트워크를 사용하여 구현할 수 있지만 AIG를 사용하면 확장성이 뛰어나고 구현이 용이하다.

구현

참조

  1. ^ 튜링의 1948년 논문은 튜링 AM으로 다시 인쇄되었다.인텔리전트 머신.In: Ince DC, 편집자.AM 튜링 - 기계 인텔리전스(Mechanical Intelligence)의 수집 작업.1992년 엘시어 사이언스 출판사
  2. ^ L. Hellerman (June 1963). "A catalog of three-variable Or-Inverter and And-Inverter logical circuits". IEEE Trans. Electron. Comput. EC-12 (3): 198–223. doi:10.1109/PGEC.1963.263531.
  3. ^ A. Darringer; W. H. Joyner, Jr.; C. L. Berman; L. Trevillyan (Jul 1981). "Logic synthesis through local transformations". IBM Journal of Research and Development. 25 (4): 272–280. CiteSeerX 10.1.1.85.7515. doi:10.1147/rd.254.0272.
  4. ^ G. L. Smith; R. J. Bahnsen; H. Halliwell (Jan 1982). "Boolean comparison of hardware and flowcharts". IBM Journal of Research and Development. 26 (1): 106–116. CiteSeerX 10.1.1.85.2196. doi:10.1147/rd.261.0106.
  5. ^ A. Kuehlmann; V. Paruthi; F. Krohm; M. K. Ganai (2002). "Robust boolean reasoning for equivalence checking and functional property verification". IEEE Trans. CAD. 21 (12): 1377–1394. CiteSeerX 10.1.1.119.9047. doi:10.1109/tcad.2002.804386.
  6. ^ Per Bjesse; Arne Borälv (2004). "DAG-aware circuit compression for formal verification" (PDF). Proc. ICCAD '04. pp. 42–49.
  7. ^ K.-H. Chang; I. L. Markov; V. Bertacco (2005). "Post-placement rewiring and rebuffering by exhaustive search for functional symmetries" (PDF). Proc. ICCAD '05. pp. 56–63.
  8. ^ A. Mishchenko; J. S. Zhang; S. Sinha; J. R. Burch; R. Brayton; M. Chrzanowska-Jeske (May 2006). "Using simulation and satisfiability to compute flexibilities in Boolean networks" (PDF). IEEE Trans. CAD. 25 (5): 743–755. CiteSeerX 10.1.1.62.8602. doi:10.1109/tcad.2005.860955.
  9. ^ S. Sinha; R. K. Brayton (1998). "Implementation and use of SPFDs in optimizing Boolean networks". Proc. ICCAD. pp. 103–110. CiteSeerX 10.1.1.488.8889.
  10. ^ S. Yamashita; H. Sawada; A. Nagoya (1996). "A new method to express functional permissibilities for LUT based FPGAs and its applications" (PDF). Proc. ICCAD. pp. 254–261.
  11. ^ J. Baumgartner; A. Kuehlmann (2001). "Min-area retiming on flexible circuit structures" (PDF). Proc. ICCAD'01. pp. 176–182.

참고 항목

본 기사는 ACM SIGDA e-뉴스레터의 칼럼에서 채택된 것으로 Alan Mishchenko Original 텍스트가 여기에 수록되어 있다.