An introduction to VLSI physical design

AN INTRODUCTION TO VLSI PHYSICAL DESIGN

Computer Engineering

Senior Consulting Editors

Stephen W. Director, Carnegie Mellon University

C. L. Liu, University of Illinois Urbana-Champaign

Bartee: Computer Architecture and Logic Design

Chang and Sze : ULSI Technology

De Micheli : Synthesis and Optimization of Digital Circuits

Feldman and Retter : Computer Architecture: A Designer's Text Based on a Generic RISC

Hamacher, Vranesic, and Zaky: Computer Organization

Hayes: Computer Architecture and Organization

Horvath: Introduction to Microprocessors Using the MC 6809 or the MC 68000

Hwang: Advanced Computer Architecture: Parallelism, Scalability, Programmability

Kohavi: Switching and Finite Automata Theory

Lawrence-Mauch: Real-Time Microcomputer System Design : An Introduction

Levine: Vision in Man and Machine

Navabi : VHDL.• Analysis and Modeling of Digital Systems

Peatman : Design with Microcontrollers

Peatman: Digital Hardware Design

Rosen: Discrete Mathematics and Its Applications

Sandige : Modern Digital Design

Sarrafzadeh and Wong: An Introduction to VLSI Physical Design

Stadler : Analytical Robotics and Mechatronics

Sze : VLSI Technology

Taub: Digital Circuits and Microprocessors

Wear, Pinkert, Wear, and Lane : Computers: An Introduction to Hardware and Software

Design

McGraw-Hill Series in Computer Science

Senior Consulting Editor

C. L. Liu, University of Illinois at Urbana-Champaign

Consulting Editor

Allen B. Tucker, Bowdoin College

Fundamentals of Computing and Programming

Computer Organization and Architecture

Computers in Society/Ethics

Systems and Languages

Theoretical Foundations

Software Engineering and Database

Artificial Intelligence

Networks, Parallel and Distributed Computing

Graphics and Visualization

The MIT Electrical Engineering and Computer Science Series

AN INTRODUCTION TO VLSI

PHYSICAL DESIGN

M. Sarrafzadeh

Northwestern University

C. K. Wong

IBM Thomas J. Watson Research Center and Chinese University of Hong Kong

The McGraw-Hill Companies, Inc .

New York St . Louis San Francisco Auckland Bogota Caracas

Lisbon London Madrid Mexico City Milan Montreal New Delhi

San Juan Singapore Sydney Tokyo Toronto

F

McGraw-Hill

A Division o f TheMcGraw•Hill Companies

X

AN INTRODUCTION TO VLSI PHYSICAL DESIGN

Copyright ©1996 by The McGraw-Hill Companies, Inc. All rights reserved . Printed in the

United States of America . Except as permitted under the United States Copyright Act of

1976, no part of this publication may be reproduced or distributed in any form or by any

means, or stored in a data base or retrieval system, without the prior written permission

of the publisher.

This book is printed on acid-free paper .

123456789DOCDOC909876

ISBN 0-07-057194-5

This book was set in Times Roman by ETP/Harrison .

The editor was Eric M. Munson ;

the production supervisor was Denise L . Puryear .

The design manager was Joseph A . Piliero .

Project supervision was done by ETP/Harrison (Portland, Oregon) .

R.R. Donnelley & Sons Company was printer and binder.

Library of Congress Cataloging-in-Publication Data

Sarrafzadeh, Majid .

An introduction to VLSI physical design / M . Sarrafzadeh and C. K.

Wong.

p .

cm.

Includes index .

ISBN 0-07-057194-5

1 . Integrated circuits-Very large scale integration-Design and

construction-Data processing . 2. Computer-aided design .

I . Wong,

C. K.

II. Title .

TK7874 .75 .527

1996

621 .39'5--dc20 95-47560

ABOUT THE AUTHORS

Majid Sarrafzadeh received his B.S ., M .S ., and Ph .D. in 1982, 1984, and 1987,

respectively, all from the University of Illinois at Urbana-Champaign in the Elec￾trical and Computer Engineering Department .

He joined Northwestern University as an Assistant Professor in 1987. Since

1991 he has been Associate Professor of Electrical Engineering and Computer

Science at Northwestern University . His research interests lie in the area of design

