에스프레소 휴리스틱 로직 미니마이저

Espresso heuristic logic minimizer

ESPRESO 로직 미니마이저는 디지털 로직 게이트 회로의 복잡성을 효율적으로 줄이기 위해 휴리스틱하고 구체적인 알고리즘을 이용한 컴퓨터 프로그램이다.[1] 에스프레소-I는 원래 IBM에서 로버트 K에 의해 개발되었다. 1982년 브레이튼 외.[2][3][4][5] 1984년 에스프레소-II로 개선되었다. 리처드 L. 루델은 이후 1986년[6] 변종 ESPRESO-MV, 1987년 변종 ESPRESOR-EXACT를 발표하였다.[7][8][5] 에스프레소는 많은 파생상품에 영감을 주었다.

소개

전자 장치는 수많은 디지털 회로 블록으로 구성되며, 이 블록의 조합은 필요한 작업을 수행한다. 로직 게이트 회로의 형태로 로직 기능을 효율적으로 구현하는 것(필요한 것보다 더 많은 로직 게이트를 사용하지 않는 것)은 생산비를 최소화하거나 기기의 성능을 극대화하기 위해 필요하다.

디지털 로직 회로 설계

모든 디지털 시스템은 정보를 저장하는 메모리 소자와 그 정보를 변환하는 결합 회로의 두 가지 기본적인 기능으로 구성된다. 상태 기계는 카운터와 마찬가지로 메모리 요소와 결합 논리 회로의 조합이다. 메모리 소자는 표준 로직 회로이기 때문에 제한된 대체 회로 세트 중에서 선택된다. 따라서 디지털 기능을 설계하는 것은 결합 게이트 회로를 설계하고 상호 연결하는 것이다.

일반적으로 고도의 추상화로부터 논리회로의 인스턴스화를 로직합성이라고 하는데, 이것은 손으로 수행할 수 있지만, 대개는 컴퓨터에 의한 어떤 형식적인 방법이 적용된다. 이 글에는 조합 논리 회로의 설계 방법이 간략하게 요약되어 있다.

디지털 로직 회로 설계의 출발점은 원하는 기능이며, 시스템 전체의 분석에서 파생된 로직 회로는 그 일부를 구성한다. 설명은 일부 알고리즘 형식 또는 논리 방정식으로 명시될 수 있지만 표 형식으로도 요약할 수 있다. 아래 예는 표시장치 각 세그먼트에 불이 들어오게 하는 신호로 소수 자릿수 값에 대한 이진 코드를 변환하는 7-세그먼트 표시장치 드라이버에 대한 표의 일부를 보여준다. 

  숫자 코드 세그먼트 A B C D E G 0 0000 1 1 1 1 1 1 0 -A- 1 0001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 F B 3 00111 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -G-1 0 G- 5101 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    0110 1 1 1 1 E C 7 0111 1 1 1 0 0 0 0 0 0 8 1000 1 1 1 1 -D- 9 1001 1 1 0 1

구현 프로세스는 별도의 용어를 더 적은 변수를 포함하는 큰 용어로 결합하여 기능 표를 단순화하기 위해 아래에서 설명하는 로직 최소화 단계로 시작한다.

다음으로, 최소화된 결과는 인자화 절차에 의해 작은 부분으로 분할될 수 있으며, 결국 대상 기술의 이용 가능한 기본 논리 셀에 매핑된다. 이 연산을 일반적으로 로직 최적화라고 한다.[9]

고전적 최소화 방법

고전적인 Karnaugh 지도를 사용하여 손으로 부울 기능을 최소화하는 것은 힘들고 지루하며 오류가 발생하기 쉬운 과정이다. 6개 이상의 입력 변수에는 적합하지 않고 최대 4개 변수에만 실용적이며, 다중 출력 기능에 대한 제품 용어 공유는 더욱 어렵다.[10] 게다가, 이 방법은 컴퓨터 프로그램의 형태로 자동화되도록 스스로 빌려주지는 않는다. 그러나 현대의 논리기능은 일반적으로 그러한 적은 수의 변수에 구속되지 않는 반면, 논리기능의 수동적 구현에는 비용과 오류의 위험이 엄두도 못 낼 정도로 높아져 컴퓨터 사용이 불가결해졌다.

