Placement and Routing of Electronic Modules / Edition 1

by Michael Pecht

Overview

This practical guide presents and compares the fundamental theories and techniques of placement and routing and provides important new approaches to solving specific problems.;Focusing on highly reliable methods for good manufacturing capability, Placement and Routing of Electronic Modules: discusses the mathematical basis for placement and routing, including set, combinatorial and graph theories; explicates the definitions, structures and relationships of tree types and gives methods of finding minimum trees; furnishes useful techniques for placing and routing high-density modules; supplies ways to determine the work-space area needed for placement and routing; shows how to estimate the number of layers necessary to complete routing; explains via minimization to reduce work-space area, facilitate manufacture, and reduce the number of layers; demonstrates a variety of search strategies for paths connecting two nodes on a work space with obstacles; and much more. Containing over 300 illustrative examples, figures and tables that clarify concepts and enhance understanding, Placement and Routing of Electronic Modules should be a useful tool for electrical and electronics, mechanical, reliability, process, and manufacturing engineers; computer scientists; applied mathematicians; and graduate-level students in these disciplines.

Product Details

ISBN-13:	9780367402426
Publisher:	Taylor & Francis
Publication date:	09/05/2019
Series:	Electrical and Computer Engineering
Pages:	352
Product dimensions:	6.00(w) x 9.00(h) x (d)

About the Author

Michael Pecht, a Professional Engineer, is Director of the Computer Aided Life Cycle Engineering (CALCE) Electronic Packaging Research Center, University of Maryland at College Park. The author or coauthor of over 200 professional papers and editor of the Handbook of Electronic Package Design (Marcel Dekker, Inc.), he is a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), serves on the board of advisors for the Society of Manufacturing Engineers' Electronics Division, and is a member of the International Electronics Packaging Society, the American Society of Mechanical Engineers, and the Institute for Interconnecting and Packaging Electronic Circuits, among other organizations. He is also the chief editor of the IEEE Transactions on Reliability. Dr. Pecht received the B.S. (1976) degree in acoustics, the M.S. (1978) degree in electrical engineering, and the M.S. (1979) and Ph.D. (1982) degrees in engineering mechanics from the University of Wisconsin - Madison.

Table of Contents

Preface v

Contributors xiii

About the CALCE EPRC xv

Chapter 1 Basic Concepts Guoqing Li Yeun Tsun Wong Michael Pecht 1

1.1 Sets 1

1.1.1 Notation 1

1.1.2 Set definitions 2

1.1.3 Set algebra 3

1.1.4 Boolean algebra 6

1.2 Combinatorial Mathematics 6

1.2.1 Permutations 6

1.2.2 Combinations 8

1.2.3 Rectilinear edges with a specific number of bends 8

1.2.4 The traveling salesman problem 13

1.2.5 The NP theory 16

1.3 Graph Theory 19

1.3.1 Graphs 19

1.3.2 The degree of a vertex 22

1.3.3 Line graphs 22

1.3.4 Paths, cycles and trees 23

1.3.5 The adjacency matrix 26

1.4 References 27

Chapter 2 Characterization and Generation of Trees Yeun Tsun Wong Guoqing Li Michael Pecht 29

2.1 Tree Types 29

2.1.1 Routing length 30

2.1.2 Steiner trees 31

2.1.3 Spanning trees 31

2.1.4 Chain trees 34

2.1.5 Source-sink trees 34

2.1.6 Row-based trees 35

2.1.7 Trees with special edges 36

2.2 Generating Minimum Spanning and Chain Trees 38

2.2.1 Generating a minimum spanning tree 38

2.2.2 Generating a minimum chain tree 44

2.3 Minimum Steiner Tree Approximations 48

2.3.1 An approximation based on MRSTs for three nodes 49

2.3.2 Staircase layouts 51

2.3.3 Nodes lying on a rectangle perimeter 54

2.4 References 57

Chapter 3 Signal Layer Estimation Sudha Balakrishnan Michael Pecht 59

3.1 Factors Affecting Layer Estimation 61

3.2 Density Approach 63

3.2.1 General estimation process 63

3.2.2 Equivalent integrated circuit count method 64

3.2.3 Comments on the density approach 67

