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 McGraw-Hill X A Division o f TheMcGraw•Hill Companies 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 F 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 ofIEEE 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 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 Xi