Stefan-Marr.de

The third day started with Brendan Eich’s keynote on JavaScript’s world domination plan. It was a very technical keynote, not very typical I suppose. And he was rushing through his slides with an enormous speed. Good that I have some JavaScript background. Aside all the small things he mentioned, interesting for me is that he seemed to be very interested to get Intel’s RiverTrail approach to data-parallelism into ECMAScript in one or another form. That is kind of contradicting the position I heard so far, that ECMAScript would be done with having WebWorkers as a model for concurrency and parallel programming.

Language Implementation

The first session had two interesting VM talks for me. The first being JIT Compilation Policy for Modern Machines. With the assumption that you cannot get your multicore/manycore machines busy with application threads, they experimented how additional compilation threads can be used to optimize code better. I do not remember the details completely, but I think, after 7 compilation threads they reached a mark where it was not worthwhile anymore to add more threads.

The second talk was on Reducing Trace Selection Footprint for Large-scale Java Applications with no Performance Loss. The goal here is to reduce the number of trace in a tracing JIT that need to be kept around and optimized. Might be something interesting for PyPy and LuaJIT2 to consider.

Parallel and Concurrent Programming

The last session I attended was again on parallel and concurrent programing. The first paper A Simple Abstraction for Complex Concurrent Indexes was a pretty formal one.

The second paper is a pessimistic approach to implement atomic statements meant for systems programming: Composable, Nestable, Pessimistic Atomic Statements. It is not optimistic like STM, and does not use a global locking order, which would need to be determined statically. Instead they annotate the fields with so-called shelters. Shelters build a hierarchy, which describes the necessary parts to synchronize with.

The third paper was also a very interesting one for me: Delegated Isolation. It is an approach again similar to STM in a sense, but it avoids unbounded number of transaction retries. For that, the object graph is essentially partitioned in growing subgraphs that can be processed in parallel. Only when a conflict, a race-condition occurred, subgraphs are merged logically, and the computation is serialized. A neat idea and an interesting use of the object-ownership idea.

The last talk was on: AC: Composable Asynchronous IO for Native Languages. It was a presentation of work done in the context of the Barrelfish manycore OS. The goal was to have an easy to use programming model, that comes close to sequential programming, but has similar performance properties as typical asynchronous APIs in operating systems. The result is a model based on async/finish, that seems to be relatively nice. As I understand it, it is basically syntactic sugar and some library support to wrap typical asynchronous APIs. But it is a model that is purely focused on such request/response asynchrony, and does not handle concurrency/parallism.

And that was basically it. SPLASH is a nice conference when it comes to the content. Not so interesting when it comes to the social “events”, it wasn’t much of an event anyway. Not even the food was notable…

The second day of the technical tracks started with a keynote by Markus Püschel. He is not the typical programming language researcher you meet at OOPSLA, but he does research in automatic optimization of programs. In his keynote, he showed a number of examples how to get the best performance for a given algorithm out of a particular processor architecture. Today’s compilers are still not up to the task, and will probably never be up to it. Given a naïve implementation, hand-optimized C code can have 10x speedup when dependencies are made explicit, and the compiler knows that no aliasing can happen. He was then discussing how that can be approached in an automated way, and was also thinking about what programming languages could do.

Award Papers

Afterwards, I attended the session with the awarded OOPSLA papers. The Hybrid Partial Evaluation talk presented an approach to avoid the typical cost of use of reflection or ‘interpretation’. The presentation of SugarJ: Library-based Syntactic Languages felt like a déjà vu. I did not get where it is different from Helvetica other than that it is for Java. The third paper on Reactive Imperative Programming with Dataflow Constraints was interesting in that it used also memory protection tricks to realize a reactive model in C++. The last presentation: Two for the Price of One: A Model for Parallel and Incremental Computation was very interesting. I have not used incremental computations as far as I am aware of anywhere other than for course work, but bringing it together with parallel programming in a single programming model, gives plenty of opportunities for super-linear speedups.

Parallel and Concurrent Programming

The second session of the day was on parallel and concurrent programming. Kismet: Parallel Speedup Estimates for Sequential Programs tackled the problem to get an idea of what opportunities for parallelism are available in a given program without having to change the used algorithms and approaches to much. For that, it uses data dependency analysis to characterize the critical path on a data-flow level. Since that usually does not give realistic results because of overestimation of parallelizability, they use in addition a hierarchical model of loops and the knowledge of the available hardware parallelism to better predict possible speedups.

The second and the third talk where almost identical in terms of problem and goal. Essentially, they provide the necessary infrastructure to run different variants of sequential implementations in parallel and then chose either the winner in terms of runtime or precision. These approaches are especially interesting if the available algorithms have very different properties for different input or input sizes. For instance, some mathematical algorithms just do not converge to a solution for certain inputs while they are very fast for others.

The last talk of the session discussed Scalable Join Patterns. Join patterns are an old approach to describe synchronization mechanism flexibly and declaratively. The presented work provided a scalable implementation approach that seems to work quite well and when they would use a compilation based approach for the patters, I guess it could be a very feasible and flexible replacement for standard synchronization mechanism provided as libraries.

Panel

Instead of attending the third paper session of the day, I attended the panel on Multicore, Manycore, and Cloud Computing: Is a new Programming Language Paradigm required?. Well, it was entertaining Nothing really new, no surprising arguments as far as I recall, but certainly interesting to watch. I think, they also recorded it. So it might be floating around the web soon.

The second conference day was unfortunately full of “conflicts of interest”… It was pretty hard to choose between all the talks on the schedule.

Beside DLS and VMIL, there was also a workshop on Actor systems. However, I did not make it to this one. Cherry picking between DLS and VMIL was already hard enough and worked out only partially.

The two DLS keynotes were certainly highlights of the whole SPLASH conference. Gilad’s talk, on Dart was not just interesting but quite entertaining; especially their take on the optional type system looks useful. I like the reasoning behind their approach a lot. Who needs sound type systems anyway? Well, then again, I had a few bugs were a complete type system could have notified me earlier to make me aware that I am doing something stupid. So, I wonder whether it would be hard to have another optional type system in addition, which could be enabled on demand for certain modules to check a more strict set of constraints?

The second DLS keynote was David’s presentation with the title: “Everything You Know (About Parallel Programming) is Wrong!: A Wild Screed About the Future”. The main conclusion is certainly that Romeo would not have died when there would have been synchronization to avoid the race condition. What a nerdy example

In the end, the parallel revolution will need to find the balance between performance and correctness, since correctness is always bought by introducing delays and thus hampers performance. Another point he made more implicitly is that programming these systems becomes not only harder because of the parallel aspect, but also because of the ever-growing complexity of the underlying hardware. We just do not know anymore what is going on and why the performance is not as expected.

The VMIL workshop started with Eliot’s presentation. But, well, if you know how Eliot presents his work on the Cog VM then you know, that it is likely that people not acquainted with the details of Smalltalk VMs have a very hard time to follow. His paper made the message a bit clearer, I think. His main point was the VM integration of the Bochs processor emulator for debugging.

After the first break, Lars talked a bit too much about Dart as a language, and the VM details were rather scarce. They said that they are going for simplicity, and the one aspect that I remember was that they do not have any static initialization to avoid ‘spontaneous’ executions. And well, their Smalltalk and Java history certainly shows between the lines.

The talk titled “Virtual machines should be invisible” was essentially about how to build a VM that reuses the standard systems ABI to integrate better with the surrounding system. They use the DWARF debugging format and dynamic linking techniques to reach that goal. Interesting but not platform-independent and I do not really see why that would be desirable or necessary for what I consider a VM.

I unfortunately missed the talk on “A Microbenchmark Case Study and Lessons Learned”. From the comments made later in the workshop, it seemed to have been an interesting and very relevant talk.

The talk titled “Intermediate Language Extensions for Parallelism” was interesting, but I found that this IL is rather language dependent and is only applicable for a X10 or Habanero-ish language. Sure, the Cilk-style seems to be useful for a number of parallel problems, but it is not the only paradigm out there, so I wonder how that IL would look like if it would be designed for a multi-language VM.

The last talk of the workshop was mine: Which Problems Does a Multi-Language Virtual Machine Need to Solve in the Multicore/Manycore Era? So, if you have any answers or thoughts on that topic, please leave me a note.

Tuesday – Evolution, Onward!, FPGAs, and the Hera-JVM

On Tuesday the main conference started with its keynotes and research tracks.

The keynote of Stephanie Forrest was an interesting introduction to how evolutionary approaches could be used in software development. One goal they are currently pursuing is fixing of certain types of bugs by reordering, deleting, and/or copying of parts in an AST. Well, that can not fix every bug, but might be interesting for many typical problems. Certainly the type of bugs I run into most frequently…

Onward! started with three interesting talks in the area of languages. The first on Registration-Based Language Abstractions presented an IDE approach to bringing high-level constructs to existing code-bases. You basically have an “imaginary” view only present in your IDE of what the low-level implementation details actually are meant to represent. Examples were simple standard Java for-loops using C-like notation getting replaced by for-each loops, or even whole class bodies getting simplified by abstracting from typical getter/setter patterns, or even delegation patterns. Neat!

Toon’s talk on Pinocchio: Bringing Reflection to Life with First-Class Interpreters advocated fully reflective systems that make it easy to build bug-specific debuggers. Thats a great idea, unfortunately not feasible in VMs which are not build in a meta-circular fully reflective way, I think. We definitely need something more sophisticated for RoarVM than printf…

The last talk on this track was on Concurrency by Modularity: Design Patterns, A Case in Point. Well, on the one hand I agree, there are certain design patterns from the gang of four which can be parallelized, however, that does not solve the problem of share state… The point that increased modularity will increase you degree of possible parallelism might be appealing but it is only a correlation and not a strict causal relationship.

The presentations after lunch were addressing performance from the angle of FPGAs. The presentation on Lime: a Java-Cpmpatible and Synthesizable Language for Heterogenous Architectures made a case for object-oriented programming for FPGAs. The idea is to have a superset of Java, with a few additional keywords, that is than mappable to hardware. As far as I understood, Lime is basically a stream-based language and thus favors data-oriented programming. The second talk was titled From OO to FPGA: Fitting Round Objects into Square Hardware? Interesting for me were the challenges they had to overcome to actually implement an OO language on top of an FPGA. The problem is mainly today’s available tool chains, that usually support only a very restricted subset of C.

The second session in the afternoon included the most related talk to my own research, a presentation on a port of the JikesRVM to the Cell processor: Hera-JVM: A Runtime System for Heterogeneous Multi-Core Architectures. The heterogenous instruction set was not the biggest challenge here, but the restricted local memory of the SPEs required them to pull a few tricks. Not only the size, but also the non-shared memory approach gave problems. To support the full semantics of the JMM, they had to implement a coherence mechanism in software. Have seen something similar for the read-mostly heap in our RoarVM before

Afterwards, I arranged the necessary details for our Birds of a Feather meeting on Non-deterministic Programming.

Wednesday – Assertions tested by the GC, Dynamic Parallelization

On the OOPSLA track, I followed a talk on What Can the GC Compute Efficiently? This was an interesting talk, since I haven’t heard about anything similar before. The general idea is, that the GC supports an assertion system which allows to express a certain number of directly determinable properties. While the GC is doing its normal job, it can also check those assertions and verifies the described invariants almost for free. Again, neat Of course, the system has certain restrictions and the assertion language basically needs to ensure that the assertions can be checked in a single pass.

In the second session, Charlotte gave her talk on Dynamic Parallelization of Recursive Code. Have seen a presentation on her idea before, so most of the time I was think how could that be made fast. Would be great if she would purse the same idea in a Tracing JIT setting *sigh* Just for the fun of it, I suppose I bet there could be something in the idea of moving all the tracing, branch-prediction and speculative execution out of the CPU into the software. If they are really going for dump and small cores in the many-many-core world, we could squeeze at least some speedup out of those sequential algorithms. See the workshop paper by András Vajda and Per Stenström. Cool stuff, all that automatic parallelization non-sense with out the speculating part won’t work anyway

Thursday – Search without Objectives,

The day started with a very interesting keynote. The take-away point is, if your goal is not reachable in a number of steps you can already predetermine, i.e., if you don’t have all the basic ingredients, than the typical goal-driven search approaches do not deliver good results. Instead of using a metric of whether your search brings you closer to your goal, you should us a metric that rewards novelty, interestingness, or just the differentness from the points you have reached in your search before. Searching with such a metric leads much more probable and typically a lot faster towards your initial goal. Kenneth Stanley present a number of very convincing arguments, but in the end he had also to admit that this approach is somehow constraint in its applicability by the rules of society. But at least we should try. So, on to something new!

The second keynote of the day was a bit too, ehm, applied? Well, it was certainly interesting to see what the influence of the F# team was on the .NET platform, but well, there was not really meat in that talk. From a theoretic perspective the CIL of .NET appeals to me much more than the JVM Bytecode set, but well, he was not talking about such low-level questions…

Afterwards, I followed the last OOPSLA session. Mainly out of curiosity what ownership types are all about. Now I have seen three talks, and can be reassured, they are not relevant for my VM design. Good. Well, the point is, such a type system just does not fit with a VM. Dynamic languages can not be sensibly compiled to such a type system, I think. Thats more a gut feeling than a great insight, but I don’t see how they match.

The last session of SPLASH for me was the short paper session of the Onward! track. It started very interesting with an experiment on how performance metrics can be turned to sound: Sonifying Performance Data to Facilitate Tuning of Complex Systems. I should try that for our VM, any approach is better than the one I use now… no at all *sigh* Well, our boids simulation already indicated a bug once, but well, if it is not used… Anyway, the talk was interesting, and the results could inspire further experiments.

The last talk was David’s: Harnessing Emergency for Manycore Programming: Early Experience Integrating Ensembles, Adverbs, and Object-based Inheritance. What should I say, of course David mentioned the RoarVM Thats great. But if it comes to the language, there are still a lot of open questions. Interestingly, David really managed to get the people thinking about the problem he presented. It was a small little puzzle of language design, something that seemed to appeal to the audience. He got some suggestions, but well, no ground breaking new idea as far as I could see. Hope they will follow up on it offline.

And that was SPLASH’10. Should have went to Lake Tahoe, saw some nice pictures of the nature, but hadn’t had the time Conclusion, Reno was just the right place to focus on work…

As usual I will write about a few of my personal highlights of SPLASH and the co-located workshops. That is mostly from my spotty notes, and from memory, so I don’t guarantee 100% accuracy, especially with respect to what other people might have said.

For an impression on the location itself, I will just cite and refer to what Nick wrote on the JOT blog:
“Reno airport was like a gateway into hell, slot machines everywhere [...] The conference venue is almost comically grim. The main floor is a sea of slot machines and haggard looking people.”
So, it was definitely not the most exciting place ever, and I was already worried that my colleagues start to shoot at those zombies

Anyway, from the content point of view, it was actually a nice conference for me.

On Sunday the Virtual Machine Intermediate Languages workshop took place. As last year, that is the most relevant workshop with respect to VMs I came across so far. This year, especially the invited talks were very interesting.

A JVM Does What????

Cliff Click started with reporting on his perception of JVMs and the illusions they provide to the developers. My take away from his talk are the following points.

First, garbage collection is still the major issue, and people are willing to pay for better performance here. He kind of implied that JIT compilers are nice to have, but not as high on the list of priorities for his typical customers.

Second, he wants people to explore alternative concurrency models on top of the VM. From his perspective, the JVM is a great platform and things like locks are cheap. He agrees that things like Erlang-like Actors need deeper hocks into the Java Memory Model and possibly the JIT compiler, but in general I understood that he would rather prefer something on top instead of another thing integrated into the VM. Well, lets see how my ideas work out.

Related to my ideas we had a small discussion afterwards with David. I was surprised that Azul uses a Uniform Memory Access model for its systems but apparently the problem is that current business applications exhibit random access patterns all over the heap. Thus, if you have a system with 16 chips and 16 memory controller, 15/16 of the access are going remote anyway. That is why the optimize for that case instead of optimizing local performance. Interesting, but perhaps just the consequence of not having appropriate languages which take locality into account in the first place.

SPUR: A Trace-Based JIT Compiler for CIL

Nikolai Tillmann reported on the SPUR project at Microsoft Research. He gave a introduction to tracing-based just-in-time compilation and also present some benchmarks. The interesting part about SPUR is that they actually JIT .NET but experiment mainly with JavaScript.

For me the most interesting aspect of his talk was the future work section were he mentioned a few attempts on parallelizing code by the tracing JIT. Their ideas mainly focus on vectorization which is kind of not so exciting, hope they will also look into speculative execution, even so Nikolai asks for more hardware support for such an idea.

A Systematic Mapping Study on High-level Language Virtual Machines

The first research paper I am going to mention here was meta research on VM research.

The authors surveyed the body of literature on VMs to find out what people are doing research on. Well, the scope was a bit to narrow to actually cover all interesting papers, but it is a very nice first step. David was a bit disappointed that his Self and other Smalltalk papers were not covered and that the literature that was identified as being relevant only started in the 90′ies or so. Well, the authors were already aware of those limitations, but beside this definitely constructive criticism, the audience also came up with proposals to get us as the community involved. There is serious interest in such research and people would be happy with helping classifying (and certainly promoting their own research) if that could happen on a wiki or so…

The Architecture of DecentVM – Towards a Decentralized Virtual Machine for Many-Core Computing

How’s the Parallel Computing Revolution Going? Towards Parallel Scalable Virtual Machine Services

Kathryn McKinley reported on experiments her students did to compare the speed and power consumption of CPUs over the last few years. Turns out, the power consumption seems to rise faster than the performance, especially since the benchmarks do not scale perfectly for multicore applications. However, there is quite a bit of progress with respect to saving energy instead of increasing performance with Intel’s Atom and related architectures.

Interesting was her proposal to parallelize the VM in itself. Something Theo always asks for, too. However, Cliff Click basically said that HotSpot is already at that point for most parts. So, at least from his perspective, that is not a field where major breakthroughs will come from…

Monday, the second day of workshops was less interesting. I started in the day with giving my presentation at the Doctoral Symposium. Did not get more than meta-feedback, unfortunately. I guess, it was just to early for that. What I have is an idea (perhaps with to many open design options) and a plan to validate it. But it was obviously still too fluffy… On the other hand, that meant I was missing great workshops like for instance Evaluate 2010 and the Dynamic Languages Symposium *sigh*