SWARM: A Novel Methodology for Integrated Circuit Layout Automation Based on Principles of Self-organization

Produktbeschreibung

After more than three decades of electronic design automation, most layouts for analog integrated circuits are still handcrafted in a laborious manual fashion today. This book presents Self-organized Wiring and Arrangement of Responsive Modules (SWARM), a novel interdisciplinary methodology addressing the design problem with a decentralized multi-agent system. Its basic approach, similar to the roundup of a sheep herd, is to let autonomous layout modules interact with each other inside a successively tightened layout zone. Considering various principles of self-organization, remarkable overall solutions can result from the individual, local, selfish actions of the modules. Displaying this fascinating phenomenon of emergence, examples demonstrate SWARM’s suitability for floorplanning purposes and its application to practical place-and-route problems. From an academic point of view, SWARM combines the strengths of procedural generators with the assets of optimization algorithms, thus paving the way for a new automation paradigm called bottom-up meets top-down.

Contents
The Methodology 1
1 Clarification of the Task 1
1.1 Technical Aim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Scientific Challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Practical Ambition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 An Interdisciplinary Approach – Preliminary Considerations 4
2.1 Divide and Conquer – Distribute and Conquer . . . . . . . . . . . . . . . . . . 4
2.2 Decentralization, Self-organization, Emergence . . . . . . . . . . . . . . . . . 5
2.3 Emergence: A Natural Phenomenon . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Forms of Emergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.2 Emergence in Biology . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.3 Emergence in Physics . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.4 Emergence in Mathematics . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Principles of Self-organization . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 The Basic Constituents of Self-organization . . . . . . . . . . . . . . . 13
2.4.2 Operational Closure and Structural Coupling . . . . . . . . . . . . . . 15
2.4.3 The Edge of Chaos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.4 Recursivity and Feedback . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.5 Stigmergic Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.6 Reducing Friction and Promoting Synergy . . . . . . . . . . . . . . . . 17
2.4.7 The Virtue of Selfishness . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.8 Law of Requisite Variety . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Models of Decentralized Systems: A Form of Artificial Life . . . . . . . . . . 20
2.5.1 Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.2 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.3 Multi-Agent Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5.4 Agent-based Models of Collective Motion . . . . . . . . . . . . . . . . 26
2.6 Adaptation to the Problem of Analog Layout Design . . . . . . . . . . . . . . 27

