Dr. Baruch Zoltan Francisc
Professor


Technical University of Cluj-Napoca
Computer Science Department


 

BARUCH ZOLTAN FRANCISC



 

CONTRIBUTIONS TO THE COMPUTER AIDED
DESIGN OF DIGITAL SYSTEMS



PhD Thesis



Supervisor: Prof. Dr. Eng. Pusztai Kalman


Cluj-Napoca, ROMANIA

1999




 

TABLE OF CONTENTS


1. INTRODUCTION

1.1. DIGITAL SYSTEM DESIGN
1.2. FPGA CIRCUITS
1.3. DESIGN STEPS WITH FPGA CIRCUITS
1.4. THESIS MOTIVATION
1.5. THESIS ORGANIZATION

 
2. ANALYSIS OF CURRENT STATUS IN THE FIELD OF VLSI AND FPGA CIRCUITS

2.1. INTRODUCTION
2.2. VLSI DESIGN PROCESS

 

2.2.1. Architectural Design
2.2.2. Logical Design
2.2.3. Physical Design

2.3. TYPES OF VLSI CIRCUITS

 

2.3.1. Gate Arrays
2.3.2. Standard Cells
2.3.3. Macro-Cells
2.3.4. FPGA Circuits

2.4. TYPES OF FPGA CIRCUITS

 

2.4.1. Xilinx FPGA Circuits
2.4.2. Altera FPGA Circuits
2.4.3. Actel FPGA Circuits
2.4.4. Quicklogic FPGA Circuits

2.5. DIFFICULTIES IN PHYSICAL DESIGN
2.6. CONCLUSIONS

 
3. PARTITIONING FOR CIRCUITS WITH LIMITED ROUTING RESOURCES

3.1. INTRODUCTION
3.2. PARTITIONING PROBLEM DEFINITION
3.3. CONSTRAINTS
3.4. SYNTHETIC PRESENTATION OF PARTITIONING METHODS

 

3.4.1. Kernighan-Lin Algorithm
3.4.2. Variants of Kernighan-Lin Algorithm
3.4.3. Fiduccia-Mattheyses Heuristic
3.4.4. Partitioning by Simulated Annealing
3.4.5. Ratio Cut Partitioning
3.4.6. Partitioning with Stable Performance
3.4.7. Spectral-Based Partitioning
3.4.8. Network Flow Partitioning
3.4.9. Multipartitioning
3.4.10. Probability-Based Partitioning

3.5. PARTITIONING FOR FPGA CIRCUITS

 

3.5.1. Hierarchical Partitioning for Multiple FPGA Circuits
3.5.2. Partitioning for PLA-Based FPGA Circuits

3.6. UNCONVENTIONAL PARTITIONING METHODS

 

3.6.1. Partitioning by Stochastic Evolution

 

3.6.1.1. Bipartitioning by Stochastic Evolution
3.6.1.2. Multipartitioning by Stochastic Evolution

 

3.6.2. Partitioning by Learning Automata

 

3.6.2.1. Learning Automata and Object Partitioning
3.6.2.2. Learning Automata for Graph Partitioning

3.7. PROPOSED PARTITIONING ALGORITHMS FOR FPGA CIRCUITS WITH LIMITED ROUTING RESOURCES

 

3.7.1. Partitioning Algorithm for Balancing the Number of Connections
3.7.2. Genetic Partitioning Algorithm for Balancing the Number of Connections

 

3.7.2.1. Terminology of Genetic Algorithms
3.7.2.2. Principle of Genetic Algorithms
3.7.2.3. Genetic Partitioning Algorithm with Balanced Connections

 

3.7.3. Experimental Results

3.8. CONCLUSIONS

 
4. MODULE PLACEMENT WITH THE OBJECTIVE TO ENSURE CIRCUIT ROUTABILITY

4.1. INTRODUCTION
4.2. PLACEMENT PROBLEM DEFINITION
4.3. COST FUNCTIONS AND CONSTRAINTS

 

4.3.1. Estimation of Wirelength
4.3.2. Minimizing Total Wirelength
4.3.3. Minimizing Maximum Cut
4.3.4. Minimizing Maximum Density
4.3.5. Maximizing Performance

4.4. SYNTHETIC PRESENTATION OF PLACEMENT METHODS

 

4.4.1. Initial Constructive Placement
4.4.2. Min-Cut Placement
4.4.3. Placement by Simulated Annealing

 

4.4.3.1. Applying the Simulated Annealing Algorithm for Placement
4.4.3.2. TimberWolf Algorithm

 

4.4.4. Placement by Hierarchical Partitioning
4.4.5. Placement by Numeric Methods
4.4.6. Linear Placement by Spectral Methods
4.4.7. Other Iterative Methods

 