and analysis of algorithms and computational complexity, with emphasis in VLSI .

Dr. Sarrafzadeh is a fellow of IEEE . He received an NSF Engineering Initi￾ation award in 1987, two distinguished paper awards in ICCAD-91, and the best

paper award for physical design in DAC-93 . He has served on the technical pro￾gram committee of various conferences, for example, ICCAD, EDAC and ISCAS .

He has published over 150 papers in the area of design and analysis of algorithms,

is a co-editor of the book Algorithmic Aspects of VLSI Layout, a co-editor-in-chief

of The International Journal of High Speed Electronics, and an associate editor of

IEEE Transactions on Computer-Aided Design, 1993-present .

C. K. Wong received the B .A. degree (First Class Honors) in mathematics

from the University of Hong Kong in 1965, and the M .A. and Ph .D. degrees in

mathematics from Columbia University in 1966 and 1970, respectively . He joined

the IBM T . J . Watson Research Center in 1969 as a Research Staff Member and

was manager of the VLSI Design Algorithms group from 1985 to 1995 . He was

Visiting Associate Professor of Computer Science at the University of Illinois,

Urbana, in 1972-73 and Visiting Professor of Computer Science at Columbia

University in 1978-79 . Currently he is Chair Professor and Chairman of the De￾partment of Computer Science and Engineering at the Chinese University of Hong

Kong on leave from IBM . His research interests include combinatorial algorithms,

such as sorting, searching, and graph algorithms ; computational geometry ; and al￾gorithms arising directly from industrial applications .

vu

Viii AN INTRODUCTION TO VLSI PHYSICAL DESIGN

He holds four U.S . patents and has published close to 200 papers. He is

author of the book Algorithmic Studies in Mass Storage Systems, published by

Computer Science Press, 1983 . He received an Outstanding Invention Award

(1971), an Outstanding Technical Achievement Award (1988), and four Invention

Achievement Awards (1977, 1980, 1983, 1989) from IBM .

Dr. Wong is a Fellow of IEEE and a Fellow of ACM . He was Chair of the

IEEE Computer Society Technical Committee on VLSI from 1990 to 1991 and

editor of IEEE Transactions on Computers from 1982 to 1985 . He is the founding

editor-in-chief of the international journal Algorithmica, and a founding member

of the editorial board of IEEE Transactions on VLSI Systems . He is also on the

editorial boards of the international journals, Networks, Fuzzy Sets and Systems,

and The Journal of Fuzzy Mathematics .

To my mother, to the memory of my father,

and to my wife Marjan

Majid Sarrafzadeh

To Catherine, Henry and Andrew

C. K. Wong

CONTENTS

Xi

Preface xv

1 Introduction 1

1 .1 VLSI Technology 2

1 .2 Layout Rules and Circuit Abstraction 5

1 .3 Cell Generation 7

1 .3 .1 Programmable Logic Arrays 8

1 .3 .2 Transistor Chaining (CMOS Functional Arrays)

9

1 .3 .3 Weinberger Arrays and Gate Matrices 9

1 .4 Layout Environments 11

1 .4 .1 Layout of Standard Cells 12

1 .4 .2 Gate Arrays and Sea-of-Gates 12

1 .4 .3 Field-Programmable Gate Arrays (FPGAs) 14

1 .5 Layout Methodologies 14

1 .6 Packaging 18

1 .7 Computational Complexity 19

1 .8 Algorithmic Paradigms 21

1 .9 Overview of the Book 25

Exercises 25

Computer Exercises 26

2 The Top-Down Approach : Placement 31

2 .1 Partitioning 31

2.1 .1 Approximation of Hypergraphs with Graphs 33

2.1 .2 The Kernighan-Lin Heuristic 34

2.1 .3 The Fiduccia-Mattheyses Heuristic 37

2 .1 .4 Ratio Cut 39

2 .1 .5 Partitioning with Capacity and 1/O Constraints 43

2 .1 .6 Discussion 45

2 .2 Floorplanning 47

2 .2 .1 Rectangular Dual Graph Approach to Floorplanning

50

Xii CONTENTS

2 .2 .2 Hierarchical Approach 54

2 .2 .3 Simulated Annealing 57

2 .2 .4 Floorplan Sizing 60

