No description available.

Lors de l'exécution des applications à base d'objets, plusieurs millions d'objets peuvent être créés, utilisés et enfin détruits s'ils ne sont plus référencés. Néanmoins, des dysfonctionnements peuvent apparaitre, quand des objets qui ne sont plus utilisés ne peuvent être détruits car ils sont référencés. De tels objets gaspillent la mémoire principale et les applications utilisent donc d'avantage de mémoire que ce qui est effectivement requis. Nous affirmons que l'utilisation du gestionnaire de mémoire virtuel du système d'exploitation ne convient pas toujours, car ce dernier est totalement isolé des applications. Le système d'exploitation ne peut pas prendre en compte ni le domaine ni la structure des applications. De plus, les applications n'ont aucun moyen de contrôler ou influencer la gestion de la mémoire virtuelle. Dans cette thèse, nous présentons Marea, un gestionnaire de mémoire virtuelle piloté par les applications à base d'objets. Il constitue une solution originale qui permet au développeurs de gérer la mémoire virtuelle au niveau applicatif. Les développeurs d'une application peuvent ordonner à nôtre système de libérer la mémoire principale en transférant les \emph{objets inutilisés, mais encore référencés} vers une mémoire secondaire (telle qu'un disque dur). En plus de la description du modèle et des algorithmes sous-jacents à Marea, nous présentons notre implémentation dans le langage Pharo. Notre approche a été validée à la fois qualitativement et quantitativement. Ainsi, nous avons réalisés des expérimentations et des mesures sur des applications grandeur-nature pour montrer que Marea peut réduire l'empreinte mémoire de 25% et jusqu'à 40%. / During the execution of object-oriented applications, several millions of objects are created, used and then collected if they are not referenced. Problems appear when objects are unused but cannot be garbage-collected because they are still referenced from other objects. This is an issue because those objects waste primary memory and applications use more primary memory than what they actually need. We claim that relying on operating systems (OS) virtual memory is not always enough since it is completely transparent to applications. The OS cannot take into account the domain and structure of applications. At the same time, applications have no way to control nor influence memory management. In this dissertation, we present Marea, an efficient application-level virtual memory for object-oriented programming languages. Its main goal is to offer the programmer a novel solution to handle application-level memory. Developers can instruct our system to release primary memory by swapping out unused yet referenced objects to secondary memory. Marea is designed to: 1) save as much memory as possible i.e., the memory used by its infrastructure is minimal compared to the amount of memory released by swapping out unused objects. 2) minimize the overhead i.e., the swapping process is fast enough to avoid slowing down applications’ primary computations. 3) allow the programmer to control or influence the objects to swap. Besides describing the model and the algorithms behind Marea, we also present our implementation in the Pharo programming language. Our approach has been qualitatively and quantitatively validated. Our experiments and benchmarks on real-world applications show that Marea can reduce the memory footprint between 25% and 40%.

We say a program is data-independent with respect to a data type X if the operations it can perform on values of type X are restricted to just equality testing, although the system may also input, store and move around (via assignment) values of type X within its variables. This property can be exploited to give procedures for the automatic verification, called model checking, of such programs independently of the instance for the type X. This thesis considers data-independent programs with arrays, which are useful for modelling memory systems such as cache protocols. The main question of interest is the following parameterised model-checking problem: whether a program satisfies its specification for all non-empty finite instances of its types. In order to obtain these results, we present a UNITY-like programming language with arrays that is suited to the study of decidability of various modelchecking problems, whilst being useful for prototyping memory systems such as caches. Its semantics are given in terms of transition systems, and we use the modal μ-calculus, a branching-time temporal logic with recursion, as our specification language. We describe a model-checking procedure for programs that use arrays indexed by one data-independent type X and storing values from another Y. This allows us to prove properties about parameterised systems: for example, that memory systems can be verified independently of memory size and data values. This decidability result is shown to extend to data-independent programs with many types and multidimensional arrays which are acyclic, meaning it is not possible to form loops of types in the 'indexed by' relation. Conversely, it is shown that even reachability model-checking problems are undecidable for classes of programs that allow cyclic-array programs. We give practical motivation for these decidability results by demonstrating how one could verify a fault-tolerant interface on a set of unreliable memories, and the cache protocol in the Pentium Pro processor. Significantly, the verifications are performed independently of many of these systems' parameters. These case studies suggest two extensions to the language: an array reset instruction, which sets every element of an array to a particular value, and an array assignment or copy instruction. Both are shown to restrict decidability of model checking problems; however we can obtain some interesting decidability results for arrays with reset by restricting the number of arrays to just one, or by allowing the arrays only to store fixed finite types, such as the booleans.

