An Artificial Intelligence Approach to Integrated Circuit Floorplanning (Lecture Notes in Engineering)

This book presents an artificial intelligence approach to top-down floor planning of integrated circuits (IC). The approach divides the floor planning process into separate knowledge-based and algorithmic tasks. This enables the use of IC specialised knowle

1 Overview.- 1.1 Introduction.- 1.2 Full Custom Design Approach.- 1.3 Structured Design.- 1.3.1 Separated Hierarchies.- 1.3.2 Interconnections and River Routing.- 1.3.3 Top-Down Approach.- 1.4 The Problem.- 1.5 This Volume.- 2 Integrated Circuit Floorplanning.- 2.1 Introduction.- 2.2 Top-Down Design Process.- 2.2.1 Process Description.- 2.2.2 Backtracking and Design Iteration.- 2.2.3 Top-Down Design Automation.- 2.3 Bottom-Up Design Process.- 2.3.1 Process Description.- 2.3.2 Bottom-Up Design Automation.- 2.4 Limitations of Algorithmic Floorplanning Approaches: Domain Knowledge.- 2.4.1 Noil-Algorithmic Floorplanning Tasks.- 2.4.2 Complexity Management.- 2.4.3 Pruning the Solution Space.- 2.4.4 Propagating “Bottom-up” Constraints.- 2.5 Knowledge-Based Space-Planning.- 2.5.1 Similarities between Building and Chip Floorplanning.- 2.5.2 AI in Automatic Space-Allocation.- 2.5.3 Differences Between Architectural and IC Floorplanning.- 2.6 Limitations of a Purely KBS Approach.- 2.6.1 Algorithms and State Resolution.- 2.6.2 Knowledge Engineering Complexity.- 2.6.3 Computational Constraints.- 2.7 Discussion & Conclusion.- 3 PIAF: A Combined KBS/Algorithmic Floorplanning System.- 3.1 Introduction.- 3.2 The Combined KBS/Algorithmic Approach.- 3.3 The Floorplanning Strategy.- 3.3.1 Floorplanning Process Interfaces.- 3.3.2 Process Overview.- 3.4 The Communication Solving Process.- 3.4.1 Domain Knowledge in Communication Solving.- 3.5 Generation of Rectangular Topologies.- 3.6 Solution Selection.- 3.6.1 Domain Knowledge in Solution Marking.- 3.7 Communication Border Estimation.- 3.8 Block Dimension Calculation.- 3.9 Estimating Block Area Adjustment.- 3.10 Satisfying Block Area and Routing Adjustments.- 3.11 Prototype System Design.- 3.11.1 Design Considerations.- 3.11.2 The PIAF Modular Architecture.- 3.12 Conclusion.- 4 Implementation and Operation with a Case Study.- 4.1 Introduction.- 4.2 Design Issues for PIF.- 4.2.1 Multiple Representation Schemes.- 4.2.2 Context Adjustment.- 4.3 The Structure and Implementation of PIF.- 4.3.1 The Expertise of the Knowledge Engineer.- 4.3.2 Selecting a KBS Programming Language.- 4.3.3 Quality Factors.- 4.3.4 Knowledge Representation.- 4.3.5 The Inference Engine.- 4.3.6 Current Context Memory Structure.- 4.3.7 User Interface.- 4.3.8 Explanation System.- 4.4 The Input to PIAF.- 4.4.1 FBDs as Text Files.- 4.4.2 The FBD Graphic Editor.- 4.5 KBS Task Implementation.- 4.5.1 Communication Solving in PIF.- 4.5.2 Implementation of the Rectangular Solution Selection Process.- 4.5.3 Investigation of Minimal Block Dimensions.- 4.5.4 Final Area and Adjustment Tuning.- 4.6 Conclusion.- 4.7 Conclusion.- 5 The Algorithm Library.- 5.1 Introduction.- 5.2 Graph Clustering Algorithm.- 5.3 An Algorithm for Building RACGs..- 5.3.1 The Algorithm’s Input.- 5.3.2 Exterior Representation.- 5.3.3 The Algorithm.- 5.3.4 Algorithm Evaluation.- 5.3.5 Run Time Examples.- 5.4 Rectangular Dualisation of Graphs.- 5.5 Algorithms for Topological Information Extraction.- 5.5.1 Algorithm for Slice Generation.- 5.5.2 Finding the Surrounds.- 5.6 Optimisation.- 5.6.1 Determination of Block Dimensions.- 5.6.2 Satisfying Area Constraints.- 5.6.3 Satisfying Aspect-Ratio Constraints.- 5.7 Interface to Chip Assembly Tools.- 5.7.1 Join/Join-Top Composition Generation.- 5.7.2 Checking for Pinwheels.- 5.8 Interface to the KBS.- 5.9 Conclusion.- 6 Conclusion.- 6.1 Introduction.- 6.2 Overview of Achievements.- 6.2.1 The Combined Approach to IC Floorplanning.- 6.2.2 PIAF Prototype.- 6.3 Direction for Future Work.- 6.3.1 A Critical Review.- 6.3.2 Important Tasks.- 6.4 Conclusion.- A Primer on Graphs.- A.1 Introduction.- A.2 Undirected Graphs.- A.3 Palm Tree, Tree Arcs and Fronds.- A.4 Paths.- A.5 Faces.- A.6 Connectivity.- A.7 Biconnectivity, Articulation Points.- A.8 Planarity.- A.9 Short-Cuts, Corner Implying Paths, Block Neighbourhood Graphs.- A.10 Rectangular Duals of a Graph.- B An FBD Example.- C Rule Examples.- C.1 Some RACG Building Rules.- C.2 Some Rectangular Topology Selection Rules.- C.3 Examples of a Communication Border Evaluation Rule.