논리 최적화
Logic optimization로직 최적화는 하나 이상의 지정된 제약 조건 하에서 지정된 로직 회로의 동등한 표현을 찾는 프로세스입니다.이 과정은 디지털 전자 장치와 집적 회로 설계에 적용되는 논리 합성의 한 부분입니다.
일반적으로, 회로는 미리 정의된 응답 지연을 충족하는 최소 칩 영역으로 제한됩니다.주어진 회로의 논리 최적화의 목표는 원래의 회로와 같은 값으로 평가하는 가장 작은 논리 회로를 얻는 것입니다.[1]일반적으로 동일한 기능을 가진 더 작은 회로는 비용이 저렴하고,[2] 공간이 적게 들고, 전력이 적게 소모되며, 지연 시간이 짧으며, 예상치 못한 크로스토크, 지연된 신호 처리의 위험 및 집적 회로의 나노 스케일 수준에서 존재하는 다른 문제들을 최소화합니다.
부울 대수학의 관점에서, 복잡한 부울 식을 최적화하는 것은 더 간단한 것을 찾는 과정이며, 평가 시 최종적으로 원래의 것과 같은 결과를 얻을 것입니다.
동기
복잡한 회로(즉, 논리 게이트와 같이 많은 요소를 가진 회로)를 가질 때의 문제점은 각 요소가 물리적 공간을 차지하고 생산하는 데 시간과 비용이 든다는 것입니다.회로 최소화는 집적 회로에서 복잡한 논리의 면적을 줄이기 위해 사용되는 논리 최적화의 한 형태일 수 있습니다.
로직 합성의 출현으로, 전자 설계 자동화(EDA) 업계가 직면한 가장 큰 과제 중 하나는 주어진 설계 기술의 가장 간단한 회로 표현을 찾는 것이었습니다.[nb 1]2단계 논리 최적화는 Quine-McCluskey 알고리즘의 형태로 오랫동안 존재해 왔지만, 나중에 에스프레소 휴리스틱 논리 최소화, 칩 밀도의 빠른 향상, 회로 설명을 위한 하드웨어 설명 언어의 광범위한 채택으로 Lo를 포함한 오늘날 논리 최적화 영역이 공식화되었습니다.gic Friday(그래픽 인터페이스), Minilog([3]미니로그), ESPRESSO-IISOJS(다가치 논리).
방법들
논리 회로 단순화 방법은 부울 식 최소화에도 동일하게 적용할 수 있습니다.
분류
오늘날 논리 최적화는 다음과 같이 다양한 범주로 나뉩니다.
- 회로 표현 기준
- 2단계 논리 최적화
- 다단계 논리 최적화
- 회로 특성에 따라
- 순차 논리 최적화
- 조합논리 최적화
- 실행유형에따름
- 그래픽 최적화 방법
- 표 형태의 최적화 방법
- 대수적 최적화 방법
그래픽 메소드
그래픽 메소드는 함수의 논리 변수와 값을 나타내는 다이어그램으로 필요한 논리 함수를 나타냅니다.다이어그램을 조작하거나 검사하면 지루한 계산을 많이 없앨 수 있습니다.2단계 논리의 그래픽 최소화 방법은 다음과 같습니다.
부울 식 최소화
 |
