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

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 Devices

2.4. TYPES OF FPGA DEVICES

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

2.5. DIFFICULTIES IN PHYSICAL DESIGN
2.6. CONCLUSIONS

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 DEVICES

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

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 Automaton

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

3.7. PROPOSED PARTITIONING ALGORITHMS FOR FPGA DEVICES 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.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 DEVICES 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 for Applying 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 Devices with Limited Routing Resources

4.6.3. Experimental Results

4.7. CONCLUSIONS

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 DEVICES

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 DEVICES

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

5.9. CONCLUSIONS

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.1. THESIS SUMMARY
7.2. THESIS CONTRIBUTIONS
7.3. POSSIBLE DEVELOPMENTS