Functional Decomposition with Applications to FPGA Synthesis

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

During the last few years Field Programmable Gate Arrays (FPGAs) have become increasingly important. Thanks to recent breakthroughs in technology, FPGAs offer millions of system gates at low cost and considerable speed.
Functional decomposition has emerged as an essential technique in automatic logic synthesis for FPGAs. Functional decomposition as a technique to find realizations for Boolean functions was already introduced in the late fifties and early sixties by Ashenhurst, Curtis, Roth and Karp. In recent years, however, it has attracted a great deal of renewed attention, for several reasons. First, it is especially well suited for the synthesis of lookup-table based FPGAs. Also, the increased capacities of today's computers as well as the development of new methods have made the method applicable to larger-scale problems. Modern techniques for functional decomposition profit from the success of Reduced Ordered Binary Decision Diagrams (ROBDDs), data structures that provide compact representations for many Boolean functions occurring in practical applications. We have now seen the development of algorithms for functional decomposition which work directly based on ROBDDs, so that the decomposition algorithm works based on compact representations and not on function tables or decomposition matrices as in previous approaches.
The book presents, in a consistent manner, a comprehensive presentation of a multitude of results stemming from the author's as well as various researchers' work in the field. Apart from the basic method, it also covers functional decomposition for incompletely specified functions, decomposition for multi-output functions and non-disjoint decomposition.
Functional Decomposition with Application to FPGA Synthesis will be of interest both to researchers and advanced students in logic synthesis, VLSI CAD, and Design Automation as well as professionals working in FPGA design and the development of algorithms for FPGA synthesis.