Improving the JCilk-1 Compiler and Runtime System

Student thesis: Master thesis (including HD thesis)

  • Allan B. Christensen
  • Martin Skou
  • Per S. Stilling
2. term, Computer Science, Master (Master Programme)
Denne rapport omhandler arbejdet på speciale semestret udført af Allan B. Christensen, Martin Skou og Per S. Stilling på Institut for Datalogi på Aalborg universitet i forskningsenheden Database- og programmeringsteknologier. Specialet bygger på et forspeciale der undersøgte fire forskellige sprog, C#, Cilk, Fortress and Scala, der hver især håndterer understøttelse af samtidighed på forskellige måder. Konklusionen af undersøgelsen var, at de principper der ligger til grund for den til dels implicitte samtidghed som Cilk understøtter igennem work-stealing og dens spawn/sync syntaks, giver et passende kompromis mellem hvad programmøren skal definere og hvad der implicit skal håndteres af programmeringssproget. I specialet har vi valgt at kigge videre på sprogkonstruktioner og systemer der minder om dem brugt i Cilk, for at finde et objekt orienteret sprog eller bibliotek som vi kan arbejde videre på, eller inspirere os fra i opbygningen af et nyt objektorienteret system. Udover Cilk, gennemgår vi fire sprog som vi mener kan inspirere til vores arbejde i dette semester; JCilk, en Java implementation af principperne brugt i Cilk, Java Fork/Join Frameworket, et Java-bibliotek opbygget på mange af de samme principper der er brugt i Cilk og JCilk, såsom work-stealing og fork/joining af beregningerne, C#’s nye Task Parallel Library, et bibliotek til C# som ligeledes bygger på principperne bag Cilk samt understøttelse af andre samtidighedskonstruktioner såsom futures, og til sidst Googles MapReduce framework, der bygger på lidt anderledes principper idet det i høj grad er inspireret af at parallelisere MapReduce operationen fra funktionelle sprog. Efter undersøgelsen af de eksisterende lignende systemer på området, vælger vi at fortsætte arbejdet på JCilk frameworket. Det vælges ud fra den iagtagelse at både Java og C#’s to nye biblioteker er under udarbejdning for øjeblikket og arbejde inden for disse rammer er derfor uhensigtsmæssigt. Abstraktionen som MapReduce frameworket tilbyder, bliver vurderetsom værende på et for lavt niveau i forhold til vores mål. JCilk frameworket stemmer derimod overens med de egenskaber vi foretræker i forbindelse med valg af et system, som vi kan arbejde videre på; det er en sprog udvidelse, hvilket giver et alternativ til de biblioteker som der bliver arbejdet på hos Microsoft og Sun, og systemet er en direkte udbygning af Cilk i et objektorienteret sprog, hvilket passer med målet for projektet. Efter valget af JCIlk, er næste skridt at undersøge den nuværende status af JCIlk-1, som det nuværende system kaldes. Et antal af forslag til forbedring og/eller observeringer af nuværende mangler i systemet bliver identificeret, både på baggrund af gruppens egne iagtagelser og baseret på de forslag der bliver givet i de rapporter der er udgivet i forbindelse med JCilk. Der bliver i forbindelse med denne del af rapporten fremlagt følgende større problemer med det nuværende system; sammenhængen mellem JCilk og Java er på nuværende tidspunkt kun en-vejs og det er ikke muligt at kalde JCilk fra Java kode, det bliver endvidere identificeret at den nuværende to-dels kompileringsprocess formodentligt er unødvendig. En anden optimering der kan laves til det nuværende system er at bruge nogle af de mere moderne sprog funktionaliteter i Java, der er introduceret efter 2004. Det sidste større problem som bliver identificeret, er at systemets performance på nuværende tidspunkt bliver svækket meget af objekt allokeringen og synkroniseringen i JCilks runtime system. Vi vælger at implementere to af disse forbedringer; afskaffelse af det sidste skridt i kompileringsprocessen af JCIlk, og optimering af den nuværende allokering i systemet. Forbedringen af allokeringen i JCIlk bliver realiseret ved at modificere JCIlk således, at de objekter der ikke længere er i brug bliver gembrugt i stedet for at lade dem blive fanget af garbage collectoren. Den anden forbedring, som består i at eliminere nødvendigheden af sproget GoJava i kompileringsprocessen, bliver implementeret ved at omdanne de goto statements og labels der bliver brugt i systemet til Java kode. Den vigtigste faktor i forbindelse med en test af begge forbedringer er hvorvidt de har forårsaget en betydelig ændret i JCilks ydeevne. Der bliver derfor efter implementationen, lavet en test af den ændring som begge forbedringer har forårsaget i systemet. Konklusionen er, at elimineringen af GoJava ikke har haft bemærkelsesværdig negativ betydning. Det påvises endivdere at elimineringen af den høje objektallokerings frekvens har forbedret ydeevnen i JCilk betydeligt. Konklusionen af projektet er, at vi med succes har lavet to forbedringer til JCilk som begge har forbedret systemet betydeligt.
LanguageEnglish
Publication date2009
Number of pages91
Publishing institutionAalborg University, Department of Computer Science
ID: 17683011