Δομές δεδομένων σε hardware

Το σχήμα 2.2 απεικονίζει τις δομές δεδομένων που διατηρούνται και διαχειρίζονται από το hardware του ATLAS, έτσι ώστε να υλοποιηθεί η παραπάνω αρχιτεκτονική ουρών. Ολη η πληροφορία που αφορά ένα δεδομένο κύτταρο είναι αποθηκευμένη σε μνήμες που είναι ``παράλληλες'' προς τον ενταμιευτή κυττάρων, δηλαδή η διεύθυνση του σώματος ενός κυττάρου στον ενταμιευτή αποτελεί τον αναγνωριστή αυτού του κυττάρου, και χρησιμοποιείται για να προσπελάσει όλη τη σχετική με αυτό πληροφορία. Οι ουρές ``έτοιμων'' κυττάρων διατηρούνται ως διασυνδεδεμένες λίστες. Η υλοποίηση απλοποιείται αρκετά από την απόφαση να επιτρέπεται σε κάθε κύτταρο να ανήκει το πολύ σε μία ``έτοιμη'' ουρά: χρειάζεται ένας δείκτης στο επόμενο κύτταρο, που κρατείται στη μνήμη των δεικτών ουράς (Queue Pointer memory)gif. Επίσης, το γεγονός ότι κάθε κύτταρο μπορεί να βρίσκεται το πολύ σε μία ``έτοιμη ουρά'' περιορίζει τις απαιτήσεις μέγιστου ρυθμού εξυπηρέτησης στον ελεγκτή. Σε διαφορετική περίπτωση, εισάγωντας κύτταρα σε πολλαπλές ουρές σε συγκεκριμένες χρονικές στιγμές θα υπαγόρευε έναν πολύ υψηλότερο στιγμιαίο ρυθμό λειτουργίας. Οι 54 ουρές που χρειάζονται στον ATLAS I αναγνωρίζονται από τα περιεχόμενα μίας μνήμης 54x17, του Αρχείου Καταχωρητών Κεφαλής/Ουράς (HTRF) (το bit εγκυρότητας χρησιμοποιείται για να διακρίνει τις άδειες ουρές από τις γεμάτες).

   figure177
Figure 2.2: Οι δομές δεδομένων στη διαχείριση ουρών

Μία εναλλακτική λύση που εξετάστηκε, αλλά απορρίφθηκε ήταν να υλοποιηθούν οι ``έτοιμες'' ουρές με αριθμούς σειράς. Για κάθε ουρά θα κρατιόταν ένας μετρητής σειράς για το πρώτο και το τελευταίο (όμοια ακριβώς με την HTRF). Για κάθε κύτταρο θα χρειαζόταν ένας αριθμός σειράς μαζί με την υπόλοιπη πληροφορία για την κατάσταση του κυττάρου (αυτό είναι όμοιο με το πεδίο δείκτη στο επόμενο κύτταρο). Εντούτοις, για να εντοπιστεί το πρώτο κύτταρο σε μία ουρά θα χρειαζόταν ένα ψάξιμο βάσει περιεχομένου στο πεδίο αριθμού σειράς, σε αντίθεση με μία απλή προσπέλαση σε μία μνήμη RAM όπως ισχύει για την οργάνωση με διασυνδεδεμένες λίστες. Βεβαίως πρέπει να σημειωθεί ότι δεν απαιτείται αυστηρή σειρά εξυπηρέτησης FIFO για τις συνδέσεις που υπόκεινται σε έλεγχο ροής προς τα πίσω, απλώς πρέπει να γίνεται ένας δίκαιος χρονοπρογραμματισμός. Αφού μέσα στο chip μπορεί να υπάρξει μόνο ένα κύτταρο ανά ομάδα ροής σε οποιαδήποτε δεδομένη στιγμή, δεν είναι ανάγκη να διατηρείται σειρά FIFO ούτε μέσα σε μία ομάδα ροής. Παρόλα αυτά, χρειάζεται σειρά FIFO για τις συνδέσεις που δεν υπόκεινται σε έλεγχο ροής προς τα πίσω, διότι η σειρά των κυττάρων μέσα σε ένα VC πρέπει να διατηρείται σύμφωνα με το ATM.

Για κάθε κύτταρο επίσης κρατιέται η εξής πληροφορία : ο αριθμός ομάδας ροής (12 bits), η μάσκα εξόδου (outMask), μία μάσκα των 17 bits που υποδεικνύει τους επιθυμητούς συνδέσμους εξόδου για ένα κύτταρο (ο 17ος σύνδεσμος αντιστοιχεί στη θύρα σύνδεσης του εξωτερικού μικροεπεξεργαστή). Επίσης η μάσκα πιστώσεων (creditMask), μία μάσκα των 17 bits που υποδηλώνει τους συνδέσμους εξόδου για τους οποίους το κύτταρο έχει αποκτήσει μία πίστωσηgif. Ολη αυτή η πληροφορία είναι σημαντική για τα κύτταρα που είναι χωρίς πιστώσεις (creditless) και άρα το σύνολο των μνημών που την φυλάσσει ονομάζεται λίστα των κυττάρων χωρίς πίστωση (CreditLess Cell List (CLL)). Όταν φτάνει μία νέα πίστωση ανιχνεύεται η CLL αν υπάρχει αποθηκευμένη καταχώρηση με την ομάδα ροής και το σύνδεσμο (outMask) της πίστωσης. Κατόπιν γίνεται ένα το αντίστοιχο bit της creditMask. Το πεδίο outMask ενδιαφέρει επίσης άμεσα τα έτοιμα κύτταρα που είναι multicast (τα άλλα έτοιμα κύτταρα μπορούν να εκμαιεύσουν όλη την πληροφορία που χρειάζονται από τον αριθμό ουράς στον οποίο ανήκουν). Τα κύτταρα που είναι χωρίς πίστωση δεν ανήκουν σε καμία έτοιμη ουρά, και άρα το πεδίο δείκτη στο επόμενο δεν χρησιμοποιείται. Στο παράδειγμα του σχήματος 2.2 κύτταρο 253 που είναι σκιασμένο είναι χωρίς πίστωση (οι μάσκες πιστώσεων και συνδέσμων εξόδου διαφέρουν κατά ένα bit).

Στον ATLAS I χρησιμοποιούνται πέντε ξεχωριστά κομάτια μνήμης για να υλοποιήσουν την παραπάνω οργάνωση. Αυτός ο διαχωρισμός που συζητείται παρακάτω, και κρίθηκε απαραίτητος λόγω των διαφορετικών ειδών προσπέλασης και χρονισμού καθενός πεδίου. Μία έκτη μνήμη μεγέθους 256x1 έχει χρησιμοποιηθεί ως λίστα των ελεύθερων θέσεων (Free List) του ενταμιευτή των κυττάρων.


next up previous
Next: Οι pipelines στη διαχείριση Up: Οργάνωση της Διαχείρισης Πολλαπλών Previous: Αρχιτεκτονική λογικών ουρών

Giorgos &
Tue Jul 8 17:26:02 EET DST 1997