Αρχιτεκτονική ροής δεδομένων

Η αρχιτεκτονική ροής δεδομένων (dataflow architecture) είναι μια αρχιτεκτονική υπολογιστή που έρχεται σε αντίθεση με την παραδοσιακή αρχιτεκτονική φον Νόιμαν ή αρχιτεκτονική ροής ελέγχου. Οι αρχιτεκτονικές ροής δεδομένων δεν έχουν μετρητή προγράμματος και (τουλάχιστον στη θεωρία) η δυνατότητα εκτέλεσης μιας εντολής καθώς και η ίδια η εκτέλεσή της εξαρτάται μόνο από τη διαθεσιμότητα των παραμέτρων εισόδου της εντολής. Αν και καμία εμπορικά επιτυχημένη αρχιτεκτονική υπολογιστή γενικού σκοπού δεν έχει χρησιμοποιήσει αρχιτεκτονική ροής δεδομένων, η αρχιτεκτονική έχει υλοποιηθεί με επιτυχία σε υλικό ειδικού σκοπού όπως στην ψηφιακή επεξεργασία σήματος, στη δρομολόγηση δικτύων, στην επεξεργασία γραφικών και, πιο πρόσφατα, στην αποθήκευση δεδομένων (data warehousing). Έχει επίσης σχέση με πολλές αρχιτεκτονικές λογισμικού που χρησιμοποιούνται σήμερα, όπως η σχεδίαση των μηχανών των βάσεων δεδομένων και τα πλαίσια προγραμματισμού παράλληλων υπολογισμών.

Οι σύγχρονες (synchronous) αρχιτεκτονικές ροής δεδομένων ρυθμίζονται ώστε να ταιριάζουν με το φόρτο εργασίας που εμφανίζουν οι εφαρμογές δεδομένων πραγματικού χρόνου (real-time data path applications) όπως η προώθηση πακέτων (wire speed packet forwarding). Οι αρχιτεκτονικές ροής δεδομένων που είναι ντετερμινιστικής φύσης επιτρέπουν στον προγραμματιστή να χειρίζεται περίπλοκες εργασίες όπως η εξισορρόπηση φόρτου στον επεξεργαστή (processor load balancing) και ο συγχρονισμός και η πρόσβαση σε κοινούς πόρους [1].

Οι αρχιτεκτονικές υλικού για ροή δεδομένων ήταν σημαντικό θέμα της έρευνας στην αρχιτεκτονική υπολογιστών κατά τη δεκαετία του 1970 και στις αρχές της δεκαετίας του 1980. Ο Jack Dennis του MIT υπήρξε πρωτοπόρος του πεδίου της αρχιτεκτονικής στατικής ροής δεδομένων ενώ η Μηχανή Ροής Δεδομένων του Μαντσεστερ (Manchester Dataflow Machine) και η αρχιτεκτονική MIT Tagged Token ήταν σημαντικά εγχειρήματα της δυναμικής ροής δεδομένων.

Οι υπολογιστές στατικής ροής δεδομένων που χρησιμοποιούν στη σχεδίασή τους τις κλασικές διευθύνσεις μνήμης σαν ετικέτες εξάρτησης μεταξύ των δεδομένων ονομάζονται υπολογιστές στατικής ροής δεδομένων. Αυτοί οι υπολογιστές δεν επιτρέπουν σε πολλαπλά στιγμιότυπα της ίδιας ρουτίνας να εκτελούνται ταυτόχρονα γιατί οι απλές ετικέτες δε μπορούν να ξεχωρίσουν μεταξύ αυτών. Οι υπολογιστές δυναμικής ροής δεδομένων χρησιμοποιούν μνήμη διευθύνσεων περιεχομένων (CAM) και χρησιμοποιούν ετικέτες στη μνήμη για να διευκολύνουν τον παραλληλισμό.

Συνήθως οι μεταγλωττιστές αναλύουν τον πηγαίο κώδικα του προγράμματος για εξαρτήσεις δεδομένων μεταξύ των εντολών ώστε να οργανώσουν καλύτερα τις ακολουθίες εντολών στα δυαδικά αρχεία που παράγουν. Οι εντολές οργανώνονται ακολουθιακά αλλά η ίδια η πληροφορία των εξαρτήσεων δεν καταγράφεται στα δυαδικά αρχεία. Τα δυαδικά αρχεία που μεταγλωττίζονται για έναν υπολογιστή ροής δεδομένων περιέχουν αυτήν την πληροφορία εξαρτήσεων. Ένας μεταγλωττιστής ροής δεδομένων καταγράφει αυτές τις εξαρτήσεις δημιουργώντας μοναδικές ετικέτες για κάθε εξάρτηση αντί να χρησιμοποιεί ονόματα μεταβλητών. Δίνοντας σε κάθε εξάρτηση μια μοναδική ετικέτα, τμήματα κώδικα του δυαδικού αρχείου που δεν έχουν εξαρτήσεις μεταξύ τους είναι δυνατό να εκτελεστούν εκτός σειράς (out of order) και παράλληλα.

