And another paper that’s going to be presented by Joeri is our work on Tanks, a variation of communicating event loops (à la E or AmbientTalk). Tanks add synchronous and consistent read access to the event loop model.
Below, you can find the preprint of the paper and its abstract for more details:
In the past, the Actor Model has mainly been explored in a distributed context. However, more and more application developers are also starting to use it to program shared-memory multicore machines because of the safety guarantees it provides. It avoids issues such as deadlocks and race conditions by construction, and thus facilitates concurrent programming. The tradeoff is that the Actor Model sacrifices expressiveness with respect to accessing shared state because actors are fully isolated from each other (a.k.a. “shared-nothing parallelism”). There is a need for more high level synchronization mechanisms that integrate with the actor model without sacrificing the safety and liveness guarantees it provides. This paper introduces a variation on the communicating event-loops actor model called the Tank model. A tank is an actor that can expose part of its state as a shared read-only resource. The model ensures that any other actor will always observe a consistent version of that state, even in the face of concurrent updates of the actor that owns that state.
Tanks: Multiple reader, single writer actors, Joeri De Koster, Stefan Marr, Theo D’Hondt, Tom Van Cutsem; Proceedings of AGERE! 2013, 3rd International Workshop on Programming based on Actors, Agents, and Decentralized Control, ACM, to appear.
On Sunday, I am going to present work on a distributed Rete engine I have been involved in over the last year. The presentation will be at the AGERE workshop co-located with SPLASH. Note that most of the work has been done by Janwillem and Thierry over the last two years. They did a great job in first implementing and parallelizing our Rete engine and now distributing it to scale up for “big data” scenarios.
Below, you can find a preprint of the paper, it’s abstract, and my presentation slides:
Traffic monitoring or crowd management systems produce large amounts of data in the form of events that need to be processed to detect relevant incidents.
Rule-based pattern recognition is a promising approach for these applications, however, increasing amounts of data as well as large and complex rule sets demand for more and more processing power and memory. In order to scale such applications, a rule-based pattern detection system needs to be distributable over multiple machines. Today’s approaches are however focused on static distribution of rules or do not support reasoning over the full set of events.
We propose Cloud PARTE, a complex event detection system that implements the Rete algorithm on top of mobile actors. These actors can migrate between machines to respond to changes in the work load distribution. Cloud PARTE is an extension of PARTE and offers the first rule engine specifically tailored for continuous complex event detection that is able to benefit from elastic systems as provided by cloud computing platforms. It supports fully automatic load balancing and supports online rules with access to the entire event pool.
Cloud PARTE: Elastic Complex Event Processing based on Mobile Actors, Janwillem Swalens, Thierry Renaux, Lode Hoste, Stefan Marr, Wolfgang De Meuter; Proceedings of AGERE! 2013, 3rd International Workshop on Programming based on Actors, Agents, and Decentralized Control, ACM, to appear.
Since quite a while, I am using R as a scripting language to generate graphs to the benchmarking results of various experiments. Since we have a new 64 core machine at the lab, I happen to run into performance issues with scripts that process the benchmark results, because the number of measurements increased significantly and the plyr library I use was designed with ease of use in mind, instead of performance. Concretely, I was experiencing script runtimes of up to 25min for a data set with roughly 50.000 measurements.
Fortunately, it is a know issue and a quick search turned up various options to improve performance. Since my initial choice for plyr was based on its intuitive DSL, I was looking for something that is similarly nice, but a lot faster. This blog post is meant to briefly document my findings for myself, and remind me how to use the data.table package, I chose.
Plyr’s ddply can be extremely slow
In an earlier post, I already outlined briefly how I use R to process benchmarking results. So far, I used ddply mostly with the transform and summarize functions to normalize measurements and to calculate averages, standard deviation, or speedup factors.
The problematic examples are for instance the following normalization and aggregation operations:
On the object-table data set form earlier experiments, the process_data(...) function takes roughly 2.1sec to execute. Thus, is as not particular fast, but still useable. However, on the recent data sets I was using, the runtime got a severe bottleneck.
Thus, I was looking into data.table to find an alternative. The result is a rewrite of the function to the process_data_dt(...) function below. The result is a roughly 20x speedup. On the sample data mentioned, the runtime goes from 2.1sec down to 0.2sec. In my particular case, the runtime went from 25min to 1.3min. That’s still slow, but much more usable.
Last Friday, I defended my PhD dissertation. Finally, after 4 years and a bit, I am done. Finally. I am very grateful to all the people supporting me along the way and of course to my colleagues for their help.
My work focused on how to build VMs with support for all kind of different concurrent programming abstractions. Since you don’t want to put them into a VM just one by one, I was looking for a unifying substrate that’s up to the task. Below, you’ll find the abstract as well as the slides.
In addition to the thesis text itself, the implementations and tools are available. Please see the project page for more details.
During the past decade, software developers widely adopted JVM and CLI as multi-language virtual machines (VMs). At the same time, the multicore revolution burdened developers with increasing complexity. Language implementers devised a wide range of concurrent and parallel programming concepts to address this complexity but struggle to build these concepts on top of common multi-language VMs. Missing support in these VMs leads to tradeoffs between implementation simplicity, correctly implemented language semantics, and performance guarantees.
Departing from the traditional distinction between concurrency and parallelism, this dissertation finds that parallel programming concepts benefit from performance-related VM support, while concurrent programming concepts benefit from VM support that guarantees correct semantics in the presence of reflection, mutable state, and interaction with other languages and libraries.
Focusing on these concurrent programming concepts, this dissertation finds that a VM needs to provide mechanisms for managed state, managed execution, ownership, and controlled enforcement. Based on these requirements, this dissertation proposes an ownership-based metaobject protocol (OMOP) to build novel multi-language VMs with proper concurrent programming support.
This dissertation demonstrates the OMOP’s benefits by building concurrent programming concepts such as agents, software transactional memory, actors, active objects, and communicating sequential processes on top of the OMOP. The performance evaluation shows that OMOP-based implementations of concurrent programming concepts can reach performance on par with that of their conventionally implemented counterparts if the OMOP is supported by the VM.
To conclude, the OMOP proposed in this dissertation provides a unifying and minimal substrate to support concurrent programming on top of multi-language VMs. The OMOP enables language implementers to correctly implement language semantics, while simultaneously enabling VMs to provide efficient implementations.
Supporting Concurrency Abstractions in High-level Language Virtual Machines, Stefan Marr. Software Languages Lab, Vrije Universiteit Brussel, Pleinlaan 2, B-1050 Brussels, Belgium, PhD Dissertation, January 2013. ISBN 978-90-5718-256-3.
It has been a while since SPLASH’12, but I got finally around to put up a copy of our paper at the AGERE’12 workshop. It is based on Thierry’s master thesis and presents his work on parallelizing a Rete engine for gesture recognition. Lode and I were his advisors and are happily working with him on what we promised in the future work section.
Applying imperative programming techniques to process event streams, like those generated by multi-touch devices and 3D cameras, has significant engineering drawbacks. Declarative approaches solve these problems but have not been able to scale on multicore systems while providing guaranteed response times.
We propose PARTE, a parallel scalable complex event processing engine which allows a declarative definition of event patterns and provides soft real-time guarantees for their recognition. It extends the state-saving Rete algorithm and maps the event matching onto a graph of actor nodes. Using a tiered event matching model, PARTE provides upper bounds on the detection latency. Based on the domain-specific constraints, PARTE’s design relies on a combination of 1) lock-free data structures; 2) safe memory management techniques; and 3) message passing between Rete nodes. In our benchmarks, we measured scalability up to 8 cores, outperforming highly
optimized sequential implementations.
Parallel Gesture Recognition with Soft Real-Time Guarantees, Thierry Renaux, Lode Hoste, Stefan Marr, Wolfgang De Meuter, Proceedings of the 2nd edition on Programming Systems, Languages and Applications based on Actors, Agents, and Decentralized Control Abstractions (AGERE’2012), page 35–46. ACM (2012).
And another paper that’s going to be presented by Joeri is our work on Tanks, a variation of communicating event loops (à la E or AmbientTalk). Tanks add synchronous and consistent read access to the event loop model. Below, you can find the preprint of the paper and its abstract for more details: Abstract In [...]
On Sunday, I am going to present work on a distributed Rete engine I have been involved in over the last year. The presentation will be at the AGERE workshop co-located with SPLASH. Note that most of the work has been done by Janwillem and Thierry over the last two years. They did a great [...]
Since quite a while, I am using R as a scripting language to generate graphs to the benchmarking results of various experiments. Since we have a new 64 core machine at the lab, I happen to run into performance issues with scripts that process the benchmark results, because the number of measurements increased significantly and [...]