Dr. Baruch Zoltan Francisc
Profesor

Universitatea Tehnică din Cluj-Napoca
Catedra de Calculatoare


 

BARUCH ZOLTAN FRANCISC



 

CONTRIBUŢII LA PROIECTAREA ASISTATĂ
DE CALCULATOR A SISTEMELOR NUMERICE



Teză de doctorat



Conducător ştiinţific: Prof. dr. ing. Pusztai Kalman


Cluj-Napoca, 1999


 

CUPRINS


1. INTRODUCERE

1.1. PROIECTAREA SISTEMELOR NUMERICE
1.2. CIRCUITE FPGA
1.3. ETAPELE DE PROIECTARE CU CIRCUITE FPGA
1.4. MOTIVAŢIA TEZEI
1.5. ORGANIZAREA TEZEI

 
2. ANALIZA SITUAŢIEI ACTUALE ĪN DOMENIUL CIRCUITELOR
VLSI ŞI FPGA

2.1. INTRODUCERE
2.2. PROCESUL DE PROIECTARE AL CIRCUITELOR VLSI

 

2.2.1. Proiectarea arhitecturală
2.2.2. Proiectarea logică
2.2.3. Proiectarea fizică

2.3. TIPURI DE CIRCUITE VLSI

 

2.3.1. Reţele de porţi
2.3.2. Celule standard
2.3.3. Macro-celule
2.3.4. Circuite FPGA

2.4. TIPURI DE CIRCUITE FPGA

 

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

2.5. DIFICULTĂŢILE PROIECTĂRII FIZICE
2.6. CONCLUZII

 
3. PARTIŢIONAREA PENTRU CIRCUITELE CU RESURSE
LIMITATE DE RUTARE

3.1. INTRODUCERE
3.2. DEFINIREA PROBLEMEI DE PARTIŢIONARE
3.3. RESTRICŢII
3.4. PREZENTAREA SINTETICĂ A METODELOR DE PARTIŢIONARE

 

3.4.1. Algoritmul Kernighan-Lin
3.4.2. Variante ale algoritmului Kernighan-Lin
3.4.3. Euristica Fiduccia-Mattheyses
3.4.4. Partiţionarea prin metoda călirii simulate
3.4.5. Partiţionarea prin tăietura proporţională
3.4.6. Partiţionarea cu performanţe stabile
3.4.7. Partiţionarea prin metode spectrale
3.4.8. Partiţionarea pe baza reţelelor de flux
3.4.9. Multipartiţionarea
3.4.10. Partiţionarea prin metode probabilistice

3.5. PARTIŢIONAREA PENTRU CIRCUITELE FPGA

 

3.5.1. Partiţionarea ierarhică pentru circuite FPGA multiple
3.5.2. Partiţionarea pentru circuite FPGA cu structuri de tip PLA

3.6. METODE NECONVENŢIONALE DE PARTIŢIONARE

 

3.6.1. Partiţionarea prin evoluţie stohastică

 

3.6.1.1. Bipartiţionarea prin evoluţie stohastică
3.6.1.2. Multipartiţionarea prin evoluţie stohastică

 

3.6.2. Partiţionarea prin automate de īnvăţare

 

3.6.2.1. Automate de īnvăţare şi partiţionarea obiectelor
3.6.2.2. Automat de īnvăţare pentru partiţionarea grafurilor

3.7. ALGORITMI DE PARTIŢIONARE PROPUŞI PENTRU CIRCUITE FPGA
CU RESURSE LIMITATE DE RUTARE

 

3.7.1. Algoritm de partiţionare cu echilibrarea numărului de conexiuni
3.7.2. Algoritm genetic pentru partiţionare cu echilibrarea numărului de conexiuni

 

3.7.2.1. Terminologia algoritmilor genetici
3.7.2.2. Principiul algoritmilor genetici
3.7.2.3. Algoritm genetic de partiţionare cu echilibrarea numărului de conexiuni

 

3.7.3. Rezultate experimentale

3.8. CONCLUZII

 
4. PLASAREA MODULELOR CU OBIECTIVUL ASIGURĂRII
RUTABILITĂŢII CIRCUITELOR

4.1. INTRODUCERE
4.2. DEFINIREA PROBLEMEI DE PLASARE
4.3. FUNCŢII DE COST ŞI RESTRICŢII

 

4.3.1. Estimarea lungimii conexiunilor
4.3.2. Minimizarea lungimii totale a conexiunilor
4.3.3. Minimizarea tăieturii maxime
4.3.4. Minimizarea densităţii maxime
4.3.5. Maximizarea performanţelor

4.4. SINTEZA METODELOR DE PLASARE

 

4.4.1. Plasarea constructivă iniţială
4.4.2. Plasarea pe baza tăieturii minime
4.4.3. Plasarea prin metoda călirii simulate

 

4.4.3.1. Aplicarea algoritmului de călire simulată pentru plasare
4.4.3.2. Algoritmul TimberWolf

 

4.4.4. Plasarea prin partiţionare ierarhică
4.4.5. Plasarea prin metode numerice
4.4.6. Plasarea liniară prin metode spectrale
4.4.7. Alte metode iterative

 

