Leaf Cell and Hierarchical Compaction Techniques

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

Leaf Cell and Hierarchical Compaction Techniques presents novel algorithms developed for the compaction of large layouts. These algorithms have been implemented as part of a system that has been used on many industrial designs.
The focus of Leaf Cell and Hierarchical Compaction Techniques is three-fold. First, new ideas for compaction of leaf cells are presented. These cells can range from small transistor-level layouts to very large layouts generated by automatic Place and Route tools. Second, new approaches for hierarchical pitchmatching compaction are described and the concept of a Minimum Design is introduced. The system for hierarchical compaction is built on top of the leaf cell compaction engine and uses the algorithms implemented for leaf cell compaction in a modular fashion. Third, a new representation for designs called Virtual Interface, which allows for efficient topological specification and representation of hierarchical layouts, is outlined. The Virtual Interface representation binds all of the algorithms and their implementations for leaf and hierarchical compaction into an intuitive and easy-to-use system.
From the Foreword:
`...In this book, the authors provide a comprehensive approach to compaction based on carefully conceived abstractions. They describe the design of algorithms that provide true hierarchical compaction based on linear programming, but cut down the complexity of the computations through introduction of innovative representations that capture the provably minimum amount of required information needed for correct compaction. In most compaction algorithms, the complexity goes up with the number of design objects, but in this approach, complexity is due to the irregularity of the design, and hence is often tractable for most designs which incorporate substantial regularity.
Here the reader will find an elegant treatment of the many challenges of compaction, and a clear conceptual focus that provides a unified approach to all aspects of the compaction task...'
Jonathan Allen, Massachusetts Institute of Technology