The data-driven multithreading virtual machine

Abstract

Από την εμφάνιση των ψηφιακών υπολογιστών, οι σχεδιαστές τσιπ κατασκεύαζαν ταχύτερους υπολογιστές στηριζόμενοι σε βελτιώσεις στις τεχνολογίες κατασκευής και αρχιτεκτονικές βελτιστοποιήσεις. Ωστόσο, η προσέγγιση αυτή τελικά έγινε αναποτελεσματική λόγω των προβλημάτων της μνήμης, ενέργειας και παραλληλίας επιπέδου εντολής. Η προβλεπόμενη λύση ήταν να στραφούν σε αρχιτεκτονικές πολλαπλών πυρήνων. Αυτή η αλλαγή δεν ασχολήθηκε με πολλά από τα παραπάνω προβλήματα και έφερε τον ταυτοχρονισμό ως μια νέα, μεγάλη πρόκληση. Το μοντέλο ροής δεδομένων είναι ένα τυπικό μοντέλο που μπορεί να χειριστεί τον ταυτοχρονισμό και ανέχεται της καθυστέρηση στη μνήμη και στο συγχρονισμό. Τα συστήματα ροής δεδομένων μπορούν να είναι απλούστερα και πιο ενεργειακά αποδοτικά από τα συμβατικά συστήματα. Στην εργασία αυτή, ερευνούμε ένα μοντέλο εκτέλεσης ροής δεδομένων για την αποτελεσματική αξιοποίηση των πόρων της αρχιτεκτονικές πολλαπλών πυρήνων. Εμείς σχεδιάσαμε, την υλοποίηση και τη βελτιστοποίηση μιας εικονικής μηχανής που υποστηρίζει τo Data-Driven Multithreading (DDM) μοντέλο εκτέλεσης (η οποία συνδυάζει Dynamic Data-Flow ταυτοχρονισμού με την αποτελεσματική σειριακή εκτέλεση) σε ομογενή και ετερογενή πολυπύρηνα συστήματα με οργάνωση υποδοχέα / επιταχυντή και ιεραρχία μνήμης ελεγχόμενη από λογισμικό. Ένα ειδικό λογισμικό προανάκλησης κρυφής μνήμης που βασίζεται στη data-driven πολιτική κρυφής μνήμης - έχει αναπτυχθεί για την αυτόματη διαχείριση των εν λόγω ιεραρχιών μνήμης. Τα ανεπτυγμένα VM υποστηρίζουν κατανεμημένη DDM εκτέλεση σε ένα σύμπλεγμα του πολυπύρηνων κόμβων. Υποστηρίζει, επίσης, ανάλυση εξαρτήσεων κατά τη μεταγλώττιση και την εκτέλεση. Αξιολογήσαμε την ομογενή και ετερογενή υλοποιήσεις του VM για ένα πολυπύρηνο κόμβο και συστάδες χρησιμοποιώντας μια σειρά από πειράματα. Η αξιολόγηση καταδεικνύει ότι η VM επεκτείνεται καλά και ανέχεται καθυστερήσεις καθώς και το κόστος συγχρονισμού αποτελεσματικά επιτυγχάνοντας πολύ καλές επιδόσεις και ξεπερνώντας άλλα state-of-the-art συστήματα.

Since the advent of digital computers, chip designers built faster computers by relying on improvements in fabrication technologies and architectural optimizations. However, this approach was eventually rendered ineffective due to the problems of the Memory, Power and Instruction Level Parallelism Walls. The envisaged solution was to switch to multi-core architectures. This switch did not address many of the above problems and elevated concurrency as a new, major challenge. The Data-flow model is a formal model that can handle concurrency and tolerate memory and synchronization latencies. Data-Flow systems can also be simpler and so more power efficient than conventional systems. In this thesis, we explore a data-flow based execution model for the efficient utilization of the resources of multi-core architectures. We design, implement and optimize a virtual machine supporting the Data-Driven Multithreading (DDM) model of execution (which combines Dynamic Data-Flow concurrency with efficient sequential execution) on homogeneous and heterogeneous multi-core systems with a host/accelerator organization and a software-managed memory hierarchy. A special prefetching software cache -based on data-driven caching policies- is developed for the automatic management of such memory hierarchies. The developed VM supports distributed DDM execution on a cluster of multi-core nodes. It also supports compile-time and runtime dependency resolution. We evaluate the homogeneous and heterogeneous implementations of the VM for single multi-core nodes and clusters using a suite of benchmarks. The evaluation demonstrates that the VM scales well and tolerates latencies and synchronization overheads efficiently achieving very good performance and outperforming other state-of-the-art systems.