Implementation and performance aspects of Kahn process networks - An investigation of problem modeling, implementation techniques, and scheduling strategies
Supervisor(s) and Committee member(s): Pål Halvorsen (supervisor), Carsten Griwodz (supervisor), Prashant Shenoy (opponent), Lasse Natvig (opponent), Tor Skeie (opponent)
URL: http://home.ifi.uio.no/paalh/students/ZeljkoVrba.pdf%20
The appearance of commodity multi-core processors has spawned a wide interest in parallel programming, which is widely-regarded as more challenging than sequential programming. Existing distributed processing frameworks like MapReduce and Dryad are intentionally meant for large batch workloads and fail to efficiently support cyclic workloads with deadlines. In this respect, a Kahn Process Networks (KPN) is a model of concurrency that relies exclusively on message passing, and that has some advantages over parallel programming tools in wide use today: simplicity, graphical representation, and determinism.
In this thesis, we investigate the applicability of KPNs to implementing general-purpose parallel computations for multi-core machines. In particular, we investigate 1) how KPNs can be used for modeling general-purpose problems; 2) how an efficient KPN run-time can be implemented; 3) what KPN scheduling strategies give good run-time performance. For these purposes, we have developed Nornir, an efficient run-time system for executing KPNs. With Nornir, we show that it is possible to develop a high-performance KPN run-time for multi-core machines. We experimentally demonstrate that problems expressed in the Kahn model resemble very much their sequential implementations, yet perform much better than when expressed in the MapReduce model, which has become widely-recognized as a simple parallel programming model. Lastly, we use Nornir to evaluate several load-balancing methods: static assignment, work-stealing, our improvement of work-stealing, and a method based on graph partitioning. The understanding brought by this evaluation is significant not only in the context of the Kahn model, but also in the more general context of load-balancing (potentially distributed) applications written in message-passing style.
Multimedia Performance Group (MPG), Simula Research Laboratory / University of Oslo
URL: http://simula.no/research/mpg%20%20
The Media Performance Group investigates the means for improving the performance of distributed, time-dependent multimedia systems. In the context of an application, the group seeks solutions by exploring, understanding and improving a particular bottleneck using an experimental approach. Improvements are found in better operating systems mechanisms, programming tools, processing environments, protocols, distributed architectures, digital media formats or a better understanding of people's perception of media in a context.
In the context of MPG, efficient processing of workloads, especially multimedia workloads, is an important area in order to support the timeliness of multimedia applications. This thesis describes a new distributed processing framework improving upon state-of-the-art being able to support cyclic and iterative workloads.