Stefan-Marr.de

Today, I gave a talk at the ExaScience Lab, Intel Labs Europe in Leuven at IMEC. I talked mainly about the idea of nondeterministic programming, the Sly programming language and some details on our Smalltalk manycore virtual machine that enables those experiments. Thus, tried to spread the word about our Renaissance project at bit further.

Below you can find the abstract and slides.

Abstract

The manycore future has several challenges ahead of us that suggest that fundamental assumptions of contemporary programming approaches do not apply anymore when scalability is required.

Sly is a language prototype designed to experiment with the inherently nondeterministic properties of parallel systems. It is designed to enable programmers to embrace nondeterminism instead of guiding them to fight it. Nature shows that complex system can be built from independent entities that achieve a common goal without global synchronization/communication. Sly is design to enable the prototyping of algorithms that show such emerging behavior. It will be introduced in the first part of the talk.

The second part of the talk will focus on the underlying problems of building virtual machines for the manycore future, which allow to harness the available computing power. The RoarVM was design to experiment on the Tilera TILE64 manycore processor architecture which provides 64 cores and characteristics that are distinctly different from today’s commodity multicore processors. Memory bandwidth, caches and communication are the biggest challenges on such architectures and this talk will give a brief overview over the design choices of the RoarVM which tackle the characteristics of the TILE64 architecture.

 

Acknowledgement: Sly and the RoarVM were designed and implemented by David Ungar and Sam Adams at IBM Research.

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…

The third and last part of the summer school started with Ondrej Lhotak talking about pointer analysis. David Bacon presented a basic introduction to garbage collection and detailed description of the real-time Metronome GC. The last lecturer for this summer school was Patrick Cousot, who gave a very basic and thus understandable introduction to abstract interpretation.

Pointer Analysis

Ondrej’s lectures were focused on pointer analysis for C and Java-like languages. He introduced it as a static analysis for several problems like for instance optimization, call-graph construction, dependency analysis and optimization, cast elimination, side effect, and escape analysis. The major problem seems to be that it is a very broad subject with many different applications, and thus, many different techniques to do the analysis.

So, before applying pointer analysis the right abstraction for a specific problem has to be chosen. Usually, this kind of analysis will result in an over approximation of the actual problem. Under approximations are unsound and the exact points-to sets are not computable. Thus, a suitable over approximation has to be found which is exact enough for a specific question to be answered.

Just to recapitulate two examples, he introduced abstractions based on type filtering, i.e, points-to sets are calculated on the bases of types of the potential object during a program execution. Furthermore, he explained field sensitive abstractions. Here the main property of interest is the field to which an object is assigned and this information is used to calculate the points-to sets. More examples and more advance techniques like refinement demand-driven analysis are shown in the slide set which will hopefully appear on the summer school webpage.

Garbage Collection and the Metronome GC

David started his lectures by showing off a bit He showed a nice demo of what the Metronome system is able to achieve in terms of real-time constraints. Definitely very interesting and it fortifies my belief that a Java-like language will be the next system programming language succeeding C/C++.

Afterwards, he gave a short introduction to mark/sweep and semi-space collectors. Useful was his explanation about the actual semantics of StopTheWorld, parallel, concurrent, and incremental GCs supported with an illustration (should remember that one). BTW: The world needs a better book on garbage collection. I don’t like the one of Jones and Lins. It does not solve my problems

Eventually, he started explaining the Metronome-2 systems. The paging approach let me wonder whether there is anything an operating system is actually doing for a modern VM. Well there is, but is it enough to justify the additional trouble? Dreaming of Singularity… The second lesson was basically dedicated to synchronization issues and parallel/concurrent data structures like lock-free stacks and which strategies are out there to implement them. This was a nice addition to what we discussed during Yannis’ lectures and gave me some basic inspiration to implement a lock-free ring buffer for multiple writers and a single reader.

His explanation of all the details of the metronome algorithm and how the different phases interact was quite difficult, and well, not to easy to follow especially since I lost the overall picture from time to time. But well, it is a hard problem and a lot of engineering without a simple solution as it seems.

Abstract Interpretation

The last topic at the summer school was abstract interpretation and the lectures were given by Mr. Abstract Interpretation Patrick Cousot himself. Even so it is a theoretical topic, I liked his introduction. Probably for some of the people it was to basic, but since I never had looked at it before, for me it was the right level of detail and complexity to get an idea what abstract interpretation is actually about.

Unfortunately, my own notes are very spares, and I was not able to retrieve the slide set up to now. However, abstract interpretation tries to provide a sound approximation of the semantics of a computer program, to enable various kinds of static analysis. The main problem here is, similar to pointer analysis, to choose the right abstraction for a given problem.

The examples I recall could have fit into Summit’s presentation about bound computation of loops as well. He introduced ideas like step-wise approximation and other techniques. But, well, unfortunately my memory is too blurry to write something down here with certainty. Beside the introduction of the formal techniques, he also spent some time on how to implement them with Ocaml examples. He also made quite some advertisement for his product ASTRÉE, which originally was developed to analyze code for avionic systems. Well, if I can get my hands on his slides, I might add some more information about the content, but for the moment that’s it.

Where to go next Year?