Dynamic Management and Optimization of Program Code for Embedded Systems

Bei Desktop-PCs ist ein großer Hauptspeicherausbau im Bereich jenseits von 1 GB dank gesunkener Speicherpreise und auf Grund gestiegener Anforderungen keine Seltenheit mehr. Es existiert jedoch eine Unmenge Kleinstrechner, wie z.B. im Automobilbereich eingesetzte Steuergeräte, die sich einen großen Speicherausbau wegen des Platzbedarfs der Speicherchips, deren Energiekonsum und den zusätzlichen Kosten nicht leisten können. Ein wichtiges Ziel beim Erzeugen der Software für eingebettete Systeme ist es also, so wenig Hauptspeicher (RAM) wie möglich zu verbrauchen. Als Entwickler steht man demnach ähnlichen Problemen gegenüber wie die Computer-Pioniere in den 1970er und 1980er Jahren. Jedoch haben Lösungen wie Overlays oder die von Betriebssystemen eingesetzte seitenbasierteSpeicherverwaltung den Nachteil, dass sie den Speicher sehr grobgranular verwalten. Dadurch wird häufig Maschinen-Code in den Arbeitsspeicher geladen, der nicht ausgeführt wird und somit die Effizienz des Speichers herabgesetzt. Der Beitrag dieser Arbeit besteht in einer neuen Form der Speicherverwaltung für Programm-Code. Unser dynamischer Code-Lader (DCL), lädt nur Programm-Code in den Arbeitsspeicher, der unbedingt zur Ausführung einer Anwendung notwendig ist. Dazu wird der Code in Einheiten von Grundblöcken geladen. Diese sind Code-Regionen mit nur jeweils einem Ein- und Ausgang, d.h. wird ein Grundblock betreten, wird er auch garantiert vollständig ausgeführt. Sollte der zur Verfügung stehende Arbeitsspeicher trotzdem nicht ausreichen, verdrängt ein Speicherbereiniger nicht mehr benötigte Grundblöcke aus dem Speicher, wodurch wieder Platz für neue entsteht. Im Laufe der Arbeit wurden je ein Prototyp des Programmladers für die Intel x86-, die ARM-Architektur und IBMs Cell B.E. entwickelt, sowie mehrere Speicherbereiniger-Techniken untersucht. Des Weiteren wurde mit unterschiedlichen Ladegranulatgrößen experimentiert, wobei neben Grundblöcken auch Funktionen betrachtet wurden. Die Evaluation des Programmladers für ARM zeigt, dass eine Speicherersparnis von 64% erzielt werden kann, wobei in manchen Fällen Laufzeitgewinne von bis zu 3% erzielt wurden und die maximalen Laufzeiteinbußen 17% betragen.Due to the low production costs and increased demand on performance, today's desktop computers commonly are fitted with main memory larger than one gigabytes. However, small embedded systems like microcontrollers in vehicles can't afford the increased costs associated with the increased size and energy consumption of larger memories. The main issue of this thesis is to minimize the code footprint (i.e. RAM usage) of the software run on embedded systems. Developers in this field have to tackle the same problems as the computer pioneers from the 1970ies and 1980ies. Unfortunately, solutions like overlays and the more recent virtual memory bear the disadvantage that they manage the main memory with very coarse granularity. This has the side effect that usually more program code is brought into the main memory than actually needed for the program's execution. Consequently, the main memory's efficiency decreases because it can't be used for data. The main contribution of this dissertation is a novel kind of memory management for program code based on our specialised program loader, Dynamic Code Loader (DCL), only loads portions of code into main memory that are absolutely necessary to execute the program. To do so, the code is loaded with the granularity of basic blocks. Since such code regions have a single entry and a single exit point, we can always asure that once a basic block is entered, it is executed completely. In case the memory is too small, DCL's garbage collector removes basic blocks that are no longer needed for the program's execution. Afterwards DCL can load new blocks and so forth. In this thesis we developed prototypes of DCL for the Intel x86, ARM, and IBM's Cell B.E. architectures. We also investigated several techniques of garbage collection and experimented with different granularites of the code fragments to be loaded. We conclude that using functions instead of basic blocks improves performance and decreases the memory consumption, as well. The evaluation of our program loader showed that we can save up to 64 per cent of main memory and in some cases the runtime even decreased by 3 per cent compared to running the software without DCL. The maximum runtime overhead is 17 per cent