第1页 / 共591页
第2页 / 共591页
第3页 / 共591页
第4页 / 共591页
第5页 / 共591页
第6页 / 共591页
第7页 / 共591页
第8页 / 共591页
Algorithms for VLSI Physical Design Automation.pdf
Front-cover
Front-matter
Contents
Foreword
Preface
Acknowledgments
Acknowledgments for the Second Edition
Acknowledgments for the Third Edition
Chapter 1 VLSI Physical Design Automation
Chapter 2 Design and Fabrication of VLSI Devices
Chapter 3 Fabrication Process and its Impact on Physical Design
Chapter 4 Data Structures and Basic Algorithms
Chapter 5 Partitioning
Chapter 6 Floorplanning and Pin Assignment
Chapter 7 Placement
Chapter 8 Global Routing
Chapter 9 Detailed Routing
Chapter 10 Over-the-Cell Routing and Via Minimization
Chapter 11 Clock and Power Routing
Chapter 12 Compaction
Chapter 13 Physical Design Automation of FPGAs
Chapter 14 Physical Design Automation of MCMs
Bibliography
Author Index
Subject Index
ALGORITHMS FOR VLSI
PHYSICAL DESIGN AUTOMATION
THIRD EDITION
ALGORITHMS FOR VLSI
PHYSICAL DESIGN AUTOMATION
THIRD EDITION
Naveed A. Sherwani
Intel Corporation.
KLUWER ACADEMIC PUBLISHERS
NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: 0-306-47509-X
0-7923-8393-1
Print ISBN:
©2002 Kluwer Academic Publishers
New York, Boston, Dordrecht, London, Moscow
Print ©1999 Kluwer Academic Publishers
Dordrecht
All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,
mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Visit Kluwer Online at:
and Kluwer's eBookstore at:
http://kluweronline.com
http://ebooks.kluweronline.com
To my parents
Akhter and Akram Sherwani
Contents
Foreword
Preface
Acknowledgements
1 VLSI Physical Design Automation
1.1
1.2
1.3
1.4
1.5
VLSI Design Cycle
New Trends in VLSI Design Cycle
Physical Design Cycle
New Trends in Physical Design Cycle
Design Styles
1.5.1
1.5.2
1.5.3
1.5.4
1.5.5
1.5.6
Full-Custom
Standard Cell
Gate Arrays
Field Programmable Gate Arrays
Sea of Gates
Comparison of Different Design Styles
1.6 System Packaging Styles
1.6.1 Die Packaging and Attachment Styles
Die Package Styles
Package and Die Attachment Styles
1.6.1.1
1.6.1.2
Printed Circuit Boards
Multichip Modules
Wafer Scale Integration
Comparison of Different Packaging Styles
1.6.2
1.6.3
1.6.4
1.6.5
Historical Perspectives
Existing Design Tools
Summary
1.7
1.8
1.9
2 Design and Fabrication of VLSI Devices
2.1
2.2
Fabrication Materials
Transistor Fundamentals
2.2.1
2.2.2
Basic Semiconductor Junction
TTL Transistors
xvii
xix
xxvii
1
3
7
9
13
15
17
18
20
22
25
25
26
26
26
27
27
29
31
31
32
33
35
39
40
43
43
45
viii
Contents
2.2.3 MOS Transistors
2.3 Fabrication of VLSI Circuits
nMOS Fabrication Process
CMOS Fabrication Process
Details of Fabrication Processes
2.4
2.5
2.3.1
2.3.2
2.3.3
Design Rules
Layout of Basic Devices
2.5.1
2.5.2
2.5.3
Inverters
NAND and NOR Gates
Memory Cells
2.5.3.1
2.5.3.2
Static Random Access Memory (SRAM)
Dynamic Random Access Memory (DRAM)
2.6
2.7
Summary
Exercises
3 Fabrication Process and its Impact on Physical Design
3.1
3.2
Scaling Methods
Status of Fabrication Process
3.2.1 Comparison of Fabrication Processes
3.3 Issues related to the Fabrication Process
3.3.1
3.3.2
3.3.3
3.3.4
3.3.5
3.3.6
3.3.7
Parasitic Effects
Interconnect Delay
Noise and Crosstalk
Interconnect Size and Complexity
Other Issues in Interconnect
Power Dissipation
Yield and Fabrication Costs
3.4 Future of Fabrication Process
3.4.1
3.4.2
3.4.3
3.4.4
3.4.5
3.4.6
More Layers of Metal
Local Interconnect
Copper Interconnect
Unlanded Vias
SIA Roadmap
Advances in Lithography
Innovations in Interconnect
3.4.3.1
3.4.3.2
3.4.3.3
3.4.3.4
Innovations/Issues in Devices
Aggressive Projections for the Process
Other Process Innovations
3.4.6.1
3.4.6.2
Silicon On Insulator
Silicon Germaniun
3.5
3.6
3.7
3.8
Solutions for Interconnect Issues
Tools for Process Development
Summary
Exercises
46
48
51
53
53
58
62
62
64
66
67
69
71
71
75
76
77
77
79
79
80
81
82
82
82
83
85
85
86
87
87
87
87
88
88
89
90
90
90
91
93
94
94
Contents
4 Data Structures and Basic Algorithms
4.1
4.2
Basic Terminology
Complexity Issues and NP-hardness
4.2.1 Algorithms for NP-hard Problems
Exponential Algorithms
Special Case Algorithms
Approximation Algorithms
Heuristic Algorithms
4.2.1.1
4.2.1.2
4.2.1.3
4.2.1.4
4.3 Basic Algorithms
4.3.1 Graph Algorithms
4.3.1.1
4.3.1.2
4.3.1.3
4.3.1.4
4.3.1.5
4.3.1.6
Graph Search Algorithms
Spanning Tree Algorithms
Shortest Path Algorithms
Matching Algorithms
Min-Cut and Max-Cut Algorithms
Steiner Tree Algorithms
4.3.2 Computational Geometry Algorithms
4.3.2.1
4.3.2.2
Line Sweep Method
Extended Line Sweep Method
4.4 Basic Data Structures
4.4.1
4.4.2
4.4.3
4.4.4
4.4.5
4.4.6
4.4.7
4.4.8
Atomic Operations for Layout Editors
Linked List of Blocks
Bin-Based Method
Neighbor Pointers
Corner Stitching
Multi-layer Operations
Limitations of Existing Data Structures
Layout Specification Languages
4.5 Graph Algorithms for Physical design
4.5.1 Classes of Graphs in Physical Design
4.5.2
4.5.3
4.5.4
Graphs Related to a Set of Lines
Graphs Related to Set of Rectangles
4.5.1.1
4.5.1.2
Relationship Between Graph Classes
Graph Problems in Physical Design
Algorithms for Interval Graphs
4.5.4.1
4.5.4.2
Maximum Independent Set
Maximum Clique and Minimum Coloring
4.5.5 Algorithms for Permutation Graphs
Maximum Independent Set
Maximum -Independent Set
4.5.5.1
4.5.5.2
4.5.6 Algorithms for Circle Graphs
4.5.6.1
4.5.6.2
4.5.6.3
Maximum Independent Set
Maximum -Independent Set
Maximum Clique
4.6
4.7
Summary
Exercises
ix
97
99
100
101
102
102
102
103
104
104
104
106
108
110
110
111
115
115
115
117
117
119
120
122
123
130
131
131
135
135
136
138
138
140
142
142
143
144
144
146
148
148
149
151
151
152
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
