Complex electronic circuits design with quantum-dot cellular automata
Authors: Λιώλης Ορέστης 
Published: November 2021

Τις τελευταίες δεκαετίες, η (συμβατική) τεχνολογία CMOS, με την υποστήριξη της κλασικής λιθογραφίας, πέτυχε την εκθετική μείωση των διαστάσεων του βασικού δομικού στοιχείου των ολοκληρωμένων κυκλωμάτων. Ωστόσο η συγκεκριμένη τεχνολογία πλησιάζει τα θεμελιώδη φυσικά όρια της τεχνολογίας CMOS, όπως το πάχος των υπέρλεπτων υμενίων των οξειδίων της πύλης του τρανζίστορ, η εμφάνιση φαινομένων κοντού καναλιού (short channel effects), οι εμφανιζόμενες ανομοιομορφίες των προσμίξεων του πυριτίου (doping fluctuations) και η αυξανόμενη δυσκολία, και κατά συνέπια και αύξηση του κόστους, της λιθογραφίας στην κλίμακα των μερικών νανομέτρων.Συνεπώς η επιστημονική κοινότητα έχει προχωρήσει σε εκτεταμένη έρευνα για την ανεύρεση νέων τεχνολογιών στην κλίμακα του νανομέτρου ώστε να αντικαταστήσει την συμβατική τεχνολογία CMOS. Μια απ’ αυτές τις νέες τεχνολογίες, είναι τα Κβαντικά Κυψελιδωτά Αυτόματα (Quantum - dot Cellular Automata - QCA), τα οποία βασίζονται σε φυσικά φαινόμενα, όπως οι ηλεκτροστατικές αλληλεπιδράσεις και καινοτόμες υπολογιστικές τεχνικές, οι οποίες διαφέρουν ριζικά από το συμβατικό υπολογιστικό μοντέλο των κυκλωμάτων CMOS.Η τεχνολογία QCA είναι μια πολλά υποσχόμενη νανοτεχνολογία, η οποία μπορεί να προσφέρει εξαιρετικά χαμηλή κατανάλωση ενέργειας, κυκλώματα πολύ μικρών διαστάσεων και πολύ υψηλής συχνότητας λειτουργία. Βασικό δομικό στοιχείο της τεχνολογίας είναι η κυψελίδα κβαντικών τελειών (quantum – dot cell – QD cell) η οποία αποτελείται από τέσσερις κβαντικές τελείες (quantum dots – QDs) τοποθετημένες στις τέσσερις γωνίες ενός τετραγώνου. Μέσα στην κυψελίδα τοποθετούνται δύο ηλεκτρόνια. Σε αντίθεση με τη συμβατική τεχνολογία όπου οι λογικές καταστάσεις αντιστοιχίζονται στα επίπεδα της τάσης, στην τεχνολογία QCA οι λογικές καταστάσεις καθορίζονται από τις θέσεις που καταλαμβάνουν τα ηλεκτρόνια στη κυψελίδα. Δηλαδή αυτό που καθορίζει την κατάσταση της κυψελίδας είναι το ποια QDs είναι κατειλημμένα από ηλεκτρόνια και ποια όχι.Αν και από το 1993, όπου τα QCA προτάθηκαν για πρώτη φορά από τον Lent, έχουν δημοσιευθεί εκατοντάδες ηλεκτρονικά κυκλώματα στη διεθνή βιβλιογραφία, εξακολουθούν να υπάρχουν πολύ σοβαρά προβλήματα που λειτουργούν ανασταλτικά στην επέκταση της τεχνολογίας. Αυτά τα προβλήματα χωρίζονται σε δύο κατηγορίες. Η πρώτη κατηγορία είναι τα κατασκευαστικά προβλήματα και η δεύτερη τα σχεδιαστικά. Στην πρώτη κατηγορία εντάσσονται προβλήματα όπως η εξεύρεση μεθόδων και τεχνικών κατασκευής που επιτρέπουν την παραγωγή μεγάλης κλίμακας, τη λειτουργία σε κανονικές για ηλεκτρονικές συσκευές θερμοκρασίες και την αντοχή των παραγόμενων κυκλωμάτων στον χρόνο. Τα τελευταία χρόνια φαίνεται να υπάρχουν στη διεθνή βιβλιογραφία προτάσεις που επιλύουν σε κάποιο βαθμό αυτά τα προβλήματα ή τουλάχιστον μέρος αυτών. Αν και η αντιμετώπιση τέτοιου είδους προβλημάτων δεν ήταν αντικείμενο της παρούσας διδακτορικής διατριβής, οι διάφορες προτάσεις αντιμετώπισής τους που υπάρχουν στην βιβλιογραφία μελετήθηκαν. Από την άλλη η αντιμετώπιση των σχεδιαστικών προβλημάτων αποτέλεσε στόχο της έρευνάς που πραγματοποιήθηκε. Καταρχάς με τον όρο σχεδιαστικά προβλήματα, αναφερόμαστε σε προβλήματα όπως ο συγχρονισμός των κυκλωμάτων QCA, η σωστή τοποθέτηση των QD κυψελίδων στον χώρο, ο συνδυασμός διαφορετικών κυκλωμάτων στην βιβλιογραφία, ο αυτοματοποιημένος σχεδιασμός κυκλωμάτων, ο σχεδιασμός κυκλωμάτων ανεκτικά σε σφάλματα κ.α. Ένας παράγοντας που δημιουργεί αυτά τα προβλήματα είναι το γεγονός ότι η τεχνολογία χρησιμοποιεί εντελώς διαφορετικούς μηχανισμού για την εκτέλεση των υπολογισμών, συνεπώς είναι αδύνατη, ή μη αποδοτική, η χρησιμοποίηση των διαφόρων αρχιτεκτονικών που έχουν δοκιμαστεί και χρησιμοποιούνται εδώ και πολλά χρόνια στη τεχνολογία CMOS. Αυτή η έλλειψη αρχιτεκτονικών και μεθοδολογιών σχεδιασμού, όλα τα προηγούμενα χρόνια οδήγησε στο να υπάρχουν στη βιβλιογραφία κυκλώματα που είτε δεν μπορούν να συνδυαστούν μεταξύ τους είτε το αναγκαίο κύκλωμα διασύνδεσής τους μπορεί να γίνει μεγαλύτερο και πολυπλοκότερο ακόμα και από το ίδιο το κύκλωμα που εκτελεί την κυρίως πράξη. Πολύ περισσότερο σε αυτές τις συνθήκες δεν μπορούμε να μιλάμε για οποιαδήποτε μορφής αυτοματοποίηση της διαδικασίας του σχεδιασμού ή δημιουργία εργαλείων λογισμικού για αυτή τη δουλειά. Χωρίς τέτοιου είδους εργαλεία δεν είναι δυνατό η τεχνολογία QCA να χρησιμοποιηθεί για το σχεδιασμό ηλεκτρονικών κυκλωμάτων, ιδιαίτερα μεγάλης κλίμακας, ανεξάρτητα από τα όποια βήματα γίνονται στο κομμάτι των τεχνικών κατασκευής.Στην προσπάθεια αντιμετώπισης του παραπάνω προβλήματος, δημιουργήσαμε και προτείναμε την αρχιτεκτονική Διασταυρούμενων Αγωγών (Programmable Crossbar Architecture). Στη συγκεκριμένη αρχιτεκτονική οι λογικές πύλες σχηματίζονται στα σημεία τομής των διασταυρούμενων αγωγών (οριζόντιων και κάθετων), οι οποίοι αποτελούν συστοιχίες από QD κυψελίδες τοποθετημένες η μία δίπλα στην άλλη. Προκειμένου να γίνει αυτό δυνατό έπρεπε το σύνολο των βασικών λογικών πράξεων να σχεδιαστεί σε αυτήν την αρχιτεκτονική. Οι πύλες AND και OR υλοποιούνταν εξαρχής πάνω στο crossbar καθώς αξιοποιούσαν την πύλη πλειοψηφίας τριών εισόδων (θέτοντας τη μία είσοδο στο λογικό 0 και 1 αντίστοιχα), η οποία αποτελεί ένα από τα πρώτα και πιο θεμελιώδη κυκλώματα QCA στην βιβλιογραφία. Αυτό όμως δεν ίσχυε και για την πύλη NOT, η οποία υλοποιήθηκε στην crossbar αρχιτεκτονική. Χρησιμοποιώντας την καινοτόμα πύλη NOT προτείναμε μια μεθοδολογία σχεδιασμού, με βάση την οποία ο σχεδιαστής μπορεί να προγραμματίζει κάθε σημείο τομής έτσι ώστε να λειτουργεί ως μια από τις τρεις βασικές λογικές πύλες. Έτσι προτείναμε ένα γενικό σύνολο κανόνων σχεδιασμού το οποίο μπορεί να χρησιμοποιηθεί για τον σχεδιασμό οποιουδήποτε ηλεκτρονικού κυκλώματος.Εκτός των άλλων κυκλωμάτων που σχεδιάστηκαν στα πλαίσια της διδακτορικής διατριβής, σχεδιάστηκε στην crossbar αρχιτεκτονική και ένα στοιχείο μνήμης, το οποίο δίνει στην αρχιτεκτονική τη δυνατότητα να αποτελέσει βάση για μια ενιαία μεθοδολογία σχεδιασμού, τόσο συνδυαστικών κυκλωμάτων, όσο και των ακολουθιακών κυκλωμάτων. Επιπλέον, η συγκεκριμένη υλοποίηση συνοδεύτηκε από μια μεθοδολογία σχεδιασμού μεγαλύτερων μνημών (ανεξαρτήτου μεγέθους), δίνοντας παράλληλα τη δυνατότητα στον σχεδιαστή να αποτυπώνει στο κύκλωμά του ακριβώς το μέγεθος της μνήμης που χρειάζεται. Αυτό το χαρακτηριστικό καθιστά την συγκεκριμένη υλοποίηση αρκετά ελκυστική στο σχεδιασμό ενσωματωμένων κυκλωμάτων, όπου ο ευέλικτος καταμερισμός ανάμεσα στη χωρητικότητα της μνήμης και την υπολογιστική ισχύ, μπορεί να γίνεται ακόμα και κατά τη λειτουργία του συστήματος. Έχοντας δημιουργήσει κάποιους γενικούς κανόνες σχεδιασμού κυκλωμάτων QCA και υλοποιώντας ένα στοιχείο μνήμης σε αυτούς τους κανόνες, έγινε δυνατή η δημιουργία μια πλήρως αυτοματοποιημένη μεθοδολογία σχεδιασμού ηλεκτρονικών κυκλωμάτων με την χρήση QD κυψελίδων, στην crossbar αρχιτεκτονική παρέχοντας για πρώτη φορά τα σχεδιαστικά εργαλεία που θα επιτρέψουν την αυτοματοποίηση του σχεδιασμού κυκλωμάτων QCA. Η δημιουργία τέτοιων μεθοδολογιών και αντίστοιχων εργαλείων σχεδιασμού αποτελεί βασική προϋπόθεση για την εδραίωση της τεχνολογίας QCA, καθώς τη σύγχρονη εποχή δεν είναι δυνατόν να σχεδιάζονται χειροκίνητα μεγάλα κυκλώματα και συστήματα, τόσο στη συγκεκριμένη τεχνολογία όσο και στις υπόλοιπες. Εδώ αξίζει να σημειωθεί ότι η συγκεκριμένη μεθοδολογία σχεδιασμού μπορεί να εφαρμοστεί τόσο για το σχεδιασμό συνδυαστικών κυκλωμάτων όσο και ακολουθιακών. Επιπροσθέτως, για πρώτη φορά στην τεχνολογία QCA υλοποιήθηκε ένα εργαλείο λογισμικού που μπορεί να χρησιμοποιηθεί για τον αυτόματο σχεδιασμό κυκλωμάτων. Το συγκεκριμένο εργαλείο δέχεται ως είσοδο τη λογική συνάρτηση που πρέπει να σχεδιαστεί και παράγει στην έξοδό του ένα αρχείο με το σχεδιασμένο κύκλωμα.Επιπλέον, στα πλαίσια της διδακτορικής διατριβής μελετήθηκε και ένα ακόμα σχεδιαστικό πρόβλημα της τεχνολογίας QCA. Το πρόβλημα αυτό αφορά την ανθεκτικότητα των κυκλωμάτων QCA σε κατασκευαστικές αστοχίες. Καταρχάς το γεγονός ότι η λειτουργία των κυκλωμάτων βασίζεται στις ηλεκτροστατικές δυνάμεις Coulomb που αναπτύσσονται μεταξύ των ηλεκτρονίων που βρίσκονται εντός των QDs μπορεί να οδηγήσει στην κατάρρευση ολόκληρου του κυκλώματος σε περίπτωση ακόμα και μικρών αποκλίσεων στις θέσεις των QD κυψελίδων. Με βάση την έρευνα που πραγματοποιήθηκε στα διάφορα σενάρια, τα κυκλώματα QCA των κλασσικών πυλών έχουν μέση ανθεκτικότητα σε αστοχίες περίπου 50%. Μελετώντας τις τεχνικές που έχουν προταθεί στη βιβλιογραφία και προσπαθούν να δώσουν λύση σε αυτό το πρόβλημα, δημιουργήσαμε μια crossbar αρχιτεκτονική ανθεκτική σε σφάλματα, η οποία εκμεταλλεύεται και τα πλεονεκτήματα της αρχιτεκτονικής που αναφέρθηκαν παραπάνω. Η μέση ανθεκτικότητα των νέων πυλών που σχεδιάστηκαν είναι περίπου 95%. Παράλληλα οι νέες διατάξεις των βασικών πυλών είναι λειτουργικές και σε υψηλότερες θερμοκρασίες από τις προηγούμενες.Όλα τα παραπάνω ενίσχυσαν τις σχεδιαστικές δυνατότητες που υπάρχουν στη τεχνολογία QCA, δίνοντας τη δυνατότητα να σχεδιαστούν πολύ μεγάλα κυκλώματα, το οποίο δεν θα μπορούσε να γίνει με την ξεχωριστή τοποθέτηση χιλιάδων QD κυψελίδων με το χέρι. Παράλληλα όμως αυτές οι νέες δυνατότητες δημιούργησαν και νέες μεγάλες απαιτήσεις στο κομμάτι του συγχρονισμού αυτών των μεγάλων συστημάτων. Στη διεθνή βιβλιογραφία έχουν προταθεί κατά καιρούς διάφορες τεχνικές συγχρονισμού κυκλωμάτων QCA. Ωστόσο, αυτές οι μέθοδοι δεν μπορούν να αντιμετωπίσουν αποτελεσματικά το πρόβλημα στο σύνολο των περιπτώσεων. Για παράδειγμα, πολλές από αυτές τις τεχνικές δεν υποστηρίζουν καν βρόχους, ενώ και για τις περιπτώσεις που μπορούν να χρησιμοποιηθούν αυτές οι τεχνικές, τα παραγόμενα αποτελέσματα είναι κατά κανόνα υπερβολικά μεγάλα κυκλώματα ενώ για τα πιο πολύπλοκα συστήματα η χρησιμοποίηση τέτοιων μεθόδων είναι απαγορευτική. Συνεπώς, στη βιβλιογραφία, ο πιο συνηθισμένος τρόπος για την αντιμετώπιση των προβλημάτων συγχρονισμού είναι η προσθήκη κυψελίδων καθυστέρησης στα σήματα εκείνα που προηγούνται. Τα προβλήματα με αυτή τη μέθοδο είναι δύο. Καταρχάς η όλη διαδικασία είναι χειροκίνητη, δηλαδή ο σχεδιαστής βρίσκει τα σήματα που πρέπει να συγχρονιστούν, βρίσκει την καθυστέρηση που πρέπει να εισαχθεί και εντέλει εισάγει την καθυστέρηση με προσοχή έτσι ώστε οι επιπλέον κυψελίδες να μην επηρεάζουν τις υπόλοιπες κυψελίδες οι οποίες εκτελούν τον επιθυμητό υπολογισμό. Συνεπώς, όσο μεγαλώνει το κύκλωμα που πρέπει να υλοποιηθεί και κατ’ επέκταση πρέπει να συγχρονιστεί, τόσο δυσκολότερη γίνεται η χρήση αυτής της μεθόδου. Επιπλέον, αποδείξαμε ότι αυτή η μέθοδος έχει κάποια φυσικά όρια, τα οποία εξαρτώνται αποκλειστικά από την τεχνολογία κατασκευής. Προφανώς αυτά τα όρια θα διευρύνονται όσο βελτιώνονται οι τεχνολογίες κατασκευής, όμως σε κάθε περίπτωση πάντα θα είναι πεπερασμένα. Για την αντιμετώπιση αυτών των προβλημάτων εμπνευστήκαμε από ένα πολύ γνωστό πρόβλημα της επιστήμης των υπολογιστών, το πρόβλημα συγχρονισμού ενός εκτελεστικού αποσπάσματος (Firing Squad Synchronization Problem). Το πρόβλημα αυτό παρουσιάστηκε στη βιβλιογραφία στα τέλη της δεκαετίας του 50 και λύθηκε για πρώτη φορά στις αρχές της δεκαετίας του 60 από τον Moore. Το πρόβλημα αφορά μία σειρά «στρατιωτών», οι οποίοι πρέπει μετά το σήμα ενός «στρατηγού» να συγχρονιστούν μεταξύ τους και να «πυροβολήσουν» ταυτόχρονα, μπορώντας όμως να επικοινωνήσουν μόνο με τους άμεσους γείτονές τους. Δηλαδή το σήμα του «στρατηγού» μεταφέρεται μονάχα στον πρώτο «στρατιώτη» της σειράς μετέπειτα στον διπλανό του και ούτω καθεξής. Επιπλέον οι «στρατιώτες» δε γνωρίζουν το μήκος της σειράς και κατ’ επέκταση δεν μπορούν με κάποιο τρόπο να εκτιμήσουν το πόσο χρόνος απαιτείται για να φτάσει το σήμα σε όλους τους υπόλοιπους. Αφού προσδιορίσαμε τις ομοιότητες και τις διαφορές του FSS προβλήματος και του προβλήματος συγχρονισμού των μεγάλων συστημάτων QCA, δημιουργήσαμε μια γενική μέθοδο χρονισμού, αξιοποιώντας αφενός τον καλύτερο αλγόριθμο επίλυσης του FSS προβλήματος που έχει προταθεί στη βιβλιογραφία από τον Mazoyer και αφετέρου τον αλγόριθμο του Umeo ο οποίος έχει μια τεχνική «παγώματος» της εκτέλεσης του. Τροποποιώντας και επεκτείνοντας τους παραπάνω αλγορίθμους προτείναμε μια μέθοδο χρονισμού που μπορεί να χρησιμοποιηθεί σε οποιοδήποτε κύκλωμα, παρέχοντας παράλληλα μια αποδοτική από άποψη μεγέθους λύση συγκριτικά με τις υπόλοιπες τεχνικές συγχρονισμού, η οποία είναι και ανεξάρτητης πολυπλοκότητας και του αριθμού των υποσυστημάτων που πρέπει να συγχρονιστούν.Τα παραπάνω, εκτός από λύση στο πρόβλημα του συγχρονισμού των κυκλωμάτων QCA αποτέλεσαν και την έμπνευση για παραπέρα μελέτη και αξιοποίηση της θεωρίας και των εφαρμογών των Κυψελιδωτών Αυτομάτων (Κ.Α.) στη τεχνολογία QCA. Τα Κ.Α., που αναπτύχθηκαν από τον John Von Neumann και παραμένουν μέχρι σήμερα μία από τις πιο προσοδοφόρες μεθόδους μοντελοποίησης πολύπλοκων προβλημάτων. Τα Κ.Α. χρησιμοποιούνται σε πολλά επιστημονικά πεδία (Επιστήμη Υπολογιστών, Επεξεργασία Εικόνας, Κρυπτογραφία, Μοντελοποίηση Φυσικών και Χημικών Συστημάτων και Διεργασιών, κ.α.) και βασίζονται στη λογική ότι οι πολύπλοκοι υπολογισμοί δύναται να ιδωθούν ως συνδυασμός πολλών απλούστερων. Η γενική συμπεριφορά του συστήματος ενός Κ.Α. προκύπτει από τις αλληλεπιδράσεις της κάθε κυψελίδας με τις γειτονικές της. Τις πολλές δεκαετίες της ύπαρξής τους έχουν δώσει τη λύση σε πολυάριθμα προβλήματα. Ίσως το πιο γνωστό Κ.Α. είναι το παιχνίδι της ζωής (Game of Life – GoL) το οποίο παρουσιάστηκε από τον Conway το 1970. Από τη στιγμή που παρουσιάστηκε το GoL κέρδισε το ενδιαφέρον της επιστημονικής κοινότητας, επειδή από τους πολύ απλούς κανόνες που διέπουν την εξέλιξη αυτού του δισδιάστατου Κ.Α. προκύπτουν εξαιρετικά πολύπλοκες συμπεριφορές, αλλάζοντας μονάχα την αρχική κατάσταση των κυψελίδων. Μάλιστα στα περίπου 50 χρόνια που έχουν μεσολαβήσει από την παρουσίασή του, έχουν προταθεί πολυάριθμες δομές οι οποίες βρίσκουν εφαρμογή σε πολλούς κλάδους της επιστήμης όπως η βιολογία, η μηχανική, η κρυπτογραφία, η επεξεργασία εικόνας κ.α., ενώ έχουν προταθεί και κάποιες εφαρμογές στη μουσική και τις τέχνες. Από όλες τις εφαρμογές του GoL, αυτές που ίσως παρουσιάζουν μεγαλύτερο ενδιαφέρον και αποτέλεσαν και σημείο της δικής μας έρευνας ήταν η ικανότητα του να υλοποιεί γενικούς υπολογισμούς. Η ικανότητα αυτή αποδείχθηκε για πρώτη φορά το 1982, ενώ από το 2000 και μετά άρχισαν να εμφανίζονται και οι πρώτοι γενικοί υπολογιστές (μηχανή Turring, Minsky Register Machine, Universal Register Machine) υλοποιημένοι στο GoL. Βασικό πλεονέκτημα αυτών των υλοποιήσεων είναι ότι πρόκειται για κυκλώματα πολύ μικρής πολυπλοκότητας όσον αφορά τον σχεδιασμό τους, που αυτό που καθορίζει τη λειτουργία τους είναι η αρχική κατάσταση των κυψελίδων που τα αποτελούν. Μάλιστα η πολυπλοκότητά τους είναι ανεξάρτητη από το μέγεθός αυτών των κυκλωμάτων.Όπως γίνεται κατανοητό η υλοποίηση του GoL στη τεχνολογία QCA δημιουργεί μια πολύ μεγάλη βάση εφαρμογών που μπορούν να χρησιμοποιηθούν άμεσα και να αξιοποιήσουν τα πολλά πλεονεκτήματα της τεχνολογίας. Στα πλαίσια της διδακτορικής έρευνας, σχεδιάστηκε η κυψελίδα του GoL με τη χρήση QCA στην crossbar αρχιτεκτονική. Παράλληλα σχεδιάστηκαν και πλέγματα περισσότερων κυψελίδων.Τέλος σχεδιάστηκε και προσομοιώθηκε η κυψελίδα του GoL και στην αρχιτεκτονική ανθεκτική σε σφάλματα, δίνοντας έτσι ένα κύκλωμα το οποίο μπορεί να απορροφήσει την κατασκευαστική αστοχία κάποιας ή κάποιων από τις χιλιάδες κυψελίδες.