Dynamische datastructuren (FWOAL822)

Softwaretoepassingen worden steeds groter en complexer, naarmate de data waarmee ze werken in grootte toeneemt. Om dit mogelijk te maken, maakte men aan de hardwarekant de overstap naar machines met meerdere processorkernen ("multicore"). Bij deze machines is de limiterende factor vaak de snelheid waarmee het werkgeheugen aangesproken kan worden. Dit leidt er toe dat de optimale representatie (of "layout") van datastructuren verschilt afhankelijk van het gebruikspatroon. Softwaretoepassingen vertonen vaak een verschillend gebruikspatroon voor bepaalde datastructuren gedurende verschilllende fasen van hun uitvoering. Om hieraan tegemoet te komen, stellen we Just-in-Time DataStructuren (JIT DS) voor. Deze abstractie automatiseert het dynamisch wijzigen van representaties, en het afbakenen van verschillende fasen binnen een softwaretoepassing. Bij JIT DS monitort de onderliggende virtuele machine datastructuren, en beslist deze wanneer een transitie naar een andere representatie gemaakt moet worden om de optimale balans tussen snelheid en geheugengebruik te bereiken. De herkenning van gebruikspatronen in JIT DS maakt zowel gebruik van de logica uitgedruk in de applicatiecode en de gebruikte softwarebibliotheken, alsook van algemene metrieken die door de virtuele machine uitgelezen kunnen worden, zoals de performance counters die in hardware geimplementeerd zijn. De virtuele machine zal aan de hand van deze informatie zonder grote meerkost gebruikspatronen kunnen detecteren, en wijzigingen aan de representatie terwerkstellen. De automatische detectie en transitie kan bijgestuurd worden door expertkennis, dewelke als declaratieve hints in de broncode toegevoegd kan worden. De JIT DS softwarebibliotheken zullen reeds annotaties en predicaten bevatten die hierbij helpen. We zullen JIT DS gebruiken om de uitvoeringstijd van softwaretoepassingen te verkorten, en de aanspreektijd ("latency") van werkgeheugen te verlagen. Centraal aan de relevantie van JIT DS staat de notie dat vele programmeurs weinig expertise hebben in het bepalen van de optimale representatie van een datastructuur voor een bepaalde hardwareimplementatie, en dat een optimale representatie verschilt van implementatie tot implementatie. Het loskoppelen van enerzijds applicatielogica en anderzijds het gebruiken van de optimale layout in iedere fase van de uitvoering van een softwaretoepassing, biedt daardoor een sterke meerwaarde.

Trefwoorden:Just-in-Time Data Structures

Disciplines:Systeemtheorie, -modellering en -identificatie