Πληροφορίες Μαθήματος

  1. Περιγραφή

  2. Ο στόχος του ΗΥ437 είναι η εμβάθυνση και η εξοικείωση με Αλγορίθμους Ηλεκτρονικού Σχεδιαστικού Αυτοματισμού (EDA - Electronic Design Automation) αιχμής για την αυτοποιημένη σχεδίαση και επαλήθευση ψηφιακών ηλεκτρονικών κυκλωμάτων (CAD - Computer Aided Design).

    Το μάθημα εστιάζει σε (1) Αλγορίθμους Λογικής Σύνθεσης, (2) Τεχνολογικής Απεικόνισης σε Βιβλιοθήκη Πυλών Τεχνολογίας Κατασκευής (standard-cell technology library), και (3) Κατασκευαστικής Επαλήθευσης, δηλαδή στα στάδια υλοποίησης ΠΡΟ της Φυσικής Σχεδίασης, και παρουσιάζει επακριβείς και ευριστικούς αλγορίθμους πανομοιότυπους με αυτούς που υλοποιούνται σε βιομηχανικά εργαλεία, όπως το Synopsys DC ή το Cadence RC Compiler.

  3. Ύλη

  4. Η ύλη του μαθήματος χωρίζεται σε 3 μέρη.

    1. Τι είναι CAD, Παραδείγματα Τύπων Προβλημάτων και Αλγορίθμων
    2. Βασικές Αρχές Αλγορίθμων, Προβλήματα P καί NP, Πολυπλοκότητα και Χειρισμός της, Ταξινόμιση και Είδη Αλγορίθμων, Αφαιρετικά μοντέλα κυκλωμάτων
    3. Λογική Σύνθεση Α: Αρχές Δυαδικής Άλγεβρας, Δυαδικοί χώροι, Αξιώματα καί Θεωρήματα, Απλοποίηση Δυαδικής Συνάρτησης, Θεώρημα Boole/Shannon, Ταυτολογία
    4. Λογική Σύνθεση Β: Αυτοματοποιημένη Σύνθεση και Απλοποίηση 2-επίπεδων Κυκλωμάτων, Κόστος, Απεικόνιση, Θεώρημα Quine, Εξαγωγή Πρώτων, Πίνακας περιορισμών UCP, Αλγόριθμος Quine-McCluskey
    5. Λογική Σύνθεση Γ: Παραδείγματα επακριβούς Βελτιστοποίησης, Συναρτήσεις Πολλαπλών Εξόδων, σχέση μεταξύ βέλτιστης σύνθεσης και Επαλήθευσης (DFT)
    6. Λογική Σύνθεση Δ: Κωδικοποίηση Κύβων, Αλγεβρικές Πράξεις και Ιδιότητες
    7. Λογική Σύνθεση Ε: Ευριστική Βελτιστοποίηση 2-επίπεδων Κυκλωμάτων, Αλγόριθμος ESPRESSO, πράξεις EXPAND, REDUCE, IRREDUNTANT, ESSENTIALS, Λειτουργία Hill-climbing απο τοπικά Ελάχιστα, Παραδείγματα Βελτιστοποίησης με το ESPRESSO
    8. Δυαδικά Διαγράμματα Αποφάσεων (Binary Decision Diagrams - BDDs) ως κανονική μορφή για ορισμό και σύγκριση Δυαδικών Συναρτήσεων
    9. Λογική Σύνθεση ΣΤ: Πολυ-επίπεδη Έκφραση Κυκλώματος, Δυαδικά Δίκτυα και οι πράξεις ELIMINATE, DECOMPOSE, EXTRACT, SIMPLIFY, SUBSTITUTE, Παραδείγματα
    10. Λογική Σύνθεση Ζ: Ανταλλαγή Βάθους/Εμβαδού μέσω Δυαδικής ή Αλγεβρικής Παραγοντοποίησης, Αλγόριθμοι Διαίρεσης και κοινοί Παράγοντες, Πυρήνες και Συν-πυρήνες - Αλγόριθμοι Εξαγωγής, Αλγόριθμοι Κάλυψης Ορθογωνίων για απο κοινού βελτιστοποίηση
    11. Λογική Σϋνθεση Η: Χρήση των Εσωτερικών/Εξωτερικών Αδιάφορων Τιμών (DCs) για Πολυ-επίπεδη Απλοποίηση, Satisfiability καί Observability DCs (SDC, ODCs), Παραδείγματα
    12. Τεχνολογική Απεικόνιση σε Βιβλιοθήκη Τεχνολογίας: Αλγόριθμοι Κάλυψης Γράφου και Δέντρων
    13. Κατασκευαστική Δοκιμή: Μοντέλα Σφαλμάτων, Ευαισθητοποίηση Οδού και Παρατηρησιμότητα, Εσωτερική Σάρωση, Delay Fault Testing, Αλγόριθμοι ATPG: D καί PODEM

  5. Εργασίες

  6. Το μάθημα περιλαμβάνει προγραμματιστικές εργασίες, οι οποίες εφαρμόζουν πρακτικά τις θεωρητικές γνώσεις του μαθήματος.
  7. Βαθμολόγηση

  8. Η βαθμολόγηση θα γίνεται με τους εξής γνώμονες:


    Οι στόχοι της παραπάνω κατανομής ποσοστών είναι η διαρκής αξιολόγηση των φοιτητών κατά την διάρκεια του εξαμήνου και η εξαγωγή του τελικού βαθμού απο όσο το δυνατόν περισσότερα δείγματα γνώσεων.
  9. Μονάδες

  10. Το μάθημα είναι επιλογής, αντιστοιχεί σε 4 Διδακτικές Μονάδες, 6 μονάδες ECTS και βρίσκεται στην Περιοχή του Υλικού και Αρχιτεκτονικής Υπολογιστών.

Χ. Σωτηρίου - Tελευταία ενημέρωση - 9/10/2013.