La dernière génération de cartes à puce permet le téléchargement d'applications après leur mise en circulation. Outre les problèmes de sécurité que cela implique, cette capacité d'extension applicative reste encore aujourd'hui bridée par un espace de stockage adressable restreint. La thèse défendue dans ce mémoire est qu'il est possible d'exécuter efficacement des applications stockées dans la mémoire non-adressable des cartes à puce, disponible en plus grande quantité, et ce, malgré ses temps de latences très longs, donc peu favorables a priori à l'exécution de code. Notre travail consiste d'abord à étudier les forces et faiblesses de la principale réponse proposée par l'état de l'art qu'est un cache. Cependant, dans notre contexte, il ne peut être implémenté qu'en logiciel, avec alors une latence supplémentaire. De plus, ce cache doit respecter les contraintes mémoires des cartes à puce et doit donc avoir une empreinte mémoire faible. Nous montrons comment et pourquoi ces deux contraintes réduisent fortement les performances d'un cache, qui devient alors une réponse insuffisante pour la résolution de notre challenge. Nous appliquons notre démonstration aux caches de code natif, puis de code et méta-données Java et JavaCard2. Fort de ces constats, nous proposons puis validons une solution reposant sur une pré-interprétation de code, dont le but est à la fois de détecter précocement les données manquantes en cache pour les charger à l'avance et en parallèle, mais aussi grouper des accès au cache et réduire ainsi l'impact de son temps de latence logiciel, démontré comme son principal coût. Le tout produit alors une solution efficace, passant l'échelle des cartes à puce. / The latest generation of smart cards allows to download applications after they are released. In addition to new security issues, this ability still remains constrained by a limited addressable storage space. The claim of our thesis is that it is possible to efficiently execute applications stored in the non-addressable memory of smart cards, available in larger quantities, and, despite its very long latency. Our work is first a study of the strengths and weaknesses of the main solution provided by the state of the art : caching. However, in our context, it can be implemented only in software,then with an additional latency. In addition, the cache must comply with memory constraints of smart cards and must then have on a low memory footprint. We show how and why these two constraints greatly reduce the performance of a cache, that finally becomes inadequate to fully tackle our challenge. We apply our demonstration to native instructions caches, then to Java/JavaCard2 instructions and metadata caches. Based on our observations, we propose and validate a solution based on a code pre-interpretation, whose purpose is to early detect of missing data in the cache to fetch them in advance, then to group accesses to the cache in order to reduce the impact of its software latency, that we demonstrate to be its main cost. Our result is an effective solution, that fits smart cards size and constraints.

Οι μνήμες αποτελούν την κύρια ανησυχία σε αρχιτεκτονικές χαμηλής κατανάλωσης και υψηλών ταχυτήτων. Σε έναν επεξεργαστή SOC (System on chip)περιορίζουν τις περισσότερες φορές την ταχύτητα και αποτελούν το κύριο μέρος της κατανάλωσης ενέργειας.Διάφορες τεχνικές έχουν προταθεί για τη μείωση της ισχύος σε κρυφές μνήμες. Στην παρούσα εργασία παρουσιάζονται τεχνικές μείωσης της δυναμικής ισχύος με μείωση της παράλληλης διακοπτικής δραστηριότητας. Οι τεχνικές αυτές αναπτύχθηκαν στη κρυφή μνήμη του Cellsim εξομοιωτή, βασισμένο στη λογική του Unisim εξομοιωτή, ενώ όλα τα ενεργειακά αποτελέσματα εξήχθησαν με το εργαλείο Cacti. Η εφαρμογή των συγκεκριμένων τεχνικών επέφερε σημαντικές μειώσεις στην κατανάλωση της δυναμικής ισχύος της κρυφής μνήμης για όλα τα μετροπρογράμματα που χρησιμοποιήθηκαν. / Memories are the main concern in low power and high speed architecture. In a Soc (System on chip) processor memories most of the time limit the speed and become the main part of power consumption. Various techniques have been proposed for power reduction in cache memories. In this thesis are presented different power reduction techniques by reducing parallel switching activity. These techniques were developped in the cache memory of Cellsim emulator, based on the logic of Unisim emulator, while all power results were extracted with the Cacti tool. The application of the specified techniques brought serious reductions in power consumption of cache memory for all the benchmarks that were used.