2 .2 .5 Discussion 67

2 .3 Placement 69

2 .3 .1 Cost Function 70

2 .3 .2 Force-directed Methods 71

2.3 .3 Placement by Simulated Annealing 73

2 .3 .4 Partitioning Placement 74

2 .3 .5 Module Placement Based on Resistive Network 75

2 .3 .6 Regular Placement: Assignment Problem 80

2 .3 .7 Linear Placement 82

2 .3 .8 Discussion 83

Exercises 84

Computer Exercises 86

3 The Top-Down Approach : Routing 91

3 .1

Fundamentals 91

3 .1 .1 Maze Running 91

3 .1 .2 Line Searching 94

3 .1 .3 Steiner Trees 96

3 .2 Global Routing 107

3 .2 .1 Sequential Approaches 110

3 .2 .2 Hierarchical Approaches 112

3 .2 .3 Multicommodity Flow-based Techniques 114

3 .2 .4 Randomized Routing 117

3 .2 .5 One-Step Approach 118

s 3 .2 .6 Integer Linear Programming 119

3 .2 .7 Discussion 120

3 .3

Detailed Routing 121

3 .3 .1 Channel Routing 123

3 .3 .2 Switchbox Routing 133

3 .3 .3 Discussion 138

3 .4 Routing in Field-Programmable Gate Arrays 140

3 .4 .1 Array-based FPGAs 141

3 .4 .2 Row-based FPGAs 145

3 .4 .3 Discussion 149

Exercises 151

Computer Exercises 152

4 Performance Issues in Circuit Layout 155

4.1 Delay Models 155

4 .1 .1 Gate Delay Models 156

4 .1 .2 Models for Interconnect Delay 159

4 .1 .3 Delay in RC Trees 161

4 .2 Timing-Driven Placement 163

4 .2 .1 Zero-Slack Algorithm 163

4 .2 .2 Weight-based Placement 169

4.2 .3 Linear Programming Approach 172

4 .2 .4 Discussion 174

CONTENTS Xlll

4 .3 Timing-Driven Routing 175

4 .3 .1 Delay Minimization 175

4 .3 .2 Clock Skew Problem 180

4 .3 .3 Buffered Clock Trees 184

4.4 Via Minimization 187

4.4 .1 Constrained Via Minimization 187

4.4 .2 Unconstrained Via Minimization 193

4 .4 .3 Other Issues in Via Minimization 195

4 .5 Power Minimization 196

4 .6 Discussion and Other Performance Issues 198

Exercises 201

Computer Exercises 203

5 Single-Layer Routing and Applications 207

5 .1 Planar Subset Problem (PSP) 207

5 .1 .1 General Regions without Holes 208

5 .1 .2 PSP with a Fixed Number of Modules 210

5 .2 Single-Layer Global Routing 212

5 .3 Single-Layer Detailed Routing 215

5 .3 .1 Detailed Routing in Bounded Regions 215

5 .3 .2 Detailed Routing in General Regions 219

5 .4 Wire-Length and Bend Minimization Techniques 222

5 .4 .1 Length Minimization 222

5 .4 .2 Bend Minimization 227

5 .5 Over-the-Cell (OTC) Routing 230

5 .5 .1 Physical Model of OTC Routing 230

5 .5 .2 Basic Steps in OTC Routing 231

5 .6 Multichip Modules (MCMs) 233

5 .6 .1 An Overview of MCM Technology 234

5 .6.2 Requirements on MCM Routers 235

5 .6 .3 Routing Problem Formulation and Algorithms 237

5 .7 Discussion 241

Exercises 242

Computer Exercises 244

6 Cell Generation and Programmable Structures 247

6 .1

Programmable Logic Arrays 248

6 .2 Transistor Chaining 253

6 .3 Weinberger Arrays and Gate Matrix Layout 256

6 .4 Other CMOS Cell Layout Generation Techniques 263

6 .5 CMOS Cell Layout Styles Considering Performance Issues 265

6 .6

Discussion 269

Exercises 269

Computer Exercises 270

7 Compaction 271

7 .1 ID Compaction 272

7 .1 .1 Compression-Ridge Techniques 273

7 .1 .2 Graph-based Techniques 276

7 .1 .3 Wire-Length Minimization 279