아래에 나열된 부울 식 최소화(간소화)와 동일한 방법을 회로 최적화에 적용할 수 있습니다.
부울 함수가 회로에 의해 지정된 경우(즉, 가능한 최소 크기의 등가 회로를 찾고자 함), 무한 회로 최소화 문제는 σ P - 시간 복잡도에서 완전한 것으로 길게 추측되었고, 그 결과는 2008년에 마침내 증명되었습니다.그러나 카노 맵과 퀸-매클러스키 알고리즘과 같은 효과적인 휴리스틱이 있습니다.
부울 함수 최소화 방법은 다음과 같습니다.
최적의 다단계 방법
부울 함수의 최적 회로 표현을 찾는 방법은 종종 문헌에서 "정확한 합성"이라고 불립니다.계산 복잡성으로 인해 정확한 합성은 작은 부울 함수에 대해서만 처리할 수 있습니다.최근의 접근법은 최적화 문제를 부울 만족도 문제에 매핑합니다.[5][6]이를 통해 SAT 솔버를 사용하여 최적의 회로 표현을 찾을 수 있습니다.
휴리스틱 방법
휴리스틱 방법은 훨씬 더 큰 문제 집합의 실질적으로 유용한 부분 집합을 해결하는 확립된 규칙을 사용합니다.휴리스틱 방법은 이론적으로 최적화된 솔루션을 제공하지 못할 수도 있지만 유용한 경우 원하는 대부분의 최적화를 최소한의 노력으로 제공합니다.논리 최적화를 위해 휴리스틱 방법을 사용하는 컴퓨터 시스템의 예로는 에스프레소 휴리스틱 논리 최소화기가 있습니다.
2단계 표현과 다단계 표현
회로의 2단계 회로 표현은 설계의[clarification needed] PLA 구현에 더 적용 가능한 SOP(Sum Of Products) 측면에서 회로의 평면도를 엄격하게 언급하지만, 다중 레벨 표현은 임의로 연결된 SOP, POS(Sum Of Sums) 측면에서 회로의 보다 일반적인 관점입니다.팩토리 형식 등논리 최적화 알고리즘은 일반적으로 회로의 구조적(SOP, 인수 형태) 또는 기능적(이진 의사결정 다이어그램, 대수적 의사결정 다이어그램(ADD)) 표현에 대해 작동합니다.SOP(Sum of Products) 형태에서는 AND 게이트가 가장 작은 단위를 이루며 OR을 사용하여 함께 연결되는 반면 POS(Product of Sums) 형태에서는 반대입니다.OR이 AND보다 우선 순위가 낮으므로 POS 양식에서는 AND 게이트 아래에 OR 용어를 그룹화하려면 괄호가 필요합니다.SOP와 POS 형태 모두 회로 로직으로 잘 변환됩니다.
두1 개의 함수 F와 F가2 있는 경우:
위의 2단계 표현은 CMOS Rep에서 6개의 제품 항과 24개의 트랜지스터를 사용합니다.
기능적으로 동등한 멀티레벨 표현은 다음과 같습니다.
- P = B + C.
- F = AP + AD.
- F = A'P + A'E.
여기의 레벨 수는 3개이지만, B+C 항의 공유로 인해 제품의 총 용어 수와 리터럴 수는[quantify] 줄어듭니다.
마찬가지로 조합 회로와 순차 회로를 구분합니다.조합 회로는 전류 입력만을 기반으로 출력을 생성합니다.이들은 부울 관계로 표현될 수 있습니다.일부 예로는 우선순위 인코더, 바이너리 디코더, 멀티플렉서, 디멀티플렉서 등이 있습니다.
순차 회로는 이전 입력을 전류 입력과 구별하기 위해 클럭 신호에 따라 전류 및 과거 입력을 모두 기반으로 출력을 생성합니다.그들은 유한한 상태 기계로 표현될 수 있습니다.예를 들어 플립플롭과 카운터가 있습니다.
예
회로를 최소화하는 여러 가지 방법이 있지만, 이는 부울 함수를 최소화(또는 단순화)하는 예입니다.회로에 의해 수행되는 부울 함수는 함수가 구현되는 대수적 표현과 직접적인 관련이 있습니다.[7] ∧ ¯)∨ ( ¯ ∧ 를 나타내는 데 사용되는 회로를 생각해 보십시오 이 문장에는 두 개의 부정, 두 개의 접속 및 접속사가 사용됩니다.즉, 회로를 구축하려면 인버터 2개, AND 게이트 2개, OR 게이트 1개가 필요합니다.
회로는 부울 대수의 법칙을 적용하거나 직관을 사용하여 단순화(최소화)할 수 있습니다.예제는 가 거짓일 때 이(가) 참이고, 반대의 경우라면 이것은 ≠ B {\를 의미한다고 결론지을 수 있습니다 논리 게이트의 관점에서 부등식은 단순히 XOR 게이트(배타 또는 )를 의미합니다.따라서( ∧ ¯∨ ( ¯ ∧ ⟺ ≠ B 그러면 아래에 표시된 두 회로는 진리표를 사용하여 확인할 수 있듯이 동치입니다
| A | B | (A) | ∧ | B) | ∨ | (A) | ∧ | B) | A | ≠ | B | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F | F | F | F | T | F | T | F | F | F | F | F | ||
| F | T | F | F | F | T | T | T | T | F | T | T | ||
| T | F | T | T | T | T | F | F | F | T | T | F | ||
| T | T | T | F | F | F | F | F | T | T | F | T |
참고 항목
- 이항결정도(BDD)
- 신경쓰지마 상태
- 주요 의미
- 회로 복잡도 - 회로 복잡도 추정에 관한 연구
- 함수구성
- 함수 분해
- 게이트 사용률 저조
- 논리중복
- 하버드 최소화 차트 (Wik variety) (Wikibooks)
메모들
참고문헌
- ^ Maxfield, Clive "Max" (2008-01-01). "Chapter 5: "Traditional" Design Flows". In Maxfield, Clive "Max" (ed.). FPGAs. Instant Access. Burlington: Newnes / Elsevier Inc. pp. 75–106. doi:10.1016/B978-0-7506-8974-8.00005-3. ISBN 978-0-7506-8974-8. Retrieved 2021-10-04.
- ^ Balasanyan, Seyran; Aghagulyan, Mane; Wuttke, Heinz-Dietrich; Henke, Karsten (2018-05-16). "Digital Electronics" (PDF). Bachelor Embedded Systems - Year Group. Tempus. DesIRE. Archived (PDF) from the original on 2021-10-04. Retrieved 2021-10-04. (101페이지)
- ^ Theobald, M.; Nowick, S. M. (November 1998). "Fast heuristic and exact algorithms for two-level hazard-free logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 17 (11): 1130–1147. doi:10.1109/43.736186.
- ^ Buchfuhrer, David; Umans, Christopher (January 2011). "The complexity of Boolean formula minimization" (PDF). Journal of Computer and System Sciences (JCSS). Computer Science Department, California Institute of Technology, Pasadena, California, USA: Elsevier Inc. 77 (1): 142–153. doi:10.1016/j.jcss.2010.06.011. 컨퍼런스 문서의 확장 버전입니다. :
{{cite book}}ignored (도움말) - ^ Haaswijk, Winston. "SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism" (PDF). EPFL. Retrieved 2022-12-07.
- ^ Haaswijk, Winston. "SAT-Based Exact Synthesis for Multi-Level Logic Networks" (PDF). EPFL. Retrieved 2022-12-07.
- ^ Mano, M. Morris; Kime, Charles R. (2014). Logic and Computer Design Fundamentals (4th new international ed.). Pearson Education Limited. p. 54. ISBN 978-1-292-02468-4.
추가열람
- (146 페이지)
- De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill. ISBN 0-07-016333-2. (NB. 제7-9장에서는 조합형 2-레벨, 조합형 멀티-레벨 및 각각 순차 회로 최적화에 대해 다룹니다.)
- Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. Logic Synthesis and Verification Algorithms. Springer Science & Business Media. ISBN 978-0-387-31005-3.
- Kohavi, Zvi; Jha, Niraj K. (2009). "4–6". Switching and Finite Automata Theory (3rd ed.). Cambridge University Press. ISBN 978-0-521-85748-2.
- Rutenbar, Rob A. Multi-level minimization, Part I: Models & Methods (PDF) (lecture slides). Carnegie Mellon University (CMU). Lecture 7. Archived (PDF) from the original on 2018-01-15. Retrieved 2018-01-15; Rutenbar, Rob A. Multi-level minimization, Part II: Cube/Cokernel Extract (PDF) (lecture slides). Carnegie Mellon University (CMU). Lecture 8. Archived (PDF) from the original on 2018-01-15. Retrieved 2018-01-15.
