بهینه سازی منطقی

این صفحه در حال ترجمه مقاله انگلیسی است لطفاً حذف نشود.

بهینه‌سازی منطقی فرآیندی است که در آن یک نمایش معادل از یک مدار منطقی مشخص شده، تحت یک یا چند محدودیت مشخص، پیدا می‌شود. این فرایند بخشی از سنتز منطقی است که در الکترونیک دیجیتال و طراحی مدارهای مجتمع کاربرد دارد.

به‌طور کلی، مدار به یک مساحت حداقل تراشه محدود می‌شود که یک تأخیر پاسخ از پیش تعریف شده را برآورده می‌کند. هدف بهینه‌سازی منطقی یک مدار معین، به دست آوردن کوچک‌ترین مدار منطقی است که همان مقادیر مدار اصلی را ارزیابی می‌کند. معمولاً، مدار کوچکتر با همان عملکرد ارزان‌تر است، فضای کمتری را اشغال می‌کند، مصرف انرژی کمتری دارد، دارای تأخیر کمتری است و خطرات تداخل غیرمنتظره، خطر پردازش سیگنال تأخیری و سایر مسائل موجود در سطح نانو ساختارهای فلزی را بر روی یک مدار مجتمع به حداقل می‌رساند.

از نظر جبر بولی، بهینه‌سازی یک عبارت بولی پیچیده فرایند پیدا کردن یک عبارت ساده‌تر است که هنگام ارزیابی، در نهایت نتایج مشابهی با عبارت اصلی تولید می‌کند.

انگیزه

مشکل داشتن یک مدار پیچیده (یعنی مداری با عناصر متعدد مانند دروازه‌های منطقی) این است که هر عنصر فضای فیزیکی اشغال می‌کند و تولید آن زمان و هزینه می‌برد. مینیمم‌سازی مدار می‌تواند یکی از اشکال بهینه‌سازی منطقی باشد که برای کاهش مساحت منطق پیچیده در مدارهای مجتمع استفاده می‌شود.

با ظهور سنتز منطقی، یکی از بزرگ‌ترین چالش‌های صنعت خودکارسازی طراحی الکترونیک (EDA) یافتن ساده‌ترین نمایش مدار از توصیف طراحی داده شده بود. در حالی که بهینه‌سازی منطق دو سطحی به شکل الگوریتم کوین-مک کلاسکی و بعداً به دنبال آن بهینه‌ساز منطقی ابتکاری اسپرسو وجود داشت، تراکم تراشه‌های در حال بهبود سریع و پذیرش گسترده زبان‌های توصیف سخت‌افزار برای توصیف مدار، حوزه بهینه‌سازی منطقی را همان‌طور که امروز وجود دارد، رسمی کرد، از جمله Logic Friday (رابط گرافیکی)، Minilog و ESPRESSO-IISOJS (منطق چند ارزشی).

روش‌ها

روش‌های ساده‌سازی مدار منطقی به یک اندازه برای مینیمم‌سازی عبارت‌های بولی قابل استفاده هستند.

طبقه‌بندی

امروزه، بهینه‌سازی منطقی به دسته‌های مختلفی تقسیم می‌شود:

بر اساس نمایش مدار

• بهینه‌سازی منطقی دو سطحی
• بهینه‌سازی منطقی چندسطحی

بر اساس ویژگی‌های مدار

• بهینه‌سازی منطق ترتیبی
• بهینه‌سازی منطق ترکیبی

بر اساس نوع اجرا

• روش‌های بهینه‌سازی گرافیکی
• روش‌های بهینه‌سازی جدولی
• روش‌های بهینه‌سازی جبری

روش‌های گرافیکی

روش‌های گرافیکی، تابع منطقی مورد نیاز را با استفاده از یک نمودار که متغیرهای منطقی و مقدار تابع را نشان می‌دهد، نمایش می‌دهند. با دستکاری یا بررسی یک نمودار، می‌توان از بسیاری از محاسبات خسته‌کننده جلوگیری کرد. روش‌های کمینه‌سازی گرافیکی برای منطق دو سطحی شامل:

• • نمودار اویلر (یا دایره اویلری) (۱۷۶۸) توسط لئونارد اویلر (۱۷۰۷–۱۷۸۳)
  • نمودار ون (۱۸۸۰) توسط جان ون (۱۸۳۴–۱۹۲۳)
  • جدول کارنو (۱۹۵۳) توسط موریس کارنو

بهینه‌سازی (ساده‌سازی) عبارات بولی