4.4.7.1. Placement by Quadratic Assignment
4.4.7.2. Placement by Optimizing Resistive Networks
4.4.7.3. Placement by the Steinberg Algorithm
4.4.7.4. Placement by the Graph Space Method
4.4.7.5. Placement by Operations on Lines and Columns

4.5. UNCONVENTIONAL PLACEMENT METHODS

 

4.5.1. Placement by Parallel Algorithms
4.5.2. Placement by Artificial Neural Networks

 

4.5.2.1. Basic Concepts of Artificial Neural Networks
4.5.2.2. Hopfield Neural Networks
4.5.2.3. Using Artificial Neural Networks for Placement

4.6. PROPOSED PLACEMENT ALGORITHMS FOR FPGA CIRCUITS WITH LIMITED ROUTING RESOURCES

 

4.6.1. Min-Cut Based Placement Algorithm

 

4.6.1.1. Description of the Placement Algorithm
4.6.1.2. The Sequence to Apply Slicing Lines

 

4.6.2. Genetic Algorithm for FPGA Placement

 

4.6.2.1. Using Genetic Algorithms for Placement
4.6.2.2. Solution Representation
4.6.2.3. Genetic Operators
4.6.2.4. Population Selection for Next Generation
4.6.2.5. Specific Issues for FPGA Circuits with Limited Routing Resources

 

4.6.3. Experimental Results

4.7. CONCLUSIONS

 
5. ROUTING FOR CIRCUITS WITH LIMITED ROUTING RESOURCES

5.1. INTRODUCTION
5.2. ROUTING PROBLEM DEFINITION
5.3. COST FUNCTIONS AND CONSTRAINTS

 

5.3.1. Cost Functions and Constraints for Global Routing
5.3.2. Cost Functions and Constraints for Detailed Routing

5.4. SYNTHETIC PRESENTATION OF ROUTING METHODS

 

5.4.1. Synthetic Presentation of Global Routing Methods
5.4.2. Synthetic Presentation of Detailed Routing Methods

5.5. GLOBAL ROUTING

 

5.5.1. Routing Regions

 

5.5.1.1. Channel Junction Conversion
5.5.1.2. Channel Ordering
5.5.1.3. Routing Regions Representation

 

5.5.2. Sequential Global Routing

 

5.5.2.1. The Steiner Tree Problem
5.5.2.2. Global Routing by Maze Running
5.5.2.3. Global Routing Using Weighted Steiner Trees
5.5.2.4. Performance-Driven Global Routing

 

5.5.3. Global Routing by Simulated Annealing
5.5.4. Global Routing by Integer Programming

5.6. DETAILED ROUTING

 

5.6.1. General Detailed Routing

 

5.6.1.1. Maze Routing
5.6.1.2. Line Search Routing

 

5.6.2. Channel Routing

 

5.6.2.1. Channel Routing Problem Definition
5.6.2.2. Constraint Graphs
5.6.2.3. Left-Edge Algorithm
5.6.2.4. Yoshimura and Kuh Algorithm
5.6.2.5. Other Channel Routing Methods

5.7. ROUTING FOR FPGA CIRCUITS

 

5.7.1. The FPGA Routing Problem
5.7.2. Routing by Graph Expansion
5.7.3. Routing Based on Multi-Weighted Graphs

 

5.7.3.1. The Iterated 1-Steiner Method
5.7.3.2. Kou, Markowsky, and Berman Method
5.7.3.3. Hybrid Routing Algorithm
5.7.3.4. Simultaneous Optimization of Multiple Objectives

5.8. PROPOSED ALGORITHM FOR ROUTING THE ATMEL 6000 FPGA CIRCUITS

 

5.8.1. Routing Architecture of Atmel 6000 FPGA Circuits
5.8.2. Circuit Modeling as a Graph
5.8.3. Description of the Routing Algorithm

5.9. CONCLUSIONS

 
6. CAD SYSTEM FOR DIGITAL DESIGN USING ATMEL FPGA CIRCUITS

6.1. GENERAL STRUCTURE OF THE CAD SYSTEM
6.2. DESIGN DESCRIPTION
6.3. COMPILING AND OPTIMIZING THE DESCRIPTION
6.4. GENERATING THE INTERNAL REPRESENTATION
6.5. TECHNOLOGY MAPPING
6.6. CELL PLACEMENT
6.7. ROUTING
6.8. CONCLUSIONS

 
7. FINAL CONCLUSIONS

7.1. THESIS SUMMARY
7.2. THESIS CONTRIBUTIONS
7.3. POSSIBLE DEVELOPMENTS


REFERENCES