Στα πλαίσια της παρούσας διπλωματικής εργασίας υλοποιήθηκε ένας εξομοιωτής κρυφών μνημών και ένας επεξεργαστής αρχιτεκτονικής τύπου MIPS σε γλώσσα προγραμματισμού Java. Με την χρήση του εξομοιωτή και ενός αλγορίθμου πολλαπλασιασμού πίνακα επί πίνακα γραμμένο σε συμβολική γλώσσα assembly αξιολογήθηκαν τα χαρακτηριστικά των κρυφών μνημών όπως συσχετιστικότητα, μέγεθος μπλοκ, μέγεθος μνήμης και ιεραρχία μνήμης. Ως αποτέλεσμα κατασκευάστηκε ένα εργαλείο αξιολόγησης τόσο της αρχιτεκτονικής του υλικού για έναν αλγόριθμο όσο και της αποδοτικότητας ενός αλγορίθμου που εισάγεται στο πρόγραμμα για μια αρχιτεκτονική. / In the context of the current thesis a cache memory simulator was implemented with a MIPS architecture processor in Java programming language. Using the simulator and a matrix by matrix multiplication algorithm written in assembly language supported by the simulator various features of the cache memories were evaluated such as associativity, block size, memory size and memory hierarchy. As a result an evaluation tool was built, capable of evaluating not only a memory hierarchy architecture but also the efficiency of an algorithm used on a specific architecture.

Κύριος σκοπός της εργασίας είναι η υλοποίηση ενός υπολογιστικού συστήματος με Scratch pad μνήμη και η διαχείριση της μνήμης μέσω ενσωματωμένου λογισμικού. Αρχικά παρουσιάζονται τα πλεονεκτήματα και τα μειονεκτήματα ενός συστήματος που χρησιμοποιεί μνήμη Scratch pad σε σύγκριση με ένα αντίστοιχο σύστημα με cache. Μετά σχεδιάζουμε το σύστημα μας χρησιμοποιώντας την γλώσσα περιγραφής υλικού VHDL και λαμβάνουμε πειραματικές μετρήσεις οι οποίες προκύπτουν από την μέτρηση των κύκλων εκτέλεσης ενός αντιπροσωπευτικού προγράμματος. Η προτεινόμενη αρχιτεκτονική με Scratch pad και η τεχνική προγραμματισμού της αποφέρουν μια βελτίωση της απόδοσης κατά 36% σε σχέση με την αντίστοιχη αρχιτεκτονική με cache. Αυτό οφείλεται στις σημαντικά λιγότερες αστοχίες που παρουσιάζει η Scratch pad όταν προγραμματιστεί κατάλληλα καθώς ο DMA ελεγκτής έχει τη δυνατότητα να μεταφέρει τα δεδομένα παράλληλα με την εκτέλεση του προγράμματος. / The main purpose of this master thesis is the implementation of a computer system using scratch pad memory including memory management via embedded software. Initially we present the pros and cons of a system using scratch pad memory, in comparison to a system using cache memory. We then design our system using the hardware description language VHDL and we compare the performance with an equivalent architecture using cache memory. This is done by counting the clock cycles needed in order to run a sample program. The proposed scratch pad architecture and the programming technique used produced a 36% better performance in comparison to an equivalent cache memory architecture. This is due to the less misses that a scratch pad memory presents, when programmed efficiently.

Η παρούσα διπλωματική αποτελεί την προσπάθεια κατασκευής ενός cache controller βασισμένο στον AHB BUS. Η ανάπτυξή του έγινε ως επί το πλείστο στο Εργαστήριο Vlsi του τμήματος Μηχανικών Υπολογιστών και Πληροφορικής με την προοπτική να ενσωματωθεί σε ένα ευρύτερο υπάρχων σύστημα βασισμένο στον open source cpu της arm Cortex M0. Δοκιμάστηκε επιτυχώς σε FPGA του εργαστηρίου αλλά ακόμα δεν έχει χρησιμοποιηθεί σε «πραγματικές συνθήκες». Απώτερος στόχος είναι να χρησιμοποιηθεί στο εργαστήριο για την επιτάχυνση εφαρμογών που θα χρειαστούν εξωτερική μνήμη δηλ. μεγαλύτερη μνήμη από την embedded του FPGA. Αν και δεν δοκιμάστηκε σε κάποιο άλλο σύστημα έχει φτιαχτεί με γνώμονα το πρότυπο του AHB οπότε υποθετικά δεν θα έχει κάποιο πρόβλημα να ενσωματωθεί σε οποιοδήποτε συμβατό με τον δίαυλο σύστημα. Η λογική πίσω από την υλοποίηση του είναι να είναι σχετικά εύκολη η αλλαγή ορισμένων μεταβλητών ώστε να διαφοροποιείται ο controller βάση των αναγκών του καθενός. Οι προδιαγραφές δίνονται παρακάτω αν και πιθανόν εκτός των πλαισίων της διπλωματικής και εντός του 2014 να επανα-σχεδιαστεί ώστε να γίνει πλήρως modular. / Cache controller compatible with AHB bus in system Verilog.

