Muutke küpsiste eelistusi

Algorithms for VLSI Design Automation [Kõva köide]

(University of Twente, The Netherlands)
  • Formaat: Hardback, 352 pages, kõrgus x laius x paksus: 254x175x24 mm, kaal: 737 g
  • Ilmumisaeg: 09-Nov-1998
  • Kirjastus: John Wiley & Sons Inc
  • ISBN-10: 0471984892
  • ISBN-13: 9780471984894
Teised raamatud teemal:
Algorithms for VLSI Design AutomationSuurem pilt
  • Formaat: Hardback, 352 pages, kõrgus x laius x paksus: 254x175x24 mm, kaal: 737 g
  • Ilmumisaeg: 09-Nov-1998
  • Kirjastus: John Wiley & Sons Inc
  • ISBN-10: 0471984892
  • ISBN-13: 9780471984894
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780471984894.html
Märksõnad:

Modern microprocessors such as Intel's Pentium chip typically contain many millions of transistors. They are known generically as Very Large-Scale Integrated (VLSI) systems, and their sheer scale and complexity has necessitated the development of CAD tools to automate their design. This book focuses on the algorithms which are the building blocks of the design automation software which generates the layout of VLSI circuits. Courses on this area are typically elective courses taken at senior undergrad or graduate level by students of Electrical and Electronic Engineering, and sometimes in Computer Science, or Computer Engineering.



Modern microprocessors such as Intel's Pentium chip typically contain millions of transitors. Known generically as Very Large-Scale Integrated (VLSI) systems, the chips have a scale and complexity that has necessitated the development of CAD tools to automate their design. This book focuses on the algorithms which are the building blocks of the design automation software which generates the layout of VLSI circuits. One of the first books on the subject, this guide covers all stages of design.

