Ανάπτυξη μεθοδολογίας για δυναμική ανάθεση μνήμης σε πολυπύρηνα επεξεργαστικά συστήματα

Abstract

This dissertation presents a methodology for creating dynamic memory allocators on computing systems, ranging from embedded systems to high-workload servers. Our thesis is that modern implementations of dynamic memory allocators have become very generic and do not use sufficiently features and functions of the modern computing systems where they are being executed. We propose a framework, that we call dmmlib, through which application developers can create their own library for dynamic memory management. By selecting different memory organizations, policies and mechanisms, the produced library can be used directly by the applications with recompiling them being optional. The dmmlib framework offers also the possibility to re-configure the allocator at the runtime in order to improve further the application performance, as well as the ability to profile extensively the memory usage.In this dissertation, we show that dmmlib can be used efficiently in both embedded systems with limited software ecosystems and general-purposed, high-performance systems, while it could act as a study and development field of policies and mechanisms for dynamic memory management. We begin by evaluating existing approaches in dynamic memory management, including popular allocators that are used in real-world applications and operating systems, and we show the advantages and possible shortcomings in modern applications. Next, we present dmmlib, and we motivate the implementations of policies and the broader mechanisms. We also derive of a possible way of executing and profiling applications against dmmlib and how the firsts can re-configure the latter at their runtime.We present also two examples of dmmlib usage on top of three different platforms. The first two refer to embedded systems, while the last one to general-purposed systems. The very first uses P2012, a many-core accelerator for embedded systems. Dynamic memory management in this platform requires extra treatment, since a single processing unit is responsible for the resource management of a cluster with 16 processing elements. We port and evaluate dmmlib at this platform. Our results show that the allocators produced by dmmlib can be up to 2.6 times faster than the official allocator of the platform, without compromising additional memory space for the metadata. In the next embedded platform, we show how processor scalability affects the performance of dynamic memory allocators. Experimental results show that low-level memory managers may not cope with scalability if the processors exceed a certain number. Finally, our last target platform is more generic and our work aims on predicting the sizes of future requests and how the current allocator can use such information in order to re-configure and improve himself at runtime. Our approach introduces minimal overhead, while it manages to keep memory fragmentation low.

Η διατριβή αυτή παρουσιάζει μία μεθοδολογία για τη δημιουργία δυναμικών αναθετών μνήμης (dynamic memory allocators) σε μία μεγάλη ποικιλία υπολογιστικών συστημάτων, από ενσωματωμένα συστήματα έως εξυπηρετητές υψηλού φόρτου. Πιστεύουμε ότι οι σημερινές υλοποιήσεις δυναμικών αναθετών μνήμης χαρακτηρίζονται από γενικεύσεις, με αποτέλεσμα να μη χρησιμοποιούν επαρκώς χαρακτηριστικά και λειτουργίες των μοντέρνων υπολογιστικών συστημάτων πάνω στα οποία εκτελούνται. Προτείνουμε ένα πλαίσιο λογισμικού, το οποίο αποκαλούμε dmmlib, μέσα από το οποίο προγραμματιστές εφαρμογών μπορούν να δημιουργήσουν την δική τους βιβλιοθήκη δυναμικής διαχείρισης μνήμης. Επιλέγοντας διαφορετικές οργανώσεις μνήμης, πολιτικές και μηχανισμούς, η παραγόμενη βιβλιοθήκη μπορεί να χρησιμοποιηθεί άμεσα από εφαρμογές χωρίς να είναι αναγκαία η επαναμεταγλώττιση των τελευταίων. Η dmmlib προσφέρει δυνατότητες αλλαγής των παραμέτρων του αναθέτη για την περαιτέρω βελτίωση των επιδόσεων των εφαρμογών, όπως επίσης και την δυνατότητα εκτενούς παρακολούθησης της λειτουργίας της μνήμης.Σε αυτήν την διατριβή, δείχνουμε ότι η dmmlib μπορεί να χρησιμοποιηθεί αποδοτικά τόσο σε ενσωματωμένα συστήματα με περιορισμένο οικοσύστημα λογισμικού όσο και σε εξυπηρετητές γενικού σκοπού και υψηλής υπολογιστικής απόδοσης, ενώ μπορεί να αποτελέσει πεδίο μελέτης και ανάπτυξης πολιτικών και μηχανισμών για δυναμική διαχείριση μνήμης. Ξεκινούμε αναλύοντας τις τρέχουσες προσεγγίσεις στη δυναμική διαχείριση μνήμης, συμπεριλαμβανομένων δημοφιλών αναθετών που χρησιμοποιούνται σε ρεαλιστικές εφαρμογές και λειτουργικά συστήματα, και δείχνουμε πλεονεκτήματα και πιθανές ελλείψεις των αναθετών αυτών σε σύγχρονα συστήματα και εφαρμογές. Στησυνέχεια, παρουσιάζουμε την dmmlib, και δείχνουμε τα κίνητρα και τις αντίστοιχες υλοποιήσεις των πολιτικών και των ευρύτερων μηχανισμών. Δείχνουμε επίσης πιθανούς τρόπους εκτέλεσης των εφαρμογών με την dmmlib και πώς αυτές μπορούν να τροποποιήσουν την dmmlib κατά την εκτέλεσή τους.Παρουσιάζουμε επίσης χρήσεις της dmmlib πάνω σε τρεις διαφορετικές πλατφόρμες. Οι δύο πρώτες αφορούν ενσωματωμένα συστήματα, ενώ η τρίτη συστήματα γενικού σκοπού. Η πρώτη χρησιμοποιεί την P2012, έναν πολυπύρηνο επιταχυντή για ενσωματωμένα συστήματα. Η δυναμική ανάθεση μνήμης στην πλατφόρμα αυτή χρήζει ιδιαίτερης μεταχείρισης, καθώς μία επεξεργαστική μονάδα αναλαμβάνει την διαχείριση των πόρων για μία ομάδα 16 επεξεργαστών. Μεταφέρουμε και αξιολογούμε την dmmlib στην πλατφόρμα αυτή. Τα αποτελέσματά μας δείχνουν ότι αναθέτες που παράγονται από την dmmlib μπορεί να είναι ακόμα και 2,6 φορές πιο γρήγοροι από τον επίσημο αναθέτη της πλατφόρμας, χωρίς να διακινδυνεύει επιπλέον κόστος στη χρήση μνήμης. Στην δεύτερη πλατφόρμα δείχνουμε πώς η κλιμακωσιμότητα του υλικού επηρεάζει την απόδοση των δυναμικών αναθετών μνήμης. Για συστήματα με πολλαπλές επεξεργαστικές μονάδες, πειραματικά αποτελέσματα δείχνουν ότι δυναμικοί αναθέτες μνήμης χαμηλού επιπέδουαδυνατούν να αντεπεξέλθουν της πολυπλοκότητας και υπολείπονται αναθετών πουπαράγονται μέσα από την dmmlib. Τέλος, σε συστήματα γενικού σκοπού δείχνουμε πώς μπορούν να εκτιμηθούν τα μεγέθη μελλοντικών αιτημάτων μνήμης και πώς ο τρέχων αναθέτης μπορεί να χρησιμοποιήσει την πληροφορία αυτή, ώστε να τροποποιηθεί κατά την εκτέλεση της εφαρμογής. Η προσέγγισή μας εισάγει ελάχιστο επιπλέον κόστος, ενώ καταφέρνει να διατηρήσει τον κατακερματισμό της μνήμης στο ελάχιστο.