ΗΥ-590.24: "Aλγόριθμοι Ηλεκτρονικού Αυτοματισμού"


Εαρινό Εξάμηνο - Ακαδημαϊκό Έτος 2008-2009
Χρήστος Σωτηρίου

Προαπαιτούμενα Μαθήματα: ΗΥ-220, HY-225
Θεματική Περιοχή: Α, Z
Διδακτικές Μονάδες: 4

Περιγραφή Μαθήματος:

Εμβάθυνση στους αλγορίθμους και εσωτερικές διεργασίες των ηλεκτρονικά αυτοματοποιημένων διαδικασιών σχεδίασης. Περιγραφή των θεμελιωδών αλγορίθμων και τεχνικών που υλοποιούνται στα σημερινά εργαλεία σχεδίασης ολοκληρωμένων κυκλωμάτων. Περιγραφή σχεδιαστικών διαδικασιών: γλώσσες υλικού, ιστορική αναδρομή στη σχεδίαση κυκλωμάτων, υπολογιστικά θέματα στην φυσική σχεδίαση, γεωμετρική αναπαράσταση, σχεδίαση με κύτταρα. Χρονική ανάλυση και βελτιστοποίηση: τοπολογική ανάλυση, ψευδείς οδοί, προσέγγιση καθυστέρησης πυλών και συνδέσεων, στατιστικά χαρακτηριστικά αγωγών. Διασύνδεση και σύμπτυξη: επίπεδα, συνδέσεις, μονοδιάστατοι και διδιάστατοι αλγόριθμοι, καθολική καί επιμέρους διασύνδεση, διασύνδεση καναλιών. Χωροθέτηση, Σχεδίαση Κάτοψης: αναλυτικοί και βασισμένοι στην επιμέρους διαίρεση αλγόριθμοι, μέτρα ποιότητας και περιορισμοί. Βελτιστοποίηση Συνδυαστικών κυκλωμάτων: PLAs, συνδυαστική λογική 2 επιπέδων, ταυτολογίες, espresso, ψηφιακά δίκτυα Boole πολλαπλών επιπέδων, αλγεβρική παραγοντοποίηση και παραγοντοποίηση Boole, κάλυψη κύβων. Τεχνολογική Αντιστοίχιση: τεχνολογική αντιστοίχιση και βελτιστοποιήση, βελτιστοποιήσεις ανεξάρτητες τεχνολογίας. Σχεδίαση Ακολουθιακών Κυκλωμάτων: κωδικοποίηση καταστάσεων, αναχρονισμός, χρόνοι άφιξης/αναχώρησης, μανταλωτές και flip-flops. Επαλήθευση: προσομοίωση καί εξομοίωση, δυαδικά διαγράμματα αποφάσεων (ΔΔΑ/BDD), έλεγχοι ισότητας. Κατασκευαστική Δοκιμή: διάγνωση λαθών, παρατηρησιμότητα, παραγωγή ανυσμάτων δοκιμών, εσωτερική σάρωση, λάθη που παράγουν καθυστέρηση. Φαινόμενα τεχνολογιών << 1μm, Διαφορές και χάσμα μεταξύ αυτοματοποιημένων διαδικασιών και χειροκίνητων τρόπων σχεδίασης κυκλωμάτων.

Διαλέξεις:

Οι τακτικές διαλέξεις του μαθήματος θα γίνονται κάθε Δευτέρα καί Τετάρτη:

Δευτέρα: 13:00-15:00, Λ206 - Κτήρια Κνωσσού
Πέμπτη: 13:00-15:00, ΡΑ203 - Κτήρια Κνωσσού

Την εβδομάδα 9/2-13/2 δέν θα γίνουν μαθήματα λόγω απουσίας του διδάσκοντα.

Προτεινόμενα Βιβλία:

  1. Logic Synthesis and Verification Algorithms, Gary D. Hachtel and Fabio Somenzi, Kluwer Academic, 1996.

  2. Synthesis of Optimization of Digital Circuits, Giovanni De Micheli, McGraw Hill, 1994.

  3. Logic Synthesis, Srinivas Devadas, Abhijit Ghosh and Kurt Keutzer, McGraw Hill, 1994.

  4. Combinatorial Algorithms for Integrated Circuit Layout, Thomas Lengauer, John Wiley and Sons, 1990.

  5. Physical Design Automation of VLSI Systems, Bryan Preas and Michael Lorenzetti, Benjamin/Cummings Publishing, 1988.

  6. Algorithms for VLSI Physical Design Automation, Naveed Sherwani, Kluwer Academic, 1999.

  7. Logic Minimization Algorithms for VLSI Synthesis, Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen and Alberto L. Sangiovanni-Vincentelli, Kluwer Academic, 1984.

  8. Algorithms and Techniques for VLSI Layout Synthesis, Dwight Hill, Don Shugard, John Fishburn abnd Kurt Keutzer, Kluwer Academic, 1989.

Διάγραμμα Διαλέξεων 2008/2009 σε Θεματικές Ενότητες:

Ε1
 CAD, Γιατί, Τί, Παρουσίαση της Ύλης του Μαθήματος, Παραδείγματα Προβλημάτων, Επισκόπιση Αντικειμένου απο Υψηλό επίπεδο μέχρι Διάταξη.
