Hardware Acceleration of EDA Algorithms: Custom ICs, FPGAs and GPUs

شتاب سخت افزاری الگوریتم های EDA: IC های سفارشی، FPGA و GPU

Kanupriya Gulati

Sunil P. Khatri

این کتاب به بررسی شتاب الگوریتم های EDA با استفاده از پلتفرم های سخت افزاری مانند IC های سفارشی، FPGA و GPU می پردازد. الگوریتم های CAD به طور گسترده برای شتاب بالقوه در این سیستم عامل ها مورد مطالعه قرار می گیرند. پوشش شامل بحث در مورد شرایطی است که در آن استفاده از یک پلت فرم بر پلتفرم دیگر ترجیح داده می شود، به عنوان مثال، زمانی که یک مشکل EDA دارای درجه بالایی از موازی سازی داده ها است، معمولاً GPU پلت فرم ترجیحی است، در حالی که وقتی مشکل کنترل بیشتری داشته باشد، یک FPGA ممکن است ترجیح داده شود. نتایج برای شتاب چندین الگوریتم CAD (شبیه‌سازی خطا، تولید جدول خطا، ارزیابی کارت مدل در SPICE، تجزیه و تحلیل زمان‌بندی استاتیکی آماری مونت کارلو، رضایت‌پذیری بولی) ارائه شده‌اند. .

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

به طور خاص، این کتاب:

• دستورالعمل هایی در مورد استفاده از IC های سفارشی، پردازنده های گرافیکی ارائه می دهد. یا FPGA ها هنگام شتاب دادن به یک الگوریتم EDA معین، اعتبار این پیشنهادها را با یک مثال عینی (رضایت بولی) اجرا شده در همه این پلتفرم ها؛
• شتاب چندین EDA محبوب را نشان می دهد. الگوریتم‌های روی پردازنده‌های گرافیکی، با افزایش سرعت تا 800 برابر؛
• به خواننده کمک می‌کند الگوریتم‌هایی را ارائه دهد که ممکن است توسط خواننده برای تعیین بهترین روش برای تسریع EDA خاص خود استفاده شود. الگوریتم؛
• درباره یک رویکرد خودکار برای تولید کد GPU، با توجه به کد تک پردازنده معمولی که مجموعه‌ای از محدودیت‌ها را برآورده می‌کند، بحث می‌کند؛
• به عنوان یک مرجع ارزشمند برای هر کسی که علاقه مند به بررسی پلتفرم های سخت افزاری جایگزین برای تسریع برنامه های مختلف EDA با استفاده از موازی سازی موجود در این پلتفرم ها است، عمل می کند.

Hardware Acceleration of EDA Algorithms: Custom ICs, FPGAs and GPUs

Kanupriya Gulati

Sunil P. Khatri

This book deals with the acceleration of EDA algorithms using hardware platforms such as Custom ICs, FPGAs and GPUs. Widely applied CAD algorithms are studied for potential acceleration on these platforms. Coverage includes discussion of conditions under which it is preferable to use one platform over another, e.g., when an EDA problem has a high degree of data parallelism, the GPU is typically the preferred platform, whereas when the problem has more control, an FPGA may be preferred. Results are presented for the acceleration of several CAD algorithms (fault simulation, fault table generation, model card evaluation in SPICE, Monte Carlo based statistical static timing analysis, Boolean Satisfiability), demonstrating speedups up to 800X compared to single-core implementatinos of these algorithms.

This book serves as a valuable guide on how best to leverage parallelism to accelerate CAD algorithms. It also presents a methodology to automatically extract SIMD parallelism from regular uniprocessor code which satisfies a set of constraints. With this approach, such uniprocessor code can automatically be converted to GPU code, allowing for significant acceleration. This approach is particularly useful since different GPUs have vastly different specifications, making the manual generation of GPU code an unscalable proposition.

In particular, this book:

• Provides guidelines on whether to use Custom ICs, GPUs or FPGAs when accelerating a given EDA algorithm, validating these suggestions with a concrete example (Boolean Satisfiability) implemented on all these platforms;
• Demonstrates the acceleration of several popular EDA algorithms on GPUs, with speedups up to 800X;
• Helps the reader by presenting example algorithms which may be used by the reader to determine how best to accelerate their specific EDA algorithm;
• Discusses an automatic approach to generate GPU code, given regular uniprocessor code which satisfies a set of constraints;
• Serves as a valuable reference for anyone interested in exploring alternative hardware platforms for accelerating various EDA applications by harnessing the parallelism available in these platforms.