本书作者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s 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level course on computeraided design, EECS 527: VLSI Layout Algorithms. The course was introduced to educate graduate students and spur doctoral research in thethen burgeoning field of computeraided design (CAD) for integrated circuits (ICs) that propelled the exponential growth of integration density in VLSI chips, as postulated by Moores Law. At that time, there was no suitable textbook on the subject to teach graduate students about the stateoftheart 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planning, 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page 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cells, I divided them into five main categories: (i) the placement by simulated annealing, (ii) the forcedirected placement, (iii) the placement by mincut graph algorithms, (iv) the placement by numerical optimization, and (v) the evolutionbased 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s Law, the chip design phase must be accelerated several folds by harnessing the evolving computing platforms.

In the late 80s, the computing platforms for the VLSI design environment were rapidly transforming from midframe 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frame 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planning 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access LAN causes a severe constraint to run parallel routing algorithms because of their finegranularity 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software codesign for such finegrained parallel algorithms over a polymorphic fabric so that various types of chip routing algorithms can be accelerated, while the placement and floorplanning 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software codesign 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