Τα προγράμματα φορτώνονται στην CAM ενός υπολογιστή δυναμικής ροής δεδομένων. Όταν όλα τα ορίσματα με ετικέτες μιας εντολής γίνουν διαθέσιμα (από έξοδο προηγούμενων εντολών ή από την είσοδο του χρήστη), η εντολή σημειώνεται σαν έτοιμη για εκτέλεση από μια μονάδα εκτέλεσης (execution unit). Αυτό είναι γνωστό σαν ενεργοποίηση (activating) ή εκπυρσοκρότηση (firing) της εντολής. Όταν μια εντολή τελειώσει από τη μονάδα εκτέλεσης, τα δεδομένα εξόδου της αποθηκεύονται (με την ετικέτα της) στην CAM. Όσες εντολές εξαρτώνται από αυτό το συγκεκριμένο δεδομένα (που αναγνωρίζεται από την ετικέτα του) σημειώνονται στη συνέχεια σαν έτοιμες για εκτέλεση. Με αυτόν τον τρόπο, οι επόμενες εντολές εκτελούνται με τη σωστή σειρά, αποφεύγοντας race conditions. Αυτή η σειρά μπορεί να διαφέρει από την ακολουθιακή σειρά που είχε υπόψη του ο προγραμματιστής, την προγραμματισμένη σειρά.

Κάθε εντολή, μαζί με τα απαιτούμενα ορίσματα δεδομένων της, στέλνεται σε μια μονάδα εκτέλεσης σαν ένα πακέτο, το οποίο είναι γνωστό σαν μονάδα εντολής (instruction token). Όμοια, τα δεδομένα εξόδου στέλνονται πίσω στην CAM σαν μονάδα δεδομένων (data token). Το πακετάρισμα των εντολών και των αποτελεσμάτων επιτρέπει την παράλληλη εκτέλεση των εντολών που είναι έτοιμες, σε μεγάλη κλίμακα. Τα δίκτυα ροής δεδομένων αφήνουν τις μονάδες εντολών στις μονάδες εκτέλεσης και επιστρέφουν τις μονάδες δεδομένων στην CAM. Σε αντίθεση με τη συμβατική αρχιτεκτονική φον Νόιμαν, οι μονάδες δεδομένων δεν αποθηκεύονται μόνιμα στη μνήμη, αλλά είναι προσωρινά μηνύματα που υπάρχουν μόνο όταν βρίσκονται στην πορεία προς τον αποθηκευτικό χώρο εντολών.

Η έρευνα, όμως, δε μπόρεσε ποτέ να ξεπεράσει τα εξής προβλήματα που σχετίζονταν με:

  • Αποδοτική μετάδοση των μονάδων δεδομένων σε ένα μαζικά παράλληλο σύστημα.
  • Αποδοτική διεκπεραίωση μονάδων δεδομένων σε ένα μαζικά παράλληλο σύστημα.
  • Κατασκευή CAMs αρκετά μεγάλων ώστε να μπορούν να κρατούν τις εξαρτήσεις ενός πραγματικού προγράμματος.

Οι εντολές και οι εξαρτήσεις δεδομένων τους αποδείχτηκε ότι ήταν πολύ λεπτού κόκκου (fine-grained) για να κυκλοφορούν αποδοτικά σε ένα μεγάλο δίκτυο. Δηλαδή, ο χρόνος που χρειάζονταν οι εντολές και τα αποτελέσματα με τις ετικέτες τους για να ταξιδέψουν διαμέσου ενός μεγάλου δικτύου συνδέσεων ήταν μεγαλύτερος από το χρόνο που χρειαζόταν για τον ίδιο τον υπολογισμό.

Παρόλα αυτά, η Εκτέλεση εκτός σειράς (Out-of-order execution, OoO) έχει γίνει το βασικό παράδειγμα υπολογισμού από τη δεκαετία του 1990. Αποτελεί μια μορφή περιορισμένης ροής δεδομένων. Αυτό το παράδειγμα εισήγαγε την ιδέα ενός παραθύρου εκτέλεσης (execution window). Το παράθυρο εκτέλεσης ακολουθεί τη σειρά εκτέλεσης της αρχιτεκτονικής Φον Νόιμαν, αλλά μέσα στο παράθυρο οι εντολές επιτρέπεται να εκτελούνται σε σειρά εξαρτήσεων δεδομένων. Αυτό επιτυγχάνεται σε CPU που δίνουν δυναμικά ετικέτες στις εξαρτήσεις δεδομένων του κώδικα στο παράθυρο εκτέλεσης. Η λογική πολυπλοκότητα της ανίχνευσης των εξαρτήσεων δεδομένων περιορίζει τις CPU με OoO σε ένα μικρό αριθμό μονάδων εκτέλεσης (2-6) και θέτει όριο στο παράθυρο εκτέλεσης μεταξύ 32 και 200 εντολών, πολύ μικρότερο από όσο είχε αρχικά προταθεί για πλήρεις υπολογιστές ροής δεδομένων.

Δείτε επίσης Επεξεργασία

Παραπομπές Επεξεργασία