Ε2 Βασικές Αρχές, Προβλήματα P καί NP, Πολυπλοκότητα και Χειρισμός της, Ταξινόμιση Αλγορίθμων, Αφαιρετικά μοντέλα κυκλωμάτων, Αλγόριθμοι Γράφων, η Λογική Σύνθεση με μια ματιά.
Ε3
 Λογική Σύνθεση Α: Αρχές Δυαδικής Άλγεβρας, Δυαδικοί χώροι, αξιώματα καί θεωρήματα, Μερική ή Καθολική περιγραφή Συνάρτησης.
Ε4
 Λογική Σύνθεση Β: Σύνθεση 2-επίπεδων Κυκλωμάτων, Κόστος, Απεικόνιση, Αλγόριθμοι επακριβούς Βελτιστοποίησης, Quine-McCluskey.
Ε5
 Λογική Σύνθεση Γ: Παραδείγματα επακριβούς Βελτιστοποίησης, Συναρτήσεις Πολλαπλών Εξόδων, το πρόβλημα της επαλήθευσης Σφαλμάτων.
Ε6
 Λογική Σύνθεση Δ: Ευριστική Βελτιστοποίηση 2-επίπεδων Κυκλωμάτων, Βασικά Βήματα και Τεχνικές αλγορίθμου-τύπου ESPRESSO, απεικόνιση και επεξεργασία με BDDs καί ITEs.
Ε7
 Λογική Σύνθεση Ε: Ευριστική Βελτιστοποίηση 2-επίπεδων Κυκλωμάτων, Παραδείγματα καί εναλλακτικές μέθοδοι.
Ε8
 Λογική Σύνθεση ΣΤ: Δυαδικά Δίκτυα ή Δίκτυα Boole, Απεικόνιση καί Κόστος Υλοποίησης, Αλγεβρική καί Δυαδική Παραγοντοποίηση, Διαίρεση, Πυρήνες καί Συν-Πυρήνες, Αλγόριθμοι Παραγοντοποίησης.
Ε9
 Λογική Σύνθεση Ζ: Αντικατάσταση καί Αναδόμηση Συνάρτησης, Χρήση όρων DC,  Διόρθωση Φάσης.
Ε10
 Λογική Σύνθεση Η: Τεχνολογική Απεικόνιση 1: Βιβλιοθήκες Κυττάρων Πυλών. Αλγόριθμος Κάλυψης Γράφου καί Μείωση Εμβαδού/Καθυστέρησης.
Ε11
 Λογική Σύνθεση Θ: Τεχνολογική Απεικόνιση 2: Προγραμματιζόμενες Συσκευές, Διαφορές καί Μέθοδοι.
Ε12
Λογική Σύνθεση Ι: Η συνολική εικόνα ενός Συστήματος Λογικής Σύνθεσης, Τα σύστηματα MIS καί SIS, Αλγόριθμοι, Βήματα, Αποτελέσματα, Παραδείγματα.
Ε13
Κατασκευαστική Δοκιμή: Μοντέλα σφαλμάτων, Βασικές Αρχές, Αλγόριθμοι PODEM καί βασισμένοι σε SAT, Παραδείγματα.
Ε14
 Φυσική Σχεδίαση: Επισκόπηση Αλγορίθμων Διχοτόμησης καί Επιμερισμού, Χωροθέτησης καί Τοποθέτησης.
E15
 Συνολική Επισκόπιση της ροής CAD καί προχωρημένα θέματα.

Προτεινόμενες Σχετικές Δημοσιεύσεις πρός Ανάγνωση:

  1. R.K. Brayton, R. Rudell, A.L. Sangiovanni-Vincentelli and A. R. Wang, MIS: A Multiple-Level Logic Optimization System, in IEEE Transactions of Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-6, No. 2, November 1987.
  2. R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli, Multilevel Logic Synthesis, in Proceedings of the IEEE, Vol. 78, No. 2, pp. 264 -- 300, 1990.
  3. S. J. Kong, R.G. Cain and D.L. Ostapko, MINI: A Heuristic approach for Logic Minimization, in IBM Journal of Research and Development, September 1974.
  4. R.K. Brayton, Factoring Logic Functions, in IBM Journal of Research and Development, Vol. 31, No. 2, March 1987.
  5. K. Bartlett, W. Cohen, A. De Geus and G. Hachtel, Synthesis and Optimization of Multilevel Logic under Timing Constraints, in IEEE Transactions of Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-5, No. 4, October 1986.
  6. K.A. Bartlett, R.K. Brayton, G.D. Hachtel, R.M. Jacoby, C.R. Morrison, R.L. Rudell and A.L. Sangiovanni-Vincentelli, Multilevel Logic Minimization using Implicit Don't Cares, in IEEE Transactions of Computer-Aided Design of Integrated Circuits and Systems, Vol. 7, No. 6, June 1988.
  7. S. Devadas, A.R. Wang, R. Newton and A.L. Sangiovanni-Vincentelli, Boolean Decomposition in Multilevel Logic Optimization, in IEEE Journal on Solid-State Circuits, Vol. 24, No. 2, April 1989.
  8. H. Savoj and R.K. Brayton, Observability Relations and Observability Don't Cares, in Proceedings of the IEEE International Conference on Computer-Aided Design,  November 1991.
  9. E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton and A.L. Sangiovanni-Vincentelli, SIS: A System for Sequential Circuit Synthesis, University of California, Berkeley, Electronics Research Laboratory Memorandum No. UCB/ERL M92/41, May 1992.
  10. B. Kernighan and S. Lin, An Efficient Heuristic Procedure for Partitioning Graphs, The Bell System Technical J., vol. 49, no. 2, pp. 291-207, Feb. 1970.
5-2-2009, Χρήστος Σωτηρίου