Στις αρχιτεκτονικές με CAM υφίσταται το πρόβλημα επιλογής ενός στοιχείου
από ένα σύνολο εναλλακτικών επιλογών και έχουν αναφερθεί μέθοδοι επίλυσής
του ως επιλυτής πολλαπλών ταιριασμάτων, δίκτυο προτεραιοτήτων, κωδικοποιητής
προτεραιότητας, κωδικοποιητής κανονικοποίησης ή διαιτητής αιτήσεων.
Το πρόβλημα επίλυσης πολλαπλών αιτήσεων αναδύεται όταν το ψάξιμο σε μία
προσεταιριστική μνήμη παράγει περισσότερα από ένα ισοδύναμα αποτελέσματα στη
μονάδα του χρόνου. Για να επιλεγεί ένα από αυτά το σύστημα πρέπει να είναι
ικανό να γεννήσει ένα 1 για την επιθυμητή επιλογή και μηδέν για όλα τα
υπόλοιπα. Ή αλλιώς το πρόβλημα μπορεί να θεωρηθεί ότι είναι να διαλέξεις από
ένα διάνυσμα Α μεγέθους N-bit, ένα μόνο στοιχείο που να είναι ένα λογικό ένα.
Ανάλογα με την περίπτωση αυτή η εκλογή μπορεί να υποδεικνύεται με μία
απευθείας διεύθυνση i, ένα διάνυσμα P (pointer) στο οποίο μόνο ένα P(i) είναι
ένα, ή ένα διάνυσμα I (inhibit), τέτοιο ώστε μόνο το
να είναι ένα.
Στο τμήμα διαχείρισης πολλαπλών ουρών του ATLAS I, ένας αποκωδικοποιητής προτεραιότητας κρίνεται απαραίτητος για τη σωστή λειτουργία των μνημών βάση περιεχομένου, αφού πολλές λέξεις μπορεί να ταιριάξουν κατά τη διάρκεια μίας λειτουργίας ψαξίματος. Έτσι ένας ελεγκτής πολλαπλών ταιριασμάτων πρέπει να έχει τον έλεγχο να επιλέγει και να προωθεί μόνο μία απόκριση. Το διάστημα χρόνου για να παράγει ένα μοναδικό αποτέλεσμα πρέπει να είναι μικρότερο ή ίσο με τον κύκλο ρολογιού της προσεταιριστικής μνήμης, έτσι ώστε να μπορεί να λειτουργεί με το ρυθμό λειτουργίας της μνήμης.
Όπως φαίνεται στο σχήμα 3.16 η είσοδος στον αποκωδικοποιητή προτεραιότητας
είναι ένα διάνυσμα 256-bit αποτελούμενο από τις γραμμές ταιριάσματος
από τις μνήμες flowGroup και outMask, υποδηλώνοντας αυτές τις λέξεις που
ταιριάσαν με τη λέξη προς ψάξιμο. Ο αποκωδικοποιητής προτεραιότητας
παράγει ένα διάνυσμα του ίδιου μεγέθους, όπου υπάρχει ένα και μόνο ``1'',
αντιστοιχώντας στο πρώτο ένα του διανύσματος εισόδου. Ο υπολογισμός
ενός bit της εξόδου αναπόφευκτα χρειάζεται να λάβει υπόψη του όλες τις
παραπάνω του εισόδους. Αν καμιά από αυτές δεν είναι ένα ταίριασμα αλλά ούτε και
η συγκεκριμένη αντίστοιχη είσοδος τίθεται ένα σήμα ονομαζόμενο
Nobody-Else-Higher (NEH) και δείχνει αυτό το αποτέλεσμα. Ουσιαστικά
τότε μία έξοδος είναι το .
Το κύκλωμα του αποκωδικοποιητή προτεραιότητας βασίζεται στις αναφορές των [JC89] και [THY+96]. Η δομή της αλυσίδας ριπής διαφαίνεται η πιο προκλητική επιλογή του πλεονεκτήματος που έχει αναφορικά με το χώρο που καταλαμβάνει και την απόδοσή της. Η απλότητα αυτής της τεχνικής, συνδυαζόμενη με την ευκολία κατασκευής και την δυνατότητα για περαιτέρω βελτίωση αντιστάθμισαν τα πλεονεκτήματα άλλων σχημάτων αποκωδικοποιητών προτεραιότητας ([Koz96]). Όπως διασαφηνίζουν οι Wade και Sodini η απόδοση ενός τέτοιου κυκλώματος πέφτει βαθμιαία καθώς το σήμα NEH πρέπει να διαδοθεί μέσα από μία μακρυά γραμμική δομή.
Αυτό το μειονέκτημα μπορεί να ξεπεραστεί και να επιταχύνουμε τη λειτουργία αυτή χρησιμοποιώντας πρόβλεψη. Πιο συγκεκριμένα, σχεδιάστηκε μία δομή με ένα δέντρο από πύλες OR δύο επιπέδων, που παράγει γραμμές προσπεράσματος, και υλοποιεί ένα είδος πρόβλεψης κρατουμένου, υπολογισμού του πιο νωρίς από την στιγμή που απαιτείται ([WE93]), διαδίδοντας νωρίτερα την ύπαρξη ενός ταιριάσματος. Κατά τη σχεδίαση χρησιμοποιήθηκε δυναμική προφορτιζόμενη λογική με χρονισμό domino, για να μειωθούν οι καθυστερήσεις, ο χώρος και οι ενδιάμεσες μεταβάσεις τάσης. Επιπλέον, ο αποκωδικοποιητής προτεραιότητας χωρίστηκε σε δύο βαθμίδες, η καθεμιά από τις οποίες λειτουργεί σε διαφορετική φάση ρολογιού. Έτσι η μια βαθμίδα προφορτίζεται ενώ η άλλη λειτουργεί (μεταξύ των δύο βαθμίδων υπάρχουν μανταλωτές μίας φάσης). Η πρώτη βαθμίδα περιλαμβάνει ένα δέντρο δύο επιπέδων από δυναμικές πύλες NOR, το οποίο δουλεύει ως μία γεννήτρια προσπερασμάτων των γραμμών ταιριάσματος για τη δεύτερη βαθμίδα pipeline. Οι είσοδοι συνδυάζονται σε ομάδες των 16, και για καθεμιά μία πύλη OR ανιχνεύει αν υπάρχει κάποιο ``1''. Το επόμενο επίπεδο του δέντρου αποτελείται από πύλες OR πάλι αλλά με αυξανόμενο αριθμό εισόδων κατά την κατεύθυνση διάδοσης του σήματος NEH, το οποίο τελικά βγάζει τα σήματα προσπεράσματος. Το πρώτο γεννάται από έναν απλό αντιστροφέα, ενώ το τελευταίο από μία πύλη OR 16 εισόδων. Η δεύτερη βαθμίδα pipeline αποτελείται από αλυσίδες τύπυ Manchester, που λειτουργούν σε ξεχωριστές ομάδες γραμμές ταιριάσματος των 16. Η διάταξη και τα κυκλώματα του αποκωδικοποιητή προτεραιότητας φαίνονται στο σχήμα 3.16. Μία λεπτομερέστατη περιγραφή της αρχιτεκτονικής και της λειτουργίας του αποκωδικοποιητή προτεραιότητας υπάρχουν στο [Koz96].
Figure 3.16: Η διάταξη και τα κυκλώματα του αποκωδικοποιητή προτεραιότητας
Ο αποκωδικοποιητής προτεραιότητας που φαίνεται στο σχήμα 3.16 σχεδιάστηκε σε χώρο διαστάσεων 60 μm x 1860 μm. Η κατακόρυφη διάσταση οφείλεται στο μέγεθος της μνήμης CAM η οποία τον τροφοδοτεί με τις γραμμές ταιριάσματος. Αποτελέσματα προσομοίωσης (σχήμα 3.17) έδειξαν ότι μπορεί να λειτουργήσει σε συχνότητα ρολογιού 100 MHz, κάτω από τις χειρότερες συνθήκες προσωμοίωσης.
Figure 3.17: Κυματομορφές του αποκωδικοποιητή προτεραιότητας (σενάριο χειρότερης
περίπτωσης : καμιά είσοδος δεν ήταν έγκυρο ταίριασμα) ( )
Παρόλα αυτά, με στόχο να μην επιμηκυνθεί η δεύτερη pipeline της διαχείρισης ουρών, η οποία επεξεργάζεται τις αφίξεις πιστώσεων, εξετάστηκαν σε βάθος δύο εναλλακτικές λύσεις. Σύμφωνα με την πρώτη, η λειτουργία ψαξίματος στις μνήμες CAM και η πρώτη βαθμίδα του αποκωδικοποιητή προτεραιότητας (αποτελούμενη από το δέντρο δύο επιπέδων) έπρεπε να παράγουν ένα έγκυρο αποτέλεσμα μέσα σε μία φάση ρολογιού. Στην επόμενη φάση που φορτίζονται οι γραμμές ταιριάσματος, ταυτόχρονα γίνεται ο υπολογισμός της δεύτερης βαθμίδας του αποκωδικοποιητή προτεραιότητας, παράγοντας ένα διάνυσμα με ένα μόνο ``1'', αν στην προηγούμενη φάση υπήρχε κάποιο ταίριασμα. Η δεύτερη εναλλακτική λύση ήταν να αφιερωθεί εξ' ολοκλήρου η μία φάση του ρολογιού στο ψάξιμο των CAM's, και να συμπυκνωθούν και οι δύο βαθμίδες του αποκωδικοποιητή προτεραιότητας στην επόμενη φάση.
Το δυναμικό στυλ λογικής όμως, που χρησιμοποιήθηκε νωρίτερα κρίθηκε ακατάλληλο και για τις δύο εναλλακτικές λύσεις, διότι οι είσοδοι στα κυκλώματα τύπου domino δεν ήταν δυνατό να είναι σταθερές κατά τη φάση υπολογισμού. Έτσι μπορούσε να συμβεί εκφόρτιση του κόμβου εξόδου προτού οι είσοδοι να πάρουν την τελική έγκυρη τιμή τους. Γι' αυτό, παρά τα πλεονεκτήματα της δυναμικής λογικής (μικρές παρασιτικές χωρητικότητες, μεγάλη ταχύτητα, μικρή κατανάλωση ισχύος) έπρεπε να κινηθούμε προς συμπληρωματική λογική, ή λογική τύπου CVSL, χρησιμποιώντας cascode CVSL ή SSDL ([WE93]). Άλλη μία συνέπεια της πρώτης εναλλακτικής λύσης θα ήταν να χρησιμοποιηθούν αισθητήριοι ενισχυτές για τις γραμμές ταιριάσματος, όπως αυτοί που αναφέρονται στους [JC89] και [THY+96], επιταχύνοντας έτσι την τροφοδοσία του αποκωδικοποιητή προτεραιότητας με έγκυρες τιμές. Αν και φαινόταν εφικτό, η προσπάθεια-χρόνος σχεδίασης και η κατανάλωση ισχύος των αισθητήριων ενισχυτών αντισταθμίστηκαν από τη δεύτερη λύση. Εξετάστηκαν επίσης κάποιες άλλες επιλογές, όπως άνιση διάρκεια φάσεων του κύκλου ρολογιού ή νέο σχήμα για τον αποκωδικοποιητή προτεραιότητας, αλλά απορρίφθηκαν.
Ένα υβριδικό σχήμα χρησιμοποιήθηκε για να υλοποιήσει μία πύλη OR μεγάλου fan-in. Μία πύλη OR 16-εισόδων απεικονίζεται στο σχήμα 3.18.
Figure 3.18: Μία πύλη OR 16-εισόδων (υπολογίζει το αποτέλεσμα στη φάση phi1)
Η πύλη προφορτίζεται κατά τη φάση phi2 και υπολογίζει το αποτέλεσμα στη φάση phi1.
Οι γραμμές ταιριάσματος αντεστραμμένες αποτελούν τις εισόδους της. Οι αλυσίδες
pull-down από τα τρανζίστορ NMOS είναι κατανεμημένα κατά μήκος της κατακόρυφης
διεύθυνσης όπου είναι οι αντίστοιχες είσοδοι. Η κοντότερη αλυσίδα βρίσκεται
και πιο μακρυά από την έξοδο, για να αντισταθμίσει τη μεγαλύτερη παρασιτική
χωρητικότητα λόγω συρμάτων διασύνδεσης. Η καθυστέρηση εξόδου της πιο πάνω
πύλης OR που τροφοδοτεί τις 16 εισόδους του δεύτερου επιπέδου πυλών OR είναι
2.3 ns. Το πιο κάτω σήμα προσπεράσματος γεννιέται μετά από 4.3 ns από την
ανερχόμενη ακμή του phi1. Αυτό συμβαίνει στην κρίσιμη περίπτωση όπου καμία
είσοδος δεν είναι σε υψηλό δυναμικό (αν υπάρχει έστω και ένα ``1'' δεν
συμβαίνει αλλαγή στην έξοδο), οπότε πρέπει να τραβηχτεί κάτω η έξοδος Y όσο
το δυνατόν πιο γρήγορα. Ένα μοναδικό τρανζίστορ PMOS θα μπορούσε να προστεθεί
(ονομαζόμενο αποκαταστάτη επιπέδου στο [J.M96]) μεταξύ του
και της εισόδου του οδηγητή αντιστροφέα, για να τραβήξει την έξοδο πιο γρήγορα
στη γείωση. Όταν η έξοδος αρχίζει να χαμηλώνει (
)
το τρανζίστορ αυτό ανοίγει και βοηθά την είσοδο να ανέβει γρηγορότερα.
Το αρνητικό αποτέλεσμα είναι από τη μιά ότι αυξάνεται η χωρητικότητα του
εσωτερικού κόμβου και από την άλλη ότι το τρανζίστορ μάχεται τη μείωση της
τάσης στον κόμβο αυτό πριν σβήσει εντελώς, καθυστερώντας έτσι περισσότερο το
χρόνο ανόδου της πύλης. Αυτό όμως δεν ενέχει καθόλου κόστος στην περίπτωσή
μας, αφού η φάση προφόρτισης διαρκεί αρκετά.
Επίσης, σε περίπωση προβλημάτων χρονισμού εξετάστηκε μία επιπλέον βελτίωση. Ένα κύκλωμα με σύνδεση προς τα πίσω, όμοιο σε αρχή λειτουργίας με αυτό της προηγούμενης παραγράφου μπορεί να χρησιμοποιηθεί όπως φαίνεται στο σχήμα 3.19. Συγκεκριμένα χρησιμοποιείται ένα τρανζίστορ NMOS για να συντομεύσει το δρόμο προς τη γείωση μόλις το σήμα εξόδου αρχίζει να ανεβαίνει.
Figure 3.19: Η βελτιωμένη βαθμίδα B του αποκωδικοποιητή προτεραιότητας
Στο σχήμα 3.20 φαίνεται η απόκριση του κυκλώματος, καταδείχνοντας
ότι η έκδοση του αποκωδικοποιητή προτεραιότητας χωρίς pipeline είναι εφικτή.
Πρέπει να σημειωθεί ότι οι ακίδες τάσης που φαίνονται στα σήματα
οφείλονται στη χωρητική σύζευξη μεταξύ του ρολογιού και των σημάτων εξόδου.
Figure 3.20: Κυματομορφές του αποκωδικοποιητή προτεραιότητας χωρίς pipeline
(χειρότερη περίπτωση : καμιά είσοδος δεν ήταν έγκυρο ταίριασμα)
Αν και το πρόβλημα επίλυσης πολλαπλών ταιριασμάτων έχει ερευνηθεί αρκετά στο παρελθόν, η λειτουργία αυτή ολοκληρώνεται σε διακριτά, ανεξάρτητα διαστήματα χρόνου (είτε μετρημένα σε λειτουργίες ψαξίματος είτε σε καθυστερήσεις πυλών), χωρίς να λαμβάνονται υπόψη τα προηγούμενα αποτελέσματα. Από τη σκοπιά ενός προσεταιριστικού συστήματος η λειτουργία αυτή είναι μη προσεταιριστική, αφού είναι ανεξάρτητη από το περιεχόμενο των πολλαπλών ταιριασμάτων. Μέχρι στιγμής μία μοναδική γραμμή ταιριάσματος μπορεί να επιλεγεί βάση της φυσικής της θέσης (με μεθόδους ριπής κρατουμένου ή δομές μορφής δέντρου ή συνδυασμούς). Συνεπώς, είναι άξιο προσοχής το γεγονός ότι η επόμενη γραμμή στο χρόνο που θα επιλεγεί είναι ασυσχέτιστη με το ιστορικό της επίλυσης πολλαπλών ταιριασμάτων. Στην περίπτωση βεβαίως όπου υπάρχει μία μοναδική γραμμή που βρέθηκε να ταίριαζει και ανήκει σε μία ανεξάρτητη ροή δεν τίθεται θέμα. Όταν όμως δύο ή περισσότερα κύτταρα είναι χωρίς πιστώσεις και ένα ψάξιμο λόγω μιας εισερχόμενης πίστωσης παράγει πολλές γραμμές που ταιριάζουν, πρέπει να υπάρχει ένας μηχανισμός για δίκαιη μεταχείριση. Ένας απλός γραμμικός αποκωδικοποιητής προτεραιότητας δεν μπορεί να εκπληρώσει αυτήν την απαίτηση. Γι' αυτό ένα νέο σχήμα εφευρέθηκε που παρέχει εγγυήσεις δικαιοσύνης και παρουσιάζεται στις επόμενες παραγράφους.