Timed Boolean Functions: A Unified Formalism for Exact Timing Analysis

تحقیق زمان‌بندی در سیستم‌های VLSI با کارایی بالا در چند سال گذشته با سرعت ثابتی پیشرفت کرده است، در حالی که ابزارها، به‌ویژه مکانیسم‌های نظری، عقب مانده‌اند. بسیاری از تحقیقات زمان‌بندی کنونی به شدت بر نمودارهای زمان‌بندی تکیه می‌کنند، که اگرچه بصری هستند، اما برای تجزیه و تحلیل طرح‌های بزرگ با پارامترهای بسیار ناکافی هستند. علاوه بر این، نمودارهای زمان‌بندی تنها تقریب‌ها و نه راه‌حل‌های دقیق را برای بسیاری از مسائل زمان‌بندی ارائه می‌دهند و در مواردی که ویژگی‌های زمانی یک طرح به طور پیچیده با عملکردهای منطقی طرح در تعامل است، بینش کمی ارائه می‌دهند. این کتاب روشی برای تحقیق زمان‌بندی ارائه می‌کند که تحلیل و طراحی مدارها و سیستم‌ها را در یک حوزه زمانی و منطقی یکپارچه تسهیل می‌کند. در بخش اول، یک فرمالیسم بازنمایی جبری، توابع بولی زمان‌بندی شده (TBF) را معرفی می‌کنیم که اطلاعات منطقی و زمان‌بندی مدارها و سیستم‌های دیجیتال را در یک فرمالیسم واحد ادغام می‌کند. ما همچنین یک فرم متعارف، TBF BDD، برای آنها می‌دهیم، که می‌تواند برای اصلاح کارآمد استفاده شود. در بخش دوم، توابع بولی زمان‌بندی شده را برای سه مسئله در تحقیق زمان‌بندی اعمال می‌کنیم، که برای اولین بار راه‌حل‌های دقیق به دست می‌آید: 1. محاسبه تاخیرهای دقیق مدارهای ترکیبی و حداقل زمان‌های چرخه ماشین‌های حالت محدود، 2. تجزیه و تحلیل و سنتز مدارهای لوله‌کشی موج، یک معماری با سرعت بالا که روابط زمان‌بندی دقیق بین سیگنال‌ها برای عملکرد صحیح ضروری است، 3. تأیید عملکرد مدار و سیستم و پوشش خطاهای تاخیر با آزمایش.

Timing research in high performance VLSI systems has advanced at a steady pace over the last few years, while tools, especially theoretical mechanisms, lag behind. Much present timing research relies heavily on timing diagrams, which, although intuitive, are inadequate for analysis of large designs with many parameters. Further, timing diagrams offer only approximations, not exact solutions, to many timing problems and provide little insight in the cases where temporal properties of a design interact intricately with the design's logical functionalities. This book presents a methodology for timing research which facilitates analy­ sis and design of circuits and systems in a unified temporal and logical domain. In the first part, we introduce an algebraic representation formalism, Timed Boolean Functions (TBF's), which integrates both logical and timing informa­ tion of digital circuits and systems into a single formalism. We also give a canonical form, TBF BDD's, for them, which can be used for efficient ma­ nipulation. In the second part, we apply Timed Boolean Functions to three problems in timing research, for which exact solutions are obtained for the first time: 1. computing the exact delays of combinational circuits and the minimum cycle times of finite state machines, 2. analysis and synthesis of wavepipelining circuits, a high speed architecture for which precise timing relations between signals are essential for correct operations, 3. verification of circuit and system performance and coverage of delay faults by testing.