內容簡介

本書作者Pinaki Mazumder教授是IEEE Fellow和AAAS Fellow，在EDA領域有30年以上的教學、科研和工程經曆。

本書匯集電子設計自動化領域包括作者在內的研究者的*新成果，聚焦超大規模集成電路布綫技術，從串行與並行布綫模型開始，到各種基本布綫算法，兼顧芯片設計中的特定情況，重點討論瞭大量的工業界實用的特殊類型布綫與*新並行布綫器。

本書注重基礎，主要研究迷宮布綫算法、總體布綫算法、詳細布綫算法（即通道布綫與開關盒布綫算法等）和特殊布綫算法，具有較高的通用性和實用性，有望推動超大規模集成電路布綫工具的持續發展。

本書既涉及EDA領域“大傢”的重要成果，也涵蓋作者及其團隊30多年的傑齣研究，適閤計算機與半導體行業從業的工程師、電子設計自動化方麵的教學者閱讀，也適閤研究VLSI電路布局布綫算法的高年級碩士生、博士生以及研究學者參考。

前言/序言

PREFACE

This handbook for routing interconnects inside a VLSI chip provides mathematical models of important classes of wiring techniques for students interested in gaining insights in integrated circuits layout automation techniques and for practicing engineers working in the field of electronic design automation (EDA). This book presents a comprehensive review on VLSI routing techniques that was undertaken in early 1990�餾 with a view to developing a generalized routing accelerator that could speed up routing chores for different styles of wiring techniques, namely, maze routing used widely for connecting different circuit blocks by finding the shortest path, channel routing used in connecting standard cells of uniform heights and variable widths arranged in the form of rows of cells, switchbox routing used in connecting surrounding multiple blocks of dissimilar aspect ratios within an enclosed routing area, and so on.

In 1988, when I started my academic career at the University of Michigan, I designed a new graduate�瞝evel course on computer�瞐ided design, EECS 527: VLSI Layout Algorithms. The course was introduced to educate graduate students and spur doctoral research in the�瞭hen burgeoning field of computer�瞐ided design (CAD) for integrated circuits (ICs) that propelled the exponential growth of integration density in VLSI chips, as postulated by Moore�餾 Law. At that time, there was no suitable textbook on the subject to teach graduate students about the state�瞣f�瞭he�瞐rt layout algorithms that were key to design complex VLSI chips. Therefore, I combed through the literature on the subject and assembled the course materials in order to teach students systematically basic underlying mathematical techniques for circuit partitioning, floor�瞤lanning, cell placement, and routing. Subsequently, I engaged my own doctoral students to expand my lecture materials in the form of comprehensive reviews.

For example, with the assistance of my doctoral student, Dr. K. Shahookar, who studied the Genetic Algorithm (GA) for VLSI cell placement techniques, I coauthored a 78�瞤age review paper, which was published in ACM Computing Surveys in June 1991. After poring over nearly a hundred publications on placement algorithms for standard cells and macro�瞔ells, I divided them into five main categories: (i) the placement by simulated annealing, (ii) the force�瞕irected placement, (iii) the placement by min�瞔ut graph algorithms, (iv) the placement by numerical optimization, and (v) the evolution�瞓ased placement. While the first two types of algorithms owe their origin to physical laws, the third and fourth are analytical techniques, and the fifth class of algorithms is derived from biological phenomena. The taxonomy of placement algorithms was created to study inherent parallelism of the different classes of algorithms. While designing the course, I realized that in order to push the mammoth potential of Moore�餾 Law, the chip design phase must be accelerated several folds by harnessing the evolving computing platforms.

In the late 80�餾, the computing platforms for the VLSI design environment were rapidly transforming from mid�瞗rame computers, namely, Digital Equipment Corporation Vax 11/780, Hewlett Packard HP 3000, and Wang Laboratories Wang VS, to the network of workstations, what is widely known as the NOW. This opportunity in hardware evolution warranted deeper insights into VLSI cell placement and routing (P&R;) techniques so that sequential algorithms that used to run on standalone mid�瞗rame computers could be rendered into parallel CAD algorithms for running efficiently on the NOW platform. Also, emergence of commercial parallel computers such as Intel hypercube and Sequent Computer System shared memory had further pushed the needs for developing parallel P&R; algorithms.

In order to promote the NOW platform for EDA research, I started working with my students to develop imaginative distributed Genetic Algorithms (GAs) for partitioning, placement and floor�瞤lanning techniques needed in VLSI chip layout automation. My research group had at that time developed an EDA tool, named Wolverines for parallel implementation of standard cell placement algorithms on the NOW platform. Since workstations are connected by a local area network (LAN) that often deploys the Ethernet to connect different workstations, communication of packets between two specific workstations generally require considerable time even when the Ethernet did not undergo collision of message packets. Because of the length of a LAN, two workstations located afar may locally sense and infer that the Ethernet is free and may launch packets asynchronously. In case, there is a collision of packets, all the senders must abandon transmission by backing off. Then they wait randomly within the range of time before attempting to transmit the packet. If a sender encounters the collision of packet again, it then waits randomly over a period of time that is twice longer than the previous time period. This exponential backing off protocol used in random�瞐ccess LAN causes a severe constraint to run parallel routing algorithms because of their fine�瞘ranularity of parallelism in contrast with placement algorithms that do not require frequent communications in parallel mode of operation over the NOW.

After realizing the key limitations of such dedicated routing accelerators that could only speed up the maze routing, my student, Dr. V. Ramachandran, who is the coauthor of this book, started looking into the possibility of developing a unified routing fabric that can be utilized to accelerate all sorts of VLSI routing algorithms. In his doctoral work, he proposed a polymorphic architecture that mainly comprises an ensemble of simple processing elements that can be configured into various connection topologies by including a suite of switches in each processing element. The highly parallel single instruction multiple data (SIMD) architecture is generally known as Content Addressable Array Parallel Processor (CAAPP) and has been originally developed for image processing applications. Specifically, Dr. Ramachandran had used the CAAPP software framework to experiment with the virtual polymorphic hardware fabric, on which different types of routing algorithms including maze, channel and switchbox were mapped as reported in Section 5.3 in this book.

My overall vision in EDA was to develop distributed networks of workstations furnished with specialized hardware accelerator board containing the polymorphic chip to accelerate different styles of VLSI routing algorithms, while Genetic Algorithms will speed up the cell placement algorithms. Due to funding constraints, in our research group we could fabricate a tiny proof of concept polymorphic chip as shown below. The purpose of this handbook is not only to introduce different styles of VLSI routing algorithms, but also to exposit the ramifications of hardware�瞫oftware co�瞕esign for such fine�瞘rained parallel algorithms over a polymorphic fabric so that various types of chip routing algorithms can be accelerated, while the placement and floor�瞤lanning algorithms will be speeded up by leveraging the intrinsic parallelism of genetic algorithms. With this vision in mind, I hope that readers will be motivated to advance the frontiers of VLSI chip design through innovating hardware�瞫oftware co�瞕esign methods as espoused in this routing handbook.

Pinaki Mazumder, Professor

Fellow of the IEEE & Fellow of the AAAS

Dept. of Elec. Eng. and Comp. Sci.

University of Michigan, Ann Arbor, USA

July 25, 2017