Σχεδιασμός πολύπλοκων ηλεκτρονικών κυκλωμάτων με κβαντικά κυψελιδωτά αυτόματα

In previous decades, the conventional CMOS technology with the support of lithography succeeded to reduce the size of the basic structural element of any integrated circuits. However, this technology is reaching the CMOS fundamental limits, such as the thickness of the gate oxides of a transistor, the appearance of short channel effects, the doping fluctuations as well as the increasing difficulty and cost of nano-scale lithography. So, the scientific community is intensely researching novel nano-scale technologies in order to replace the conventional CMOS technology. One of these technologies is the Quantum-dot Cellular Automata (QCA). QCA are dependent on physical phenomena such as electrostatic reactions and novel computation techniques, which are very different compared to conventional computation model of CMOS circuits.QCA technology is a very promising nanotechnology, which provides ultra-low power consumption, very small circuits and very high operation frequency. The basic structural element of QCA technology is the quantum-dot cell (QD cell) which consists of four quantum dots (QDs) placed at the vertices of a square. Two electrons are placed inside the cell. In contrast to the conventional electronics where the logic states are represented by the voltage level, in QCA technology the logic states are represented by the position of the electrons within the cell. Namely, the logic state of one cell is defined by the QDs which are occupied by electrons.Even though QCA was introduced in 1993 by Lent and hundreds of electronic circuits have been presented in literature, some very important technological issues still exist. These issues can be classified into two main categories. The first one consists of the fabrication problems, while the second consists of the design problems. The fabrication problems are about finding techniques and methods which will enable the large scale fabrication, functionality in temperatures comparable to that of conventional electronics, circuit durability and others. Several works recently presented in literature claim to resolve these problems or at least some of them. Although these issues were not the subject of this Ph.D. thesis, these works have been thoroughly studied.On the other hand, the goal of the Ph.D. research was to provide solutions to the design problems of the QCA technology. Firstly, with the term design problems, we describe problems such as the efficient QD cells placing in the area, the QCA circuits’ synchronization, the combination of different circuits in the literature, the automated design, the design of fault-tolerant circuits and others. These problems are caused by the QCA technology’s computational mechanisms which differ from the mechanisms that are used in conventional electronics. Consequently, the utilization of architectures and design methods that have been used for many years is either impossible or inefficient. This lack of architectures and methods leads to the design of circuits, that presented in the literature and they either cannot be combined or the interconnection circuit is bigger and more complex than the circuit that makes the computation. Moreover, while these problems remain unsolved, we cannot even talk about automated circuit design or the presentation of software tools for this task. Regardless of the improvement of the fabrication techniques, it is impossible for QCA technology to be used for large-scale electronic circuits design, without such automated tools. A solution to this problem is the Programmable Crossbar Architecture that was created during the Ph.D. research. In this architecture the logic gates are formed at the cross points of vertical and horizontal wires. These wires are QD cells placed one next to the other. In order to make this architecture applicable to digital circuits design the three fundamental gates of Boolean algebra should be implemented in this. The logic OR and AND gates are implemented in cross shape, since both are utilizing the 3-input majority gate which is one of the first and most used circuit in QCA circuit design in the literature. On the other hand, this is not the case for the NOT gate. A cross-shape NOT gate designed and presented in this thesis. Then we used this novel NOT gate and we proposed a design methodology with the ability to program each cross point to function as one of the three fundamental logic gates. So, we proposed a universal set of design rules, which is applicable to the design of any electronic circuit.Among the other circuits that were designed to prove the functionality of the proposed architecture during the Ph.D. thesis, a memory element was designed too. This memory element is providing the architecture with the ability to be used in the design of sequential logic design too. Furthermore, this memory implementation was followed by a design methodology for larger memories, providing the designer with the ability to create circuits with the exact size of memory they need. This makes this memory implementation very attractive compared to the others, especially in embedded system design, where the flexible adjustments between memory and computational power are taking place even during system operation.The memory element and the universal set of design rules are the base of a complete methodology of automated design of QCA electronic circuits in crossbar architecture. Moreover, in this thesis design methodologies and tools for automated design are presented for the first time. The creation of such methodologies and corresponding design tools is a basic precondition for the consolidation of QCA technology, as in modern times it is not possible to manually design large circuits and systems, both in this technology and in others. The proposed design methodology can be applied to both combinatorial and sequential circuit design. In addition, for the first time in QCA technology, a software tool was implemented that can be used for automated circuit design. This tool takes as input the logical function to be designed and produces a file with the circuit’s layout as its output.Moreover, during this Ph.D. research another design problem of QCA technology is studied. This problem is the tolerance of QCA circuits to construction failures. First of all, the fact that the operation of the circuits is based on the Coulomb electrostatic forces that develop between the electrons inside the QDs can lead to the collapse of the whole circuit in case of even small deviations in the positions of the QD cells. Based on the research carried out in the various scenarios, the QCA circuits of the standard logic gates that used in the literature have an average fault tolerance about 50%. By studying the techniques proposed in the literature and trying to solve this problem, we created a fault-tolerant crossbar architecture, which makes use of the advantages of crossbar architecture as mentioned above. The average fault tolerance of the proposed gates is about 95%. At the same time, the fault-tolerant gates are functional at higher temperatures than the standard ones.All of the above have enhanced the design capabilities of QCA technology, namely they enable very large circuits design, which could not be done by placing manually thousands of QD cells. However, these new capabilities create great new demands in the synchronization of these large systems. Various QCA circuit synchronization techniques have been proposed the past years in the literature. However, these methods cannot effectively address the problem in all cases. For example, many of these techniques do not even support loops, and even in cases where these techniques can be used, they usually result in too large circuits, while for more complex systems the use of such methods is prohibitive. Therefore, in the literature, the most common way to deal with synchronization problems is to add delay cells to the preceding signals. There are two problems with this method. First the whole process is manual, i.e. the designer finds the signals to be synchronized, finds the delay to be entered and finally inserts the delay carefully so that the extra cells do not affect the other cells which perform the desired calculation. So, the larger the circuit to be implemented and consequently to be synchronized, the more difficult it becomes to use this method. In addition, we have shown that this method has some physical limits, which depend solely on the fabrication technology. Obviously, these limits will be expanded as fabricating techniques improve, but in any case they will always be finite.To address these issues, we were inspired by a well-known computer science problem, the Firing Squad Synchronization Problem. This problem appeared in the literature in the late 1950s and was first solved in the early 1960s by Moore. The problem concerns a series of "soldiers", who must synchronize with each other and "shoot" at the same time, after the signal of a "general". The soldiers can only communicate with their immediate neighbors. Namely, the signal of the "general" is transferred only to the first "soldier" of the line later to his neighbor and so on. In addition, the "soldiers" do not know the length of the line and therefore cannot somehow estimate how long it takes for the signal to reach everyone else. After identifying the similarities and differences between the FSS problem and the synchronization problem of large QCA systems, we developed a universal timing method, utilizing both the best FSS problem-solving algorithm proposed in the literature by Mazoyer and the "freeze" technique by Umeo. By modifying and enhancing the above algorithms we proposed a synchronization method that can be used in any circuit, while providing a size-efficient solution compared to other synchronization techniques. The proposed method is independent of the complexity and number of subsystems to be synchronized.The above, except of a solution to the QCA circuits synchronization problem, was the inspiration for further study and utilization of the theory and applications of Cellular Automata (CA) in QCA technology. CA were developed by John Von Neumann and remain to this day one of the most lucrative methods for modeling complex problems. CA are used in many scientific fields (Computer Science, Image Processing, Cryptography, Modeling of Physical and Chemical Systems and Processes, etc.) and are based on the logic that complex calculations can be seen as a combination of many simpler ones. The general behavior of a CA arises from the interactions of each cell with its neighbors. The many decades of their existence, they have provided the solution to numerous problems. Perhaps the most known CA is the Game of Life (GoL) which was introduced by Conway in 1970. Since its introduction, GoL has gained the interest of the scientific community, because from very simple rules extremely complex behaviors occur, through changing only the initial state of the cells. In fact, in the approximately 50 years that have passed since its introduction, numerous structures have been proposed which find application in many scientific fields such as biology, engineering, cryptography, image processing, etc. Some applications of GoL have also been proposed in music and the arts. Of all the GoL applications, the ones that are perhaps the most interesting and they were part of the Ph.D. research was its ability to perform universal calculations. This universality was first demonstrated in 1982, and from 2000 the first universal computers (Turring machine, Minsky Register Machine, Universal Register Machine) implemented in GoL began to appear in the literature. The main advantage of these implementations is that they are low complex circuits. The circuit’s operation is depended on the initial state of the cells. In fact the complexity is independent of the size of these circuits.The implementation of GoL in QCA technology creates a very large database of ready-to-use applications that take advantage of the technology’s characteristics. During this Ph.D. research, the GoL cell was designed in crossbar architecture using QCA. Grids of more cells were also designed and presented. Finally, a GoL cell was designed and simulated in the fault-tolerant architecture that mentioned earlier.Τις τελευταίες δεκαετίες, η (συμβατική) τεχνολογία 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. Ωστόσο, αυτές οι μέθοδοι δεν μπορούν να αντιμετωπίσουν αποτελεσματικά το πρόβλημα στο σύνολο των περιπτώσεων. Για παράδειγμα, πολλές από αυτές τις τεχνικές δεν υποστηρίζουν καν βρόχους, ενώ και για τις περιπτώσεις που μπορούν να χρησιμοποιηθούν αυτές οι τεχνι