3 The Methodology: Self-organized Wiring and Arrangement of Responsive Modules
29
3.1 Overview of the SWARM Methodology . . . . . . . . . . . . . . . . . . . . . 30
3.1.1 The Three Core Concepts of SWARM . . . . . . . . . . . . . . . . . . 30
3.1.2 Depiction of SWARM’s Self-organization Flow . . . . . . . . . . . . . 31
3.2 Responsive Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Context Awareness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2 Governing Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2.1 Temporary Context Duplication . . . . . . . . . . . . . . . . 36
3.2.2.2 Co-transformations in a Governing Module . . . . . . . . . . 39
3.2.3 Module Associations . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.3.1 Supreme Commanders . . . . . . . . . . . . . . . . . . . . . 41
3.2.3.2 Hierarchical Module Associations . . . . . . . . . . . . . . 42
3.2.3.3 Co-transformations in a Module Association . . . . . . . . . 43
3.2.3.4 Coordinate System Issues . . . . . . . . . . . . . . . . . . . 46
3.2.4 Layout Variability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.4.1 Intrinsic Variability . . . . . . . . . . . . . . . . . . . . . . 50
3.2.4.2 Cumulative Variability . . . . . . . . . . . . . . . . . . . . . 51
3.2.4.3 Variability of Primitive Devices . . . . . . . . . . . . . . . . 52
3.2.4.4 Variability of Simple Modules . . . . . . . . . . . . . . . . . 53
3.3 Module Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3.1 Assessment of the Participant’s Condition . . . . . . . . . . . . . . . . 58
3.3.1.1 Interference . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.1.2 Turmoil . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3.1.3 Protrusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3.1.4 Wounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.1.5 Noncompliance . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3.2 Perception of the Free Peripheral Space . . . . . . . . . . . . . . . . . 75
3.3.2.1 Geometrical Recipe for Perceiving the Free Peripheral Space 76
3.3.2.2 Pervasion (Obstacles in the Free Peripheral Space) . . . . . . 77
3.3.3 Exploration and Evaluation of Possible Actions . . . . . . . . . . . . . 79
3.3.3.1 Native Actions . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3.3.2 Custom Actions . . . . . . . . . . . . . . . . . . . . . . . . 94
3.3.3.3 Full Variability . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.3.4 Execution of the Preferred Action . . . . . . . . . . . . . . . . . . . . 98
3.3.4.1 Action Preference . . . . . . . . . . . . . . . . . . . . . . . 98
3.3.4.2 Action Execution . . . . . . . . . . . . . . . . . . . . . . . 104
3.4 Interaction Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.4.1 Scaling the Layout Zone . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.4.1.1 Setting and Enlarging the Layout Zone . . . . . . . . . . . . 111
3.4.1.2 Tightening the Layout Zone . . . . . . . . . . . . . . . . . . 116
3.4.1.3 Considering Rectilinear Layout Zones . . . . . . . . . . . . 120
3.4.2 Transient Tightening Policies . . . . . . . . . . . . . . . . . . . . . . 126
3.4.2.1 Progressive Tightening . . . . . . . . . . . . . . . . . . . . 127
3.4.2.2 Regressive Tightening . . . . . . . . . . . . . . . . . . . . . 134
3.4.3 Comfort Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
3.4.3.1 Solid Comfort Padding . . . . . . . . . . . . . . . . . . . . 146
3.4.3.2 Volatile Comfort Padding . . . . . . . . . . . . . . . . . . . 147
3.5 Final Remarks About the Conception of SWARM . . . . . . . . . . . . . . . . 152
3.5.1 Comparison with Optimization Algorithms . . . . . . . . . . . . . . . 152
3.5.2 Comparison with Decentralized Systems . . . . . . . . . . . . . . . . 158
The Implementation 166
4 Implementation and Results 166
4.1 Examples of Emergence in SWARM . . . . . . . . . . . . . . . . . . . . . . . 166
4.1.1 Example of an Emerging Collective Motion . . . . . . . . . . . . . . . 167
4.1.2 Examples of an Emerging Optimal Layout Outcome . . . . . . . . . . 168
4.1.3 Examples of Nonterminating Interaction Cycles . . . . . . . . . . . . . 178
4.2 Practical Floorplanning Examples . . . . . . . . . . . . . . . . . . . . . . . . 183
4.2.1 Floorplanning Example with Rectangular Outline . . . . . . . . . . . . 183
4.2.2 Floorplanning Example with Nonrectangular Outline . . . . . . . . . . 185
4.2.3 Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.3 Practical Place-and-Route Examples . . . . . . . . . . . . . . . . . . . . . . . 187
4.3.1 Usage of SWARM in the Design Flow . . . . . . . . . . . . . . . . . . 187
4.3.2 Symmetric P-Input Operational Transconductance Amplifier . . . . . . 190
4.3.3 Folded Cascode P-Input Operational Transconductance Amplifier . . . 198
4.3.4 Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.3.4.1 Assessment Regarding Layout Quality . . . . . . . . . . . . 203
4.3.4.2 Assessment Regarding Design Productivity . . . . . . . . . . 208
5 Towards a Holistic Design Flow on Module Level 214
5.1 Cognate Topics Across the Three Different Design Domains . . . . . . . . . . 214
5.1.1 Works Concerning the Physical Domain . . . . . . . . . . . . . . . . . 216
5.1.2 Works Concerning the Structural Domain . . . . . . . . . . . . . . . . 216
5.1.3 Works Concerning the Behavioral Domain . . . . . . . . . . . . . . . 217

5.2 The Scientific Value of SWARM: Meeting Bottom-up With Top-down . . . . . 217
6 Summary and Outlook 220
Listings 225
Vocabulary 225
Mathematical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
Geometrical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
References 231
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Further Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

Keywords: Integrated Circuits, Analog Layout, Floorplanning, Placement, Routing, Constraints, Electronic Design Automation, Optimization Algorithms, Procedural Generators, Multi-Agent Systems, Integrated Circuits, Analog Layout, Floorplanning, Placement, Routing, Constraints, Electronic Design Automation, Optimization Algorithms, Procedural Generators, Multi-Agent Systems