همان روش‌های ساده‌سازی عبارات بولی که در زیر فهرست شده‌اند، ممکن است برای بهینه‌سازی مدار اعمال شوند.

در حالتی که تابع بولی توسط یک مدار مشخص شده باشد (یعنی می‌خواهیم یک مدار معادل با حداقل اندازه ممکن پیدا کنیم)، مشکل ساده‌سازی مدار نامحدود، برای مدت طولانی حدس زده می‌شد که در پیچیدگی زمانی Σ2P- کامل باشد، نتیجه‌ای که در نهایت در سال ۲۰۰۸ ثابت شد، اما برخی از روش‌های ابتکاری مؤثر مانند جدول‌های کارنو و الگوریتم کواین-مک‌کلاسی وجود دارند که این فرایند را تسهیل می‌کنند.

روش‌های کمینه‌سازی تابع بولی عبارتند از:

• • الگوریتم کواین-مک کلاسکی
  • روش پتریک

روش‌های چندسطحی بهینه

روش‌هایی که نمایش‌های مدار بهینه برای توابع بولی پیدا می‌کنند، اغلب در ادبیات به عنوان سنتز دقیق شناخته می‌شوند. به دلیل پیچیدگی محاسباتی، سنتز دقیق تنها برای توابع بولی کوچک قابل حل است. رویکردهای اخیر مسئله بهینه‌سازی را به یک مسئله رضایت‌پذیری بولی نگاشت می‌کنند. این امکان را فراهم می‌کند تا با استفاده از یک حل‌کننده SAT، نمایش‌های مدار بهینه را پیدا کرد.

روش‌های اکتشافی

یک روش ابتکاری از قوانین مشخصی استفاده می‌کند که زیرمجموعه‌ای عملی و مفید از مجموعه بسیار بزرگ‌تر مشکلات ممکن را حل می‌کند. روش ابتکاری ممکن است بهینه‌ترین راه‌حل نظری را تولید نکند، اما اگر مفید باشد، بیشتر بهینه‌سازی مورد نظر را با حداقل تلاش فراهم می‌کند. یک مثال از یک سیستم کامپیوتری که از روش‌های ابتکاری برای بهینه‌سازی منطق استفاده می‌کند، بهینه‌ساز منطق ابتکاری Espresso است.

نمایش‌های دو سطحی در مقابل نمایش‌های چندسطحی

در حالی که یک نمایش دو سطحی مدار به‌طور دقیق به نمای مسطح مدار از نظر مجموع حاصلضرب‌ها (SOP) اشاره دارد - که بیشتر برای پیاده‌سازی PLA طراحی قابل اجرا است [نیازمند توضیح] - یک نمایش چندسطحی یک دید کلی‌تر از مدار از نظر SOPهای به هم پیوسته دلخواه، POSهای (حاصلضرب مجموع)، فرم فاکتور شده و غیره است. الگوریتم‌های بهینه‌سازی منطق معمولاً روی نمایش ساختاری (SOPها، فرم فاکتور شده) یا نمایش عملکردی (نمودارهای تصمیم دودویی، نمودارهای تصمیم جبری) مدار کار می‌کنند. در فرم مجموع حاصلضرب (SOP)، دروازه‌های AND کوچک‌ترین واحد را تشکیل می‌دهند و با استفاده از ORها به هم متصل می‌شوند، در حالی که در فرم حاصلضرب مجموع (POS) برعکس است. فرم POS برای گروه‌بندی اصطلاحات OR تحت دروازه‌های AND به پرانتز نیاز دارد، زیرا OR اولویت کمتری نسبت به AND دارد. هر دو فرم SOP و POS به خوبی به منطق مدار ترجمه می‌شوند.

اگر دو تابع F1 و F2 داشته باشیم:

F1=AB+AC+AD

F2=A′B+A′C+A′E

نمایش دو سطحی بالا از شش جمله حاصلضرب و ۲۴ ترانزیستور در پیاده‌سازی CMOS استفاده می‌کند.

یک نمایش چندسطحی معادل از نظر عملکردی می‌تواند باشد:

P = B + C

F1 = AP + AD

F2 = A'P + A'E

با وجود اینکه تعداد سطوح در اینجا ۳ است، اما تعداد کل جملات حاصلضرب و متغیرها به دلیل اشتراک‌گذاری جمله B + C، به‌طور قابل توجهی کاهش می‌یابد.

