Οι επεξεργαστές, οι μνήμες, οι μεταγωγείς, και τα interfaces εισόδου/εξόδου αποτελούν τους βασικούς δομικούς λίθους των σύγχρονων και των μελλοντικών συστημάτων δικτύων υπολογιστών. Τα δίκτυα διασύνδεσης κατέχουν κεντρικό ρόλο σε όλες τις κλίμακες : από το χώρο των συστημάτων, ως τα τοπικά αλλά και τα δίκτυα ευρείας περιοχής. (πολλά θέματα αρχιτεκτονικού χαρακτήρα είναι όμοια σε όλα αυτά τα επίπεδα). Τα δίκτυα διασύνδεσης υψηλής ταχύτητας χρησιμοποιούν συνδέσμους σημείου προς σημείο και μεταγωγείς, έτσι ώστε να αποφευχθούν οι καθυστερήσεις που οφείλονται σε διαιτησία, και για να αυξηθεί ο παραλληλισμός στην επικοινωνία.
Στα σημερινά δίκτυα διασύνδεσης υπάρχει αυξημένο ενδιαφέρον για ποιότητα
υπηρεσιών (QoS). Από τη μια όμως, βελτιωμένη ποιότητα υπηρεσιών συνεπάγεται
μικρή καθυστέρηση για κίνηση υψηλής προτεραιότητας, το οποίο σημαίνει
μεταξύ άλλων και χρονοπρογραμματισμό βάσει προτίμησης (preemptive scheduling)
στους μεταγωγείς, όπως λόγου χάρη στη μεταγωγή πακέτων ή ποσοτήτων μικρού μεγέθους
(σε δύο δημοφιλείς τεχνολογίες, αυτό επιτυγχάνεται χρησιμοποιώντας κύτταρα
στην τεχνολογία Asynchronous Transfer Mode (ATM) [LeB92], ή
flits στο Wormhole Routing [DS87]).
Από την άλλη πλευρά, για να βελτιωθεί η ποιότητα υπηρεσιών απαιτείται εξεζητημένος
έλεγχος ροής, ο οποίος βασίζεται στη διαχείριση κάθε ροής ατομικά. Κατά συνέπεια αυτό σημαίνει
τη διατήρηση και τη διαχείριση πολλαπλών ουρών. Επίσης, πολλές ουρές απαιτούνται
για να αποφευχθεί το φαινόμενο μπλοκαρίσματος στην αρχή της ουράς (head-of-line
blocking), έτσι ώστε να είναι δυνατόν δηλαδή οι ροές υψηλής προτεραιότητας
ή οι ασυμφόρητες ροές να προσπεράσουν αυτές που είναι χαμηλότερης προτεραιότητας
ή συμφορημένες.
Η υλοποίηση πολλαπλών ουρών και η διαχείρισή τους σε ψηλές ταχύτητες κατέχει
ένα σημαντικότατο ρόλο στη σχεδίαση μεταγωγέων για δίκτυα υψηλής απόδοσης.
Αυτή η εργασία παρουσιάζει την υλοποίηση της διαχείρισης πολλαπλών ουρών και εξεζητημένου ελέγχου ροής σε hardware, μέσα σε ένα μεταγωγέα υψηλής ταχύτητας. Συγκεκριμένα παρουσιάζεται ο πυρήνας του τμήματος ελέγχου ενός μεταγωγέα ATM, ολοκληρωμένος σε ένα μοναδικό chip, με 16x16 σύνδεσμους των 622Mbps και προαιρετικό έλεγχο ροής βασισμένο σε πιστώσεις (backpressure ανά ομάδα ροής). Αυτό το chip, ονομαζόμενο ATLAS I, έχει 4 εκατομμύρια τρανζίστορ, παρέχει δυνατότητα multicasting, τρία επίπεδα προτεραιότητας, διαμοιρασμένο χώρο ενταμίευσης, καθυστέρηση για cut-through λιγότερη από ένα μικροδευτερόλεπτο, δυνατότητα ομαδοποίησης συνδέσμων, πίνακα μετάφρασης εικονικών μονοπατιών/κυκλωμάτων (VP/VC) και υποστήριξη για παρακολούθηση και έλεγχο φόρτου. Ο ATLAS I βρίσκεται υπό ανάπτυξη και θα κατασκευαστεί σύντομα σε τεχνολογία CMOS 0.35 micron.
Στο παρελθόν η μεταγωγή γινόταν συχνά σε επίπεδο λογισμικού, σε υπολογιστές
γενικού σκοπού ή χρησιμοποιώντας επεξεργαστές συγκεκριμένα για αυτό το σκοπό
ειδικά σε περιβάλλοντα τοπικού ή ευρύ δικτύου (LAN, WAN).
Μεταγωγείς εξ' ολοκλήρου σε hardware έχουν χρησιμοποιηθεί κυρίως σε
πολυεπεξεργαστές. Σήμερα όμως, με την επιθυμία για βελτιωμένη ποιότητα
υπηρεσιών, που συνεπάγεται μικρές καθυστερήσεις και κύτταρα μικρού μεγέθους,
οι μεταγωγείς υψηλής απόδοσης πρέπει να υλοποιούνται σε hardware
[Tob90], και να ενσωματώνουν δομές δεδομένων κατάλληλες για
τα κύτταρα που αποθηκεύουν, οι οποίες δεν ήταν απαραίτητες πριν
[CST88].
Η σύγχρονη τεχνολογία VLSI παρέχει τη δυνατότητα για να ολοκληρωθούν τέτοιοι
εξελιγμένοι μεταγωγείς σε ένα μοναδικό chip, αποφεύγοντας έτσι το υψηλό
κόστος και τα μειονεκτήματα απόδοσης που αφορούν λύσεις πολλών chip.
Διαχείριση εξεζητημένων δομών δεδομένων σε hardware μέσα σε μεταγωγείς έχει
εμφανιστεί και παλιότερα σε δρομολογητές wormhole, όπως στους
[TF88], iWarp [B+90],
Spider [Gal97], αλλά και σε μεταγωγείς ATM που έχουν
αναπτύξει οι
[KES+91], [SMS+91],
Prizma [DEI95], κ.α.
Σε σύγκριση όμως με αυτές τις εργασίες ο ATLAS διατηρεί πολλές λογικές ουρές στην έξοδο ως ένα διαμοιρασμένο χώρο από αναγνωριστές (identifiers) με έναν μοναδικό κοινόχρηστο ελεγκτή, αποφεύγοντας έτσι το ψηλό κόστος σε χώρο των ενταμιευτών και των ελεγκτών ανά ουρά εξόδου όπως στον μεταγωγέα Prizma [DEI95]. Επίσης, η λειτουργία του μοναδικού ελεγκτή στον ATLAS I είναι pipelined, μια και πρέπει να διαχειριστεί τις δομές δεδομένων των κυττάρων σε πολύ υψηλότερους ρυθμούς από ότι παλαιότεροι μεταγωγείς [TF88], [KES+91]. Ο μεταγωγέας ATLAS υλοποιεί έλεγχο ροής πολλών λωρίδων (multilane) βασισμένο σε πιστώσεις, ενώ άλλοι μεταγωγείς είτε δεν παρέχουν έλεγχο ροής [DEI95], [KES+91], [TF88], ή μονάχα έλεγχο ροής ατομικών λωρίδων (single-lane) [SMS+91]. Ορισμένοι δρομολογητές wormhole, όπως ο iWarp [B+90] και ο Spider [Gal97] υποστηρίζουν έλεγχο ροής πολλαπλών λωρίδων (multilane) για ένα μικρό αριθμό καναλιών ή ομάδων ροών και υλοποιούν ουρές με έναν ενταμιευτή σταθερού μεγέθους ανά κανάλι. Ο ATLAS I από την άλλη πλευρά υποστηρίζει 65536 ομάδες ροών (4096 για καθεμιά από τις 16 θύρες του), διαχειρίζεται 54 ουρές εξόδου από ``έτοιμα'' κύτταρα, όπως και έναν αριθμό από κύτταρα χωρίς πιστώσεις (``creditless''). Όλα τα κύτταρα και οι ουρές μοιράζονται δυναμικά έναν μοναδικό χώρο αποθήκευσης. Τέλος, ο ATLAS υλοποιεί όλα τα παραπάνω χαρακτηριστικά σε ένα μοναδικό chip, παρέχοντας μια ικανοποιητική λύση όσο αφορά το κόστος για δίκτυα διασύνδεσης υψηλής ταχύτητας.
Συμπερασματικά, ο ATLAS I προσφέρει ένα συνδυασμό από έλεγχο ροής υψηλής ταχύτητας πολλαπλές ουρές μέσα σε έναν κοινόχρηστο ενταμιευτή, και δυνατότητα multicasting, συνδυασμός που είναι μοναδικός ανάμεσα στους δρομολογητές wormhole και στους μεταγωγείς ATM. Η υλοποίηση αυτών των χαρακτηριστικών απαιτεί μια εξεζητημένη μονάδα ελέγχου μέσα σ'αυτόν τον μεταγωγέα σε VLSI. Η λειτουργία της βασίζεται σε δύο παράλληλες pipelines : η μία χειρίζεται αφίξεις και αναχωρήσεις κυττάρων και η δεύτερη αφίξεις πιστώσεων. Οι εξαρτήσεις που δημιουργούνται σ' αυτές τις pipelines των τριών και τεσσάρων βαθμίδων επιλύονται με προσπεράσματα, έτσι ώστε να αποφευχθούν φαινόμενα ακινητοποίησής τους. Επίσης ο ελεγκτής αυτός χρησιμοποιεί μη τετριμένες δομές δεδομένων : οι ουρές των ``έτοιμων'' κυττάρων υλοποιούνται ως διασυνδεδεμένες λίστες, οι άδειες θέσεις του ενταμιευτή αναγνωρίζονται από μια λίστα ελεύθερων θέσεων, και τέλος οι σύνδεσμοι εξόδου ενός κυττάρου και οι διαθέσιμες πιστώσεις του αναπαριστάνονται με μάσκες.
Η μονάδα ελέγχου είναι κεντρικοποιημένη και λειτουργεί πάνω στις επικεφαλίδες των κυττάρων στις διευθύνσεις και στους αναγνωριστές των πιστώσεων. Ο μέγιστος ρυθμός λειτουργίας της κατέδειξε την ανάγκη χρήσης πολύπορτων μνημών και μνημών προσπελάσιμων βάση του περιεχομένου τους, ώστε να υλοποιηθούν οι παραπάνω hardware δομές δεδομένων. Η εξεζητημένη λειτουργικότητα αυτών των μνημών, η οποία παρουσιάζεται εκτενώς στα ακόλουθα κεφάλαια, εισήγαγε την ανάγκη χρήσης τεχνικών σχεδίασης σε full-custom VLSI. Αυτή η εργασία παρουσιάζει ακριβώς την υλοποίηση σε full-custom VLSI του υποσυστήματος διαχείρισης πολλαπλών ουρών του ATLAS I.
Ακολουθεί μία συνοπτική περιγραφή του μεταγωγέα ATM ATLAS I.