Just-in-Time Data Structures

Project Details

Description

While software applications have become larger and more complex with huge data sets, hardware has moved to multicore machines that are limited by memory access speed. Because of application phase behavior, each data structure can have different optimal data representations, or layouts, depending on its algorithms and data usage, at different program points. We propose Just-in-Time Data Structures (JIT DS), which will alleviate the need for the programmer to manually change representations or delineate phases; the underlying language virtual machine will monitor data structures and automatically decide when to transition to another data representation for optimal performance and memory efficiency. JIT DSs coordinate across the system stack, including communication from the application level and the software library level to the language virtual machine level, which will read hardware performance counters as part of its monitoring. The software engineer can insert declarative hints to guide transitions. Our JIT DS libraries will include annotations or predicates indicating behavior more conducive to a particular representation. The virtual machine will perform low-overhead profiling of data structure behavior to inform a data layout change. We will use JIT DSs to optimize application execution time and memory access latency, which is timely as there are more non-expert programmers, and as computer systems seek new holistic solutions to deal with hitting physical limits.

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.
AcronymFWOAL792
StatusFinished
Effective start/end date1/01/1631/12/19

Keywords

  • data structures
  • computer technology

Flemish discipline codes

  • Other computer engineering, information technology and mathematical engineering not elsewhere classified