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

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

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

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

Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής/τρια θα κατέχει τις παρακάτω γνώσεις, δεξιότητες και ικανότητες:

• Γνώση και κατανόηση της θεωρίας Ευριστικών και μη Αλγορίθμων CAD
• Γνώση και κατανόηση των τύπων Αλγορίθμων και την εφαρμογή τους για την επίλυση ενός προβλήματος
• Γνώση πληθώρας πρακτικών βιομηχανικών Αλγορίθμων CAD για Βελτιστοποίηση Συνδυαστικών Κυκλωμάτων, Ανταλλαγή Εμβαδού, Ταχύτητας, Τεχνολογική Απεικόνιση και Κατασκευαστική Δοκιμή
• Ανάλυση της πολυπλοκότητας των Αλγορίθμων και Αξιολόγηση διαφορετικών μεθόδων λύσης
• Κατανόηση της διαδικασίας σχεδίασης Νέων αλγορίθμων

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

• Εργασίες : 40% Βαθμού
• Πρόοδος : 20% Βαθμού
• Τελική Εξέταση : 40% Βαθμού

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

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