3.3 Connectivity Approach 68

3.3.1 Permitted connectivity 71

3.3.2 Demanded connectivity 75

3.3.3 Generic model for layer estimation 91

3.4 References 96

Chapter 4 Placement for Routability Yeun Tsun Wong Michael Pecht Michael D. Osterman Guoqing Li 97

4.1 Cost Functions 98

4.1.1 Routing length computations 99

4.1.2 Correction functions 100

4.1.3 Partitioning pertaining to placement objectives 101

4.2 Constructive Techniques 103

4.2.1 Pair-linking 105

4.2.2 Cluster-development 105

4.2.3 Quadratic assignment 106

4.3 Iterative Techniques 108

4.3.1 Force-directed placement 109

4.3.2 Simulated annealing 112

4.3.3 Min-cut 113

4.4 Approximating Minimum Steiner Trees 116

4.4.1 The iso-distance error graph 117

4.4.2 The connection errors 120

4.4.3 The error index 122

4.4.4 Characteristic IDEGs 125

4.4.5 Approximations with row-based trees 127

4.4.6 Testing and discussion 130

4.5 References 134

Chapter 5 Placement for Reliability and Producibility Michael D. Osterman Michael Pecht 139

5.1 Placement for Temperature-Dependent Reliability 140

5.1.1 Convection-cooling placement 141

5.1.2 Conduction cooling placement 145

5.1.3 Placement on substrates 153

5.2 Placement for Fatigue-dependent Reliability 154

5.3 Placement for Vibration 159

5.3.1 Deformation, stress and vibration 159

5.3.2 Modeling for automatic rearrangement 161

5.3.3 Placement algorithm 165

5.4 Placement for Producibility 168

5.5 Combined Placement 173

5.5.1 Interchange placement 173

5.5.2 Simulated annealing 173

5.5.3 Force-directed placement 174

5.6 References 177

Chapter 6 Detailed Routing Yeun Tsun Wong Michael Pecht Guoqing Li 181

6.1 Maze Searching 183

6.1.1 Lee's router 184

6.1.2 Modified Lee's routers 185

6.1.3 Minimum detour-length searching 192

6.2 Line Searching 197

6.2.1 Mikami-Tabuchi's router 197

6.2.2 Hightower's router 199

6.2.3 The line-expansion router 200

6.3 Gridless Searching 202

6.3.1 Rectangle expansion router 202

6.3.2 Ohtsuki's gridless router 204

6.3.3 Multilayer gridless router 207

6.4 Advanced Search Techniques 209

6.4.1 Maze searching in a costing workspace 210

6.4.2 The gridless minimum detour length router 211

6.4.3 Searching for paths with special requirements 213

6.5 References 216

Chapter 7 Via Minimization Guoqing Li Michael Pecht Yeun Tsun Wong 221

7.1 Introduction 222

7.2 The NP-Completeness of the CVM Problem 223

7.2.1 The general 2-CVM problem 223

7.2.2 Restricted 2-CVM problem 227

7.2.3 The n-CVM problem 233

7.3 The NP-Completeness of the UVM Problem 237

7.3.1 Basic definitions 237

7.3.2 The NP-completeness of the two-layer UVM problem 238

7.4 Algorithms and Implementations 245

7.4.1 Crossing graph and via minimization algorithms 245

7.4.2 A 2-CVM algorithm for topological layouts 251

7.5 References 257

Chapter 8 A Solution for Steiner's Problem Yeun Tsun Wong Michael Pecht 261

8.1 Basic Definitions 262

8.2 Properties of Steiner Points 272

8.3 Cliques 277

8.4 Exchangeable Edge-Sets and Trees 285

8.5 General Solution 294

8.6 Procedures 296

8.7 Example 298

Appendix A Symbols 305

Appendix B Acronyms 309

Appendix C Glossary 311

Index 321

Editorial Reviews

Focusing on highly reliable methods for good manufacturing quality, this practical guide presents and compares the fundamental theories and techniques of placement and routing and provides new approaches to solving specific problems. Eight chapters cover basic concepts, characterization and generation of trees, signal layer estimation, placement for routability, placement for reliability and producibility, detailed routing, via minimization, and a solution for Steiner's problem. Includes a glossary. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews