Improving the JCilk-1 Compiler and Runtime System
Authors
B. Christensen, Allan ; Skou, Martin ; S. Stilling, Per
Term
2. term
Education
Publication year
2009
Pages
91
Abstract
Dette speciale undersøger, hvordan man bedst understøtter samtidighed—at flere opgaver kører parallelt for hurtigere og mere responsive programmer—i objektorienterede sprog. Det bygger på et forstudie af C#, Cilk, Fortress og Scala, hvor vi fandt, at Cilks principper som work-stealing (ledige tråde tager arbejde fra travle) og spawn/sync (starte og afvente delopgaver) giver en god balance mellem det, programmøren selv beskriver, og det sproget håndterer automatisk. På denne baggrund gennemgår vi beslægtede løsninger: JCilk (en Java-udvidelse med Cilk-ideer), Java Fork/Join-frameworket (baseret på work-stealing og fork/join, dvs. at dele arbejdet op og samle resultaterne), C# Task Parallel Library (som også understøtter futures, dvs. pladsholdere for resultater, der kommer senere) og Googles MapReduce (inspireret af map og reduce fra funktionel programmering). Vi vælger at arbejde videre med JCilk, fordi de nye Java- og C#-biblioteker stadig var under udvikling, og fordi MapReduce’s abstraktion ikke passede til vores mål. JCilk er en sproglig udvidelse, der bringer Cilk til et objektorienteret miljø, hvilket stemmer med projektets retning. Vi analyserer den aktuelle version, JCilk-1, og identificerer større forbedringsmuligheder: ensrettet integration med Java (man kan ikke kalde JCilk fra Java-kode), en sandsynligvis unødvendig todelt kompileringsproces, manglende udnyttelse af nyere Java-funktioner samt performance-tab på grund af hyppig objektallokering og synkronisering i runtime-systemet. Vi implementerer to forbedringer: 1) vi fjerner det sidste kompileringsskridt ved at omsætte de anvendte goto-udsagn og labels til ren Java-kode, så det særlige GoJava-trin ikke længere kræves, og 2) vi reducerer omkostningerne ved objektallokering ved at genbruge objekter, så færre overgår til garbage collectoren. Testene viser, at fjernelsen af GoJava-trinnet ikke har negativ effekt, og at genbrug af objekter forbedrer JCilks ydeevne markant. Samlet set har vi gennemført to ændringer, der væsentligt forbedrer JCilk.
This thesis explores how to best support concurrency—running multiple tasks in parallel for faster and more responsive programs—in object-oriented languages. It builds on a prior study of C#, Cilk, Fortress, and Scala, where we found that Cilk’s principles such as work-stealing (idle threads take work from busy ones) and spawn/sync (start and wait for subtasks) strike a good balance between what programmers specify and what the language handles implicitly. Based on this, we review related solutions: JCilk (a Java extension with Cilk ideas), the Java Fork/Join framework (based on work-stealing and fork/join, i.e., splitting work and joining results), the C# Task Parallel Library (which also supports futures, placeholders for results available later), and Google’s MapReduce (inspired by map and reduce from functional programming). We choose to continue with JCilk because the new Java and C# libraries were still under development, and because MapReduce’s abstraction did not align with our goals. JCilk is a language extension that brings Cilk to an object-oriented setting, matching the project’s direction. We analyze the current version, JCilk-1, and identify major opportunities: one-way integration with Java (JCilk cannot be called from Java code), a likely unnecessary two-stage compilation process, limited use of newer Java features, and performance costs from frequent object allocation and synchronization in the runtime. We implement two improvements: (1) remove the final compilation step by translating the used goto statements and labels into plain Java code, eliminating the need for the GoJava step, and (2) reduce allocation overhead by reusing objects so fewer are handled by the garbage collector. Tests show that removing the GoJava step has no notable negative impact, and that object reuse significantly improves JCilk’s performance. Overall, we deliver two changes that substantially improve JCilk.
[This abstract was generated with the help of AI]
Documents