인기 있는 첫 번째 대안 방법은 윌러드 콰인과 에드워드 맥클러스키가 개발한 표 방식이었다. 논리 기능 집합에 대한 진실 표부터 시작하여 기능이 활성(ON-커버)되거나 함수 값이 관련이 없는(Don't-Care-cover 또는 DC 커버)의 최소 조건을 결합하여 주요 내연성 물질 집합을 구성한다. 마지막으로, 출력 기능이 실현될 수 있는 최소의 프라이밍 내연성 물질을 찾기 위한 체계적 절차를 따른다.[11][12]

비록 이 Quine-McCluskey 알고리즘이 컴퓨터 프로그램에서 구현되기에 매우 적합하지만, 처리 시간과 메모리 사용의 측면에서 그 결과는 여전히 효율적이지 못하다. 변수의 수에 따라 진리표 길이가 기하급수적으로 증가하기 때문에 함수에 변수를 추가하면 두 변수 모두 대략 두 배가 된다. 조합 함수 블록의 출력 함수 수를 늘릴 때도 비슷한 문제가 발생한다. 결과적으로 Quine-McCluskey 방법은 입력 변수와 출력 기능이 제한된 기능에만 실용적이다.

에스프레소 알고리즘

이 문제에 대한 다른 접근법은 버클리 캘리포니아 대학의 브레이튼 외 연구진이 개발한 ESPRESO 알고리즘에 따른다.[4][3] 경험적 위험 없는 2-레벨 로직 최소화 문제를 해결하기 위한 자원 및 성능 효율 알고리즘이다.[13]

이 프로그램은 논리 함수를 분광기(minterms)로 확장하는 대신 ON, DC-, OFF-에서 제품 용어를 나타내는 "Cube"를 반복적으로 다룬다. 최소화가 전지구적 최소화가 보장되지는 않지만, 실제로 이는 매우 근사치인 반면 솔루션은 항상 중복성이 없다. 다른 방법들에 비해 이 방법은 본질적으로 더 효율적이어서 메모리 사용과 연산 시간을 몇 배나 줄인다. 그 이름은 즉시 신선한 커피 한 잔을 만드는 방법을 반영한다. 조합함수 블록의 변수 수, 출력함수 및 제품 조건에는 제한이 거의 없다. 일반적으로 출력함수가 수십 개인 변수들은 쉽게 처리된다.

ESPRESO에 대한 입력은 원하는 기능의 함수 테이블이다. 그 결과는 선택한 옵션에 따라 기능의 ON 커버 또는 OFF 커버를 설명하는 최소화된 표이다. 기본적으로 제품 조건은 여러 출력 기능에 의해 최대한 공유되지만 프로그램에서는 출력 기능을 각각 따로 다루도록 지시할 수 있다. 이를 통해 PLA(Programmable Logic Array) 또는 PAL(Programmable Array Logic)과 같은 2단계 로직 어레이에서 효율적인 구현이 가능하다.

ESPRESO 알고리즘은 매우 성공적이어서 거의 모든 동시대 로직 합성 도구에 표준 로직 함수 최소화 단계로 통합되었다. 다중 레벨 로직의 기능을 구현하기 위해, 최소화 결과는 인자화에 의해 최적화되며, 이것이 현장 프로그래밍 가능한 게이트 어레이(FPGA) 또는 애플리케이션별 통합 회로(ASIC)와 관련이 있는지 여부에 관계없이 대상 기술에서 이용 가능한 기본 논리 셀에 매핑된다.

소프트웨어

에스프레소

오리지널 에스프레소 프로그램은 버클리 캘리포니아 대학교 웹사이트에서 C 소스 코드로 이용할 수 있다. 마지막 버전은 1988년 버전 2.3이었습니다.[14] 현대 POSIX 시스템을 위한 ESPRESOT의 업데이트 버전인 ESPRESOT-AB와 EQNTOT(진실표와 동일) 프로그램은 C 소스 코드뿐만 아니라 데비안 리눅스 배포(.deb) 파일 형식으로도 이용할 수 있다. 마지막 버전은 2008년 버전 9.0이었습니다.[15]

로직 프라이데이

로직 프라이데이(Logic Friday)는 에스프레소에 그래픽 인터페이스를 제공하는 무료 윈도 프로그램이며, 실수도 있다.버클리 옥토터스 패키지의 또 다른 모듈 II. Logic Friday 사용자는 논리 함수를 진리표, 방정식 또는 게이트 다이어그램으로 입력하고 함수를 최소화한 다음 다른 두 가지 표현 모두에서 결과를 볼 수 있다. 마지막 버전은 2012년 버전 1.1.4이었습니다.[16]

미니로그

미니로그는 이 에스프레소 알고리즘을 활용한 로직 최소화를 제공하는 무료 윈도 프로그램이다. 최대 40개의 입출력 결합기능 블록이나 최대 256개의 상태를 가진 동기식 상태 머신을 위한 2레벨 게이트 구현이 가능하다. 그것은 Publicad 교육 디자인 패키지의 일부분이다.

에스프레소-아이소제스

에스프레소-아이소JS는 단일 출력 기능을 위한 에스프레소-II의 자바스크립트 구현이다. 유니테이트 재귀 패러다임에 기초한 ESPRESO-II의 다양한 알고리즘에 대한 추가 최적화 기법으로 단위 전파를 채택하고 있다. 또 다른 추가 사항은 언제 리터럴을 올릴 수 있는지 통제할 수 있도록 하는 것인데, 이를 이용하여 클레인 논리 기능을 효과적으로 최소화할 수 있다.[17]

참조

  1. ^ Hayes, John Patrick (1993). Digital Logic Design. Addison Wesley. ISBN 0-201-15461-7.
  2. ^ Brayton, Robert King; Hachtel, Gary D.; Hemachandra, Lane A.; Newton, A. Richard; Sangiovanni-Vincentelli, Alberto Luigi M. (1982). "A comparison of logic minimization strategies using ESPRESSO: an APL program package for partitioned logic simulation". Proceedings of the IEEE International Symposium on Circuits and Systems, 1982. New York, New York, USA: IEEE: 42–48.
  3. ^ a b "Robert K. Brayton; Professor Emeritus, Professor in the Graduate School". University of California, Berkeley. 2018-09-23. Archived from the original on 2018-09-23. Retrieved 2018-09-23.
  4. ^ a b Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis Tracy; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Logic Minimization Algorithms for VLSI Synthesis (9th printing 2000, 1st ed.). Boston, Massachusetts, USA: Kluwer Academic Publishers. ISBN 0-89838-164-9.
  5. ^ a b 볼튼, 마틴(1990년)."4.3.3ESPRESSO-II".브리스틀 대학교, 영국 브리스톨에서 쓰여진.Dagless에서, 에릭은 L.(교육.).디지털 시스템 디자인 연산과 논리.전자 시스템 공학 시리즈(1판).오킹엄, 영국:Addison-Wesley 출판사 주식 회사를 대신하여 서명함. 112, 115–116.아이 에스비엔 0-201-14545-6. LCCN 90000007.아이 에스비엔 978-0-201-14545-8 궤:/13960/t2f83p38r.2021-04-17 Retrieved.{{책을 인용하다.}}:CS1 maint:url-status(링크)(xiv+379+1 페이지).
  6. ^ Rudell, Richard L. (1986-06-05). Multiple-Valued Logic Minimization for PLA Synthesis (PDF). Memorandum No. UCB/ERL M86-65. Berkeley, USA.
  7. ^ Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi M. (September 1987). "Multiple-valued logic minimization for PLA optimization". IEEE Transactions on Computer-Aided Design. 6 (5): 727–750.
  8. ^ Rudell, Richard L. (April 1989). Logic Synthesis for VLSI Design (PhD thesis). Electronics Research Laboratory, College of Engineering, University of California, Berkeley, USA. (ESPRESOR-EXact)
  9. ^ De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill Science Engineering. ISBN 0-07-016333-2.
  10. ^ Lewin, Douglas (1985). Design of Logic Systems. Van Nostrand (UK). ISBN 0-442-30606-7.
  11. ^ Katz, Randy Howard; Borriello, Gaetano (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company. ISBN 0-8053-2703-7.
  12. ^ Lala, Parag K. (1996). Practical Digital Logic Design and Testing. Prentice Hall. ISBN 0-02-367171-8.
  13. ^ Theobald, Michael; Nowick, Steven M. "Fast Heuristic and Exact Algorithms for Two-Level Hazard-Free Logic Minimization". Department of Computer Science, Columbia University. Retrieved 2021-10-04.{{cite web}}: CS1 maint : url-status (링크)
  14. ^ "Espresso C source code (1988)". University of California, Berkeley. 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
  15. ^ "Espresso-eb / eqntott C source code and program (2008)". Google Code. 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
  16. ^ "Logic Friday program (2012)". sontrak. 2018-09-21. Archived from the original on 2013-10-22. Retrieved 2018-09-21.
  17. ^ "Espresso-IISOJS".

추가 읽기

  • Eschermann, Bernhard (May 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [Functional design of digital circuits - Methods and CAD techniques]. Springer-Lehrbuch (in German). Springer-Verlag. pp. 136–137, 140–141. ISBN 9-783540-56788-2. ISBN 3-540-56788-7.