Στην παρούσα διπλωματική εργασία θα ασχοληθούμε με το πρόβλημα της αξιοπιστίας των κρυφών μνημών δεδομένων και εντολών πρώτου επιπέδου. Η υψηλή πυκνότητα ολοκλήρωσης και η υψηλή συχνότητα λειτουργίας των σύγχρονων ολοκληρωμένων κυκλωμάτων έχει οδηγήσει σε σημαντικά προβλήματα αξιοπιστίας, που οφείλονται είτε στην κατασκευή, είτε στη γήρανση των ολοκληρωμένων κυκλωμάτων. Στην παρούσα εργασία γίνεται αρχικά μια αποτίμηση της μείωσης της απόδοσης των κρυφών μνημών πρώτου επιπέδου όταν εμφανίζονται μόνιμα σφάλματα για διαφορετικές τεχνολογίες ολοκλήρωσης. Στη συνέχεια παρουσιάζεται μια νέα τεχνική αντιμετώπισης της επίδρασης των σφαλμάτων, η οποία βασίζεται στη πρόβλεψη της χωρικής τοπικότητας των μπλοκ μνήμης που εισάγονται στις κρυφές μνήμες πρώτου επιπέδου. Η αξιολόγηση της εν λόγω τεχνικής γίνεται με τη χρήση ενός εξομοιωτή σε επίπεδο αρχιτεκτονικής. / In this thesis we will work on the problem of reliability of first-level data and instruction cache memories. Technology scaling improvement is affecting the reliability of ICs due to increases in static and dynamic variations as well as wear out failures. First of all, in this work we try to estimate the impact of permanent faults in first level faulty caches. Then we propose a methodology to mitigate this negative impact of defective bits. Out methodology based on prediction of spatial locality of the incoming blocks to cache memory. Finally using cycle accurate simulation we showcase that our approach is able to offer significant benefits in cache performance.

Στη σύγχρονη εποχή το κενό απόδοσης μεταξύ του επεξεργαστή και της μνήμης ενός σύγχρονου υπολογιστικού συστήματος συνεχώς μεγαλώνει. Είναι λοιπόν σημαντικό να ερευνηθούν νέοι τρόποι για να καλυφθεί η αδυναμία της κύριας μνήμης να ακολουθήσει τον επεξεργαστή. Η μνήμη cache ήταν ανέκαθεν ένα χρήσιμο εργαλείο προς αυτήν την κατεύθυνση. Χρειάζεται όμως πλέον να προχωρήσει πέρα από την απλοϊκή μορφή της και τον αλγόριθμο LRU Η παρούσα διπλωματική έχει σαν σκοπό την μελέτη της cache σε πραγματικό περιβάλλον και την ανάλυση της δυνατότητας και της χρησιμότητας της πρόβλεψης της συμπεριφοράς ενός σύγχρονου προγράμματος όσον αφορά την προσπέλαση της μνήμης. Η εργασία επικεντρώνεται στην χρήση τεχνικών dynamic instrumentation για την υλοποίηση ενός μηχανισμού πρόβλεψης της απόστασης επαναχρησιμοποίησης μιας θέσης μνήμης, μέσω της ανάλυσης και μελέτης της συμπεριφοράς της εντολής, που ζητά να προσπελάσει την συγκεκριμένη θέση μνήμης. Αναλύεται εκτενώς η λειτουργία ενός τέτοιου μηχανισμού και παρέχονται στατιστικές μετρήσεις που επιβεβαιώνουν την χρησιμότητα και ευστοχία μιας τέτοιας πρόβλεψης. / In contemporary times the performance gap between the CPU and the main memory of a modern computer system grows larger. So it is important to find new ways to cover the inability of the main memory to cope with the CPU’s performance. Cache memory has always been a useful tool towards this goal. However the need arises for it to move beyond simplistic implementations and algorithms like LRU. The present end year project aims towards the study of cache memory in a real time environment and the analysis of the capability and usefulness of prediction of the memory access behaviour of a modern program. The thesis puts weight on the use of dynamic instrumentation techniques for the creation of a prediction mechanism of the reuse distance of a memory address, through the analysis and study of the behavior of the instruction that accessed this memory address. The function of such a mechanism is analyzed in depth and statistical measures are provided to prove the usefulness and accuracy of such a prediction.