Test pattern generation using Boolean proof engines

پس از تولید تراشه، صحت عملکرد مدار مجتمع باید بررسی شود. در غیر این صورت محصولات دارای نقص به مشتریان تحویل داده می شود که برای هیچ شرکتی قابل قبول نیست. الگوریتم های زیادی برای \"تولید الگوی تست خودکار\" (ATPG) در 30 سال گذشته پیشنهاد شده است. اما به دلیل پیچیدگی طراحی روزافزون، تکنیک های جدیدی باید توسعه یابد که بتواند با مدارهای امروزی مقابله کند. در حالی که رویکردهای کلاسیک مبتنی بر عقبگرد در ساختار مدار هستند، چندین رویکرد مبتنی بر "رضایت پذیری بولی" (SAT) از اوایل دهه 80 ارائه شده است.

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

After producing a chip, the functional correctness of the integrated circuit has to be checked. Otherwise products with malfunctions would be delivered to customers, which is not acceptable for any company. Many algorithms for "Automatic Test Pattern Generation" (ATPG) have been proposed in the last 30 years. But due to the ever increasing design complexity, new techniques have to be developed that can cope with today’s circuits. While classical approaches are based on backtracking on the circuit structure, several approaches based on "Boolean Satisfiability" (SAT) have been proposed since the early 80s.

In Test Pattern Generation using Boolean Proof Engines, we give an introduction to ATPG. The basic concept and classical ATPG algorithms are reviewed. Then, the formulation as a SAT problem is considered. As the underlying engine, modern SAT solvers and their use on circuit related problems are comprehensively discussed. Advanced techniques for SAT-based ATPG are introduced and evaluated in the context of an industrial environment. The chapters of the book cover efficient instance generation, encoding of multiple-valued logic, usage of various fault models, and detailed experiments on multi-million gate designs. The book describes the state of the art in the field, highlights research aspects, and shows directions for future work.