Preface xi
I Preliminaries 1(80)
Introduction to Design Methodologies
3(8)
The VLSI Design Problem
3(2)
The Design Domains
5(2)
Design Actions
7(1)
Design Methods and Technologies
8(1)
Bibliographic Notes
9(2)
A Quick Tour of VLSI Design Automation Tools
11(10)
Algorithmic and System Design
11(2)
Structural and Logic Design
13(2)
Transistor-level Design
15(1)
Layout Design
15(2)
Verification Methods
17(1)
Design Management Tools
18(1)
Bibliographic Notes
19(2)
Algorithmic Graph Theory and Computational Complexity
21(20)
Terminology
22(2)
Data Structures for the Representation of Graphs
24(2)
Computational Complexity
26(3)
Examples of Graph Algorithms
29(10)
Depth-first Search
30(2)
Breadth-first Search
32(2)
Dijkstra's Shortest-path Algorithm
34(3)
Prim's Algorithm for Minimum Spanning Trees
37(2)
Bibliographic Notes
39(1)
Exercises
40(1)
Tractable and Intractable Problems
41(12)
Combinatorial Optimization Problems
41(2)
Decision problems
43(2)
Complexity Classes
45(1)
NP-completeness and NP-hardness
46(3)
Consequences
49(1)
Bibliographic Notes
50(1)
Exercises
51(2)
General-purpose Methods for Combinatorial Optimization
53(28)
The Unit-size Placement Problem
54(1)
Backtracking and Branch-and-bound
55(7)
Backtracking
56(3)
Branch-and-bound
59(3)
Dynamic Programming
62(3)
Integer Linear Programming
65(4)
Linear Programming
65(1)
Integer Linear Programming
65(4)
Local Search
69(2)
Simulated Annealing
71(2)
Tabu Search
73(2)
Genetic Algorithms
75(3)
A Few Final Remarks on General-purpose Methods
78(1)
Bibliographic Notes
79(2)
II Selected Design Problems and Algorithms 81(194)
Layout Compaction
83(18)
Design Rules
83(2)
Symbolic Layout
85(1)
Problem Formulation
86(5)
Applications of Compaction
86(1)
Informal Problem Formulation
86(1)
Graph-theoretical Formulation
87(3)
Maximum-distance Constraints
90(1)
Algorithms for Constraint-graph Compaction
91(6)
A Longest-path Algorithm for DAGs
91(1)
The Longest Path in Graphs with Cycles
92(1)
The Liao-Wong Algorithm
93(2)
The Bellman-Ford Algorithm
95(1)
Discussion: Shortest Paths, Longest Paths and Time Complexity
96(1)
Other Issues
97(2)
Bibliographic Notes
99(1)
Exercises
99(2)
Placement and Partitioning
101(18)
Circuit Representation
102(3)
Wire Length Estimation
105(1)
Types of Placment Problem
106(2)
Placement Algorithms
108(4)
Constructive Placement
108(1)
Iterative Improvement
109(3)
Partitioning
112(5)
The Kernighan-Lin Partitioning Algorithm
112(5)
Bibliographic Notes
117(1)
Exercises
118(1)
Floorplanning
119(14)
Floorplanning Concepts
121(4)
Terminology and Floorplan Representation
121(3)
Optimization Problems in Floorplanning
124(1)
Shape Functions and Floorplan Sizing
125(5)
Bibliographic Notes
130(1)
Exercises
131(2)
Routing
133(34)
Types of Local Routing Problems
133(1)
Area Routing
134(4)
Channel Routing
138(12)
Channel Routing Medels
139(1)
The Vertical Constraint Graph
140(3)
Horizontal Contraints and the Left-edge Algorithm
143(3)
Channel Routing Algorithms
146(4)
Introduction to Global Routing
150(4)
Standard-cell layout
151(2)
Building-block Layout and Channel Ordering
153(1)
Algorithms for Global Routing
154(9)
Problem Definition and Discussion
155(2)
Efficient Rectilinear Steiner-tree Construction
157(6)
Local Transformations for Global Routing
163(1)
Bibliographic Notes
163(3)
Exercises
166(1)
Simulation
167(28)
General Remarks on VLSI Simulation
167(2)
Gate-level Modeling and Simulation
169(11)
Signal Modeling
170(1)
Gate Modeling
171(1)
Delay Modeling
171(1)
Connectivity Modeling
172(1)
Compiler-driven Simulation
173(3)
Event-driven Simulation
176(4)
Switch-level Modeling and Simulation
180(11)
Connectivity and Signal Modeling
181(2)
Simulation Mechanisms
183(8)
Bibliographic Notes
191(1)
Exercises
192(3)
Logic Synthesis and Verification
195(40)
Introduction to Combinational Logic Synthesis
195(6)
Basic Issues and Terminology
195(4)
A Practical Example
199(2)
Binary-decision Diagrams
201(21)
ROBDD Principles
201(5)
ROBDD Implementation and Construction
206(2)
ROBDD Manipulation
208(7)
Variable Ordering
215(2)
Applications to Verification
217(2)
Applications to Combinatorial Optimization
219(3)
Two-level Logic Synthesis
222(8)
Problem Definition and Analysis
222(3)
A Heuristic Based on ROBDDs
225(5)
Bibliographic Notes
230(2)
Exercises
232(3)
High-level Synthesis
235(40)
Hardware Models for High-level Synthesis
235(4)
Hardware for Computations, Data Storage, and Interconnection
236(2)
Data, Control, and Clocks
238(1)
Internal representation of the Input Algorithm
239(8)
Simple Data Flow
239(2)
Conditional Data Flow
241(2)
Iterative Data Flow
243(2)
Data-flow Graph Representation
245(2)
Allocation, Assignment and Scheduling
247(6)
Goals and Terminology
247(1)
A detailed Example
248(3)
Optimization Issues
251(2)
Some Scheduling Algorithms
253(8)
ASAP Scheduling
253(1)
Mobility-based Scheduling
254(2)
Force-directed Scheduling
256(3)
List Scheduling
259(2)
Some Aspects of the Assignment Problem
261(5)
Optimization Issues
261(1)
Graph Theoretical problem Formulation
262(2)
Assignment by Interval and Circular-arc Graph Coloring
264(1)
Assignment by Clique Partitioning
265(1)
High-level Transformations
266(5)
Bibliographic Notes
271(2)
Exercises
273(2)
III Appendices 275(22)
Appendix A CMOS Technology
277(10)
A.1 The MOS Transistor and CMOS Logic Design
278(4)
A.2 Transistor Layout in CMOS and Related Issues
282(3)
A.3 Bibliographic Notes
285(2)
Appendix B About and Pseudo-code Notation
287(8)
B.1 Data Structures and Declarations
288(1)
B.2 C-language Constructs
289(3)
B.3 Pseudo-code Constructs
292(2)
B.4 Bibliographic Notes
294(1)
Appendix C List of Acronyms
295(2)
References 297(18)
Index 315


The author, Sabih Gerez, has based the book on a course given to his students at the University of Twente, Enschede, in the Netherlands. As an assistant professor at the Department of Electrical Engineering, he teaches courses on circuit theory and VLSI design. His research focuses on VLSI design automation, especially high-level synthesis. Dr Gerez holds an M.Sc. degree (with honors) in Electrical Engineering and a Ph.D. degree in Applied Sciences, both from the University of Twente.