Md

AV CONTENTS

7 .1 .4 Compaction with Automatic Jogs

7 .1 .5 Grid Constraints

7 .2 2D Compaction

7 .3 Discussion

Exercises

Computer Exercises

Appendix

A.1 Using DISPLAY

A.2 Examples

A.3 Running display

A.4 Bugs

Bibliography

Index

PREFACE

This book focuses on the VLSI physical design process . A large number of prob￾lems studied here are of a fundamental nature and have applications in many other

scientific and engineering fields . In particular, the basic paradigms studied here

apply to a number of large-scale computationally intensive optimization problems .

This book has evolved from the lecture notes used since 1991 for teaching a

VLSI physical design class at Northwestern University (EECS-C57 : "Design Au￾tomation in VLSI"), taken by both advanced undergraduate students and graduate

students . Students learn about various optimization problems related to physical

design and study the corresponding solution techniques . They also learn the un￾derlying technologies and get a chance to develop computer-aided design (CAD)

tools .

This book assumes that the readers have a basic understanding of computer

data representation and manipulation (i .e ., data structures), computer algorithms,

and computer organization . An introductory course in algorithm design and a first

course in logic design can serve as student prerequisites for a course using this

book.

At Northwestern University, we teach two classes related to physical design .

The first one (EECS-C57) is taken by juniors, seniors, and graduate students . In

that course, this book is followed closely . The second course (EECS-D59) is a

more advanced course, taken by graduate students . (In EECS-D59, interaction

of physical design with higher-level phases such as logic design and behavioral

design is also studied .) Several readings are assigned for that course, typically,

this book, Lengauer [213], and recent papers .

The approach we have taken in writing this book is as follows . We first

introduce commonly used algorithmic paradigms . For each topic we will dis￾cuss several basic approaches and elaborate on the more fundamental ones . Other

techniques will be summarized at the end of the corresponding section or chap￾ter. Some of the algorithms described might be very simple ; however, they are

xv

I

Xvi PREFACE

widely used in industry and form the basis for understanding more advanced tech￾niques . The concepts introduced in earlier chapters and sections are presented in a

less formal manner. Once the reader understands the basic concepts, more formal

(theoretical) issues are introduced in later chapters and sections . This manner of

presentation has worked well in EECS-C57 at Northwestern University.

There are two types of exercises at the end of each chapter . The first type

of exercise involves the design and analysis of algorithms for physical design

problems. The second are computer exercises that can be used in conjunction

with the display environment presented in the Appendix . Such exercises involve

the implementation of the algorithms presented in the text or the implementation

of new algorithms to be designed by students . Some of the computer exercises

are meant to provide a complete understanding of tools development . They start

with a simple model in the earlier chapters and evolve into more sophisticated

(and practical) tools in later chapters .

We are grateful to our colleagues Prof. Wayne Dai (UC-Santa Cruz), Dr .

Fook-Luen Heng (IBM T. J . Watson), Prof. Yoji Kajitani (TIT-Japan), Prof. Steve

Kang (UI-Urbana), Prof . Ernie Kuh (UC-Berkeley), Dr. Jin-Fuw Lee (IBM T . J .

Watson), Prof. Dave Liu (UI-Urbana), Prof. Margaret Marek-Sadowska (UC￾Santa Barbara), and Dr . Gary Yeap (Motorola) for their valuable suggestions on

an early draft of the book . Dr . Jin-Fuw Lee's insightful comments on Chapter 6,

Compaction, have significantly improved the presentation of that chapter .

Collaboration with our colleagues in the past has provided new insights into

the VLSI physical design problem . Among them are Prof. D . T . Lee (Northwestern

University), Prof. Thomas Lengauer (GMD, Germany), and Prof . Franco Preparata

(Brown University) . We are also grateful to former and current CAD students at

Northwestern University, Dr . D. S . Chen, Dr. Charles Chiang, Professor J . D.

Cho, Amir Farrahi, Dr . Y . M. Huang, David Knol, Dr. K. F . Liao, Dr . Weiliang

Lin, Salil Raje, Dr. Richard Sun, and Gustavo Tellez, for their valuable comments

and suggestions . David Knol has helped design the cover of the book .

Majid Sarrafzadeh

C. K. Wong