4.4.7.1. Plasarea prin asignare cuadratică
4.4.7.2. Plasarea pe baza optimizării reţelelor rezistive
4.4.7.3. Plasarea prin algoritmul Steinberg
4.4.7.4. Plasarea prin metoda spaţiului grafurilor
4.4.7.5. Plasarea bazată pe operaţii cu linii şi coloane

4.5. METODE NECONVENŢIONALE DE PLASARE

 

4.5.1. Plasarea prin algoritmi paraleli
4.5.2. Plasarea prin reţele neuronale artificiale

 

4.5.2.1. Concepte de bază ale reţelelor neuronale artificiale
4.5.2.2. Reţele neuronale Hopfield
4.5.2.3. Utilizarea reţelelor neuronale pentru plasare

4.6. ALGORITMI DE PLASARE PROPUŞI PENTRU CIRCUITELE FPGA
CU RESURSE LIMITATE DE RUTARE

 

4.6.1. Algoritm de plasare pe baza tăieturii minime

 

4.6.1.1. Descrierea algoritmului de plasare
4.6.1.2. Secvenţa de aplicare a liniilor de tăietură

 

4.6.2. Algoritm genetic pentru plasarea circuitelor FPGA

 

4.6.2.1. Utilizarea algoritmilor genetici pentru plasare
4.6.2.2. Reprezentarea soluţiei
4.6.2.3. Operatori genetici
4.6.2.4. Selecţia populaţiei pentru generaţia următoare
4.6.2.5. Aspecte specifice pentru circuitele FPGA cu resurse limitate de rutare

 

4.6.3. Rezultate experimentale

4.7. CONCLUZII

 
5. RUTAREA CIRCUITELOR CU RESURSE LIMITATE
DE RUTARE

5.1. INTRODUCERE
5.2. DEFINIREA PROBLEMEI DE RUTARE
5.3. FUNCŢII DE COST ŞI RESTRICŢII

 

5.3.1. Funcţii de cost şi restricţii pentru rutarea globală
5.3.2. Funcţii de cost şi restricţii pentru rutarea detaliată

5.4. SINTEZA METODELOR DE RUTARE

 

5.4.1. Prezentarea sintetică a metodelor de rutare globală
5.4.2. Prezentarea sintetică a metodelor de rutare detaliată

5.5. RUTAREA GLOBALĂ

 

5.5.1. Regiuni de rutare

 

5.5.1.1. Conversia joncţiunilor canalelor
5.5.1.2. Ordonarea canalelor
5.5.1.3. Reprezentarea regiunilor de rutare

 

5.5.2. Rutarea globală secvenţială

 

5.5.2.1. Problema arborelui Steiner
5.5.2.2. Rutarea globală prin metoda parcurgerii labirintului
5.5.2.3. Rutarea globală utilizānd arbori Steiner ponderaţi
5.5.2.4. Rutarea globală orientată pe performanţe

 

5.5.3. Rutarea globală prin metoda călirii simulate
5.5.4. Rutarea globală prin metoda programării īntregi

5.6. RUTAREA DETALIATĂ

 

5.6.1. Rutarea detaliată generală

 

5.6.1.1. Rutarea labirint
5.6.1.2. Rutarea prin metoda căutării liniilor

 

5.6.2. Rutarea prin canale

 

5.6.2.1. Definirea problemei de rutare prin canale
5.6.2.2. Grafuri de constrāngeri
5.6.2.3. Algoritmul marginii din stānga
5.6.2.4. Algoritmii Yoshimura şi Kuh
5.6.2.5. Alte metode de rutare prin canale

5.7. RUTAREA CIRCUITELOR FPGA

 

5.7.1. Problema de rutare a circuitelor FPGA
5.7.2. Rutarea prin expandarea grafului
5.7.3. Rutarea pe baza grafurilor cu ponderi multiple

 

5.7.3.1. Metoda 1-Steiner iterată
5.7.3.2. Metoda Kou, Markowsky şi Berman
5.7.3.3. Algoritm de rutare hibrid
5.7.3.4. Optimizarea simultană a obiectivelor multiple

5.8. ALGORITM PROPUS PENTRU RUTAREA CIRCUITELOR FPGA ATMEL 6000

 

5.8.1. Arhitectura de rutare a circuitelor FPGA Atmel 6000
5.8.2. Modelarea circuitului printr-un graf
5.8.3. Descrierea algoritmului de rutare

5.9. CONCLUZII

 
6. SISTEM CAD PENTRU PROIECTAREA SISTEMELOR NUMERICE
CU CIRCUITELE FPGA ATMEL

6.1. STRUCTURA GENERALĂ A SISTEMULUI CAD
6.2. DESCRIEREA PROIECTULUI
6.3. COMPILAREA ŞI OPTIMIZAREA DESCRIERILOR
6.4. GENERAREA REPREZENTĂRII INTERNE
6.5. MAPAREA TEHNOLOGICĂ
6.6. PLASAREA CELULELOR
6.7. RUTAREA CIRCUITULUI
6.8. CONCLUZII

 
7. CONCLUZII FINALE

7.1. SUMARUL TEZEI
7.2. CONTRIBUŢIILE TEZEI
7.3. DEZVOLTĂRI POSIBILE


BIBLIOGRAFIE