به‌طور مشابه، بین مدارهای ترکیبی و مدارهای ترتیبی تمایز قائل می‌شویم. مدارهای ترکیبی خروجی خود را تنها بر اساس ورودی‌های فعلی تولید می‌کنند. آنها می‌توانند با روابط بولی نمایش داده شوند. برخی از مثال‌ها عبارتند از کدگذار اولویت‌دار، رمزگشا (کدگشا) دودویی، مالتی‌پلکسر و دمالتی‌پلکسر.

مدارهای ترتیبی خروجی خود را بر اساس ورودی‌های فعلی و گذشته تولید می‌کنند، و برای تشخیص ورودی‌های قبلی از ورودی‌های فعلی به سیگنال ساعت وابسته هستند. آن‌ها می‌توانند با ماشین‌های حالت متناهی نمایش داده شوند. برخی از مثال‌ها عبارتند از فلیپ‌فلاپ‌ها و شمارنده‌ها.

مثال

مدار نمونه اصلی و ساده شده

در حالی که روش‌های بسیاری برای ساده‌سازی یک مدار وجود دارد، این یک مثال ساده‌سازی یک تابع بولی است. تابع بولی که توسط مدار انجام می‌شود، به‌طور مستقیم به عبارت جبری مرتبط است که تابع از آن پیاده‌سازی شده است. به مدار مورد استفاده برای نمایش ('A ∧ B) ∨ (A' ∧ B) توجه کنید. مشخص است که از دو نفی، دو الحاق و یک فصل مشترک در این عبارت استفاده شده است. این بدان معناست که برای ساخت مدار، به دو گیت NOT، دو دروازه AND و یک دروازه OR نیاز داریم.

این مدار را می‌توان با استفاده از قوانین جبر بولی یا با استفاده از شهود ساده کرد (مینیمایز کرد). از آنجایی که مثال بیان می‌کند که A زمانی درست است که B نادرست باشد و برعکس، می‌توان نتیجه گرفت که این به سادگی به معنای A ≠ B است. از نظر دروازه‌های منطقی، نابرابری به سادگی به معنای یک دروازه XOR (یا انحصاری) است؛ بنابراین، ('A ∧ B) ∨ (A' ∧ B) ⟺ A ≠ B. سپس دو مدار نشان داده شده در زیر معادل هستند، همان‌طور که می‌توان با استفاده از جدول درستی بررسی کرد:

B	≠	A		(B	ʌ	'A)	v	('B	ʌ	A)		B	A
ن	ن	ن		ن	ن	د	ن	د	ن	ن		ن	ن
د	د	ن		د	د	د	ن	ن	ن	ن		د	ن
ن	د	د		ن	ن	ن	د	د	د	د		ن	د
د	ن	د		د	ن	ن	د	ن	ن	د		د	د

جستارهای وابسته

• نمودار تصمیم‌گیری دودویی (BDD)
• شرط بی‌تفاوت
• مینی‌ترم اولیه
• پیچیدگی مدار - بر اساس برآورد پیچیدگی مدار
• ترکیب توابع
• تجزیه توابع
• عدم‌استفاده‌کافی از دروازه
• زائدبودن منطقی
• نمودار کمینه‌سازی هاروارد (ویکی‌دانشگاه) (کتاب‌های ویکی)

منابع

1. 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.
2. 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 pages)
3. Theobald, M. ; Nowick, S. M. (نوامبر ۱۹۹۸). "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.
4. Buchfuhrer, David; Umans, Christopher (ژانویه ۲۰۱۱). "The complexity of Boolean formula minimization" (PDF). Journal of Computer and System Sciences (JCSS). 77 (1). Computer Science Department, California Institute of Technology, Pasadena, California, USA: Elsevier Inc.: 142–153. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher (2008). "The Complexity of Boolean Formula Minimization". Proceedings of Automata, Languages and Programming (PDF). Lecture Notes in Computer Science (LNCS). Vol. 5125. Berlin / Heidelberg, Germany: Springer-Verlag. pp. 24–35. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Archived (PDF) from the original on 2018-01-14. Retrieved 2018-01-14. {{cite book}}: Empty citation (help): |work= ignored (help)
5. Haaswijk, Winston. "SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism" (PDF). EPFL. Retrieved 2022-12-07.
6. Haaswijk, Winston. "SAT-Based Exact Synthesis for Multi-Level Logic Networks" (PDF). EPFL. Retrieved 2022-12-07.
7. 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.

برای مطالعهٔ بیشتر

• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Analysis and Design of Sequential Digital Systems. Macmillan Press. ISBN 0-33319266-4. (146 pages)
• De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill. ISBN 0-07-016333-2. (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)
• 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.