An Artificial Intelligence Approach to Integrated Circuit Floorplanning

ISBN-13: 9783540539582 / Angielski / Miękka / 1991 / 149 str.

M. A. Jabri; Marwan A. Jabri

Opis

In 1984, while I was following his postgraduate course on VLSI design, my supervisor Dr. David Skellern, asked me if I was interested in investigating intelligent approaches to automatic Ie floorplanning. He told me then: "a circuit that works always looks nice, has a clever data and control flow. A fast way to look at students' Ie projects is by looking at their fioorplans.." Later, I took a course on Knowledge Engineering (KE) and Artificial Intelligence (AI) with Professor John Gero, who encouraged me to investigate this area of design automation. The resources for such development were really poor at IS&E as KE was a relatively new field of research in Australia at that time. 'Vhatever the difficulties (a good programmmer never blames his tools as David Skellern used to tell me), I undertook the investigation of Knowledge-Based approaches to Ie ftoor planning as my PhD thesis subject with the help of my supervisor and John Gero and the encouragement of all researchers at IS&E, who provided an exciting environment for my research. This volume reports the results of my research during 1984, 1985, 1986, and 1987. The voulme deals with Ie ftoorplanning from four perspectives: floorplanning strategy, Knowledge Engineering in the Ie domain, the development of knowledge-based fioorplan ning processes and new floorplanning algorithms for use in the overall strategy."

Spis treści

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.