@article {Simula.mpg.30,
	title = {The Nornir Run-Time System for Parallel Programs Using Kahn Process Networks on Multi-Core Machines - a Flexible Alternative to MapReduce},
	journal = {The Journal of Supercomputing},
	number = {Online first},
	year = {2010},
	note = {In print: January 2013, Volume 63, Issue 1, pp 191-217},
	pages = {1-27},
	abstract = {Even though shared-memory concurrency is a paradigm frequently used for developing parallel applications on small- and middle-sized machines, experience has shown that it is hard to use. This is largely caused by synchro- nization primitives which are low-level, inherently nondeterministic, and, consequently, non-intuitive to use. In this paper, we present the Nornir run-time system. Nornir is comparable to well-known frameworks such as MapReduce and Dryad that are recognized for their efficiency and simplicity. Unlike these frameworks, Nornir also supports process structures containing branches and cycles. Nornir is based on the formalism of Kahn process networks, which is a shared-nothing, message-passing model of concurrency. We deem this model a simple and deterministic alternative to shared-memory concurrency. Experiments with real and synthetic benchmarks on up to 8 CPUs show that per- formance in most cases scales almost linearly with the number of CPUs, when not limited by data dependencies. We also show that the modeling flexibility allows Nornir to outperform its MapReduce counter-parts using well-known benchmarks.},
	doi = {10.1007/s11227-010-0503-2},
	author = {Vrba, Zeljko and Halvorsen, P{\r a}l and Griwodz, Carsten and Beskow, Paul and Espeland, H{\r a}vard and Johansen, Dag}
}
@inproceedings {Simula.ND.411,
	title = {Program Obfuscation by Strong Cryptography},
	journal = {Proceedings of the International Conference on Availability, Reliability and +Security (ARES), Krakow, Poland, February 2010},
	year = {2010},
	pages = {242-247},
	publisher = {N/A},
	type = {Conference},
	abstract = {Program obfuscation is often employed by malware in order to avoid detection by anti-virus software, but it has many other legitimate uses, such as copy protection, software licensing or private computing in the cloud. In this paper, we present a program obfuscation method that is based on the combination of strong encryption of code and data and a CPU simulator (CSPIM) that implements theMIPS I instruction set. Our method is different from existing methods in that only a single word (32- bits) of the protected code or data is present as plain-text in main memory. Furthermore, our method allows the possibility of externally supplying the decryption key to the simulator. We have extensively tested the simulator, and it is able to successfully execute C programs compiled by the gcc cross-compiler. Even though purely software-based method cannot provide perfect protection, we argue that this approach significantly raises the bar for reverse-engineers, especially wen combined with existing program obfucation techniques.},
	isbn = {978-1-4244-5879-0},
	doi = {10.1109/ARES.2010.47},
	author = {Vrba, Zeljko and Halvorsen, P{\r a}l and Griwodz, Carsten}
}
@inproceedings {Simula.ND.409,
	title = {A Simple Improvement of the Work-Stealing Scheduling Algorithm},
	journal = {Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems (CISIS) - International Workshop on Multi-Core Computing Systems (MuCoCoS), Krakow, Poland, February 2010},
	year = {2010},
	pages = {925-930},
	publisher = {N/A},
	type = {Workshop},
	abstract = {Work-stealing is the todays algorithm of choice for dynamic load-balancing of irregular parallel applications on multiprocessor systems. We have evaluated the algorithm\&$\#$39;s efficiency on a variety of workloads, including scatter-gather workloads, which occur in common algorithms such as MapReduce. We have discovered that work-stealing scheduling suffers serious scalability problems with fine-grained parallelism because of contention over run-queues. We therefore propose a simple modification to the work-stealing algorithm that significantly improves its performance on scatter-gather workloads, without any negative impact on other types of workloads.},
	isbn = {978-1-4244-5917-9},
	doi = {10.1109/CISIS.2010.67},
	author = {Vrba, Zeljko and Halvorsen, P{\r a}l and Griwodz, Carsten}
}
@inproceedings {Simula.ND.263,
	title = {Evaluating the Run-Time Performance of Kahn Process Network Implementation Techniques on Shared-Memory Multiprocessors},
	journal = {Complex, Intelligent and Software Intensive Systems, International Conference},
	year = {2009},
	pages = {639-644},
	publisher = {IEEE Computer Society},
	type = {Workshop},
	abstract = {Software development tools have not adapted to the growing popularity of multi-core CPUs, and developers are still {\textquoteleft}{\textquoteleft}stuck\&$\#$39;\&$\#$39; with low-level and high-cost thread abstractions. The situation is becoming even more complicated with the advent of heterogenuous computing. In this article, we point out some drawbacks of high-level abstractions currently in use, and propose Kahn process networks (KPN) as a more high-level and efficient abstraction for developing parallel applications. We show that the native POSIX mechanisms (threads and message queues) perform suboptimally as an implementation vehicle for KPNs, and we present an implementation of a run-time environment that can execute KPNs with less overhead. Our evaluation shows the advantages and disadvantages of statically mapping Kahn processes to CPUs.},
	isbn = {978-0-7695-3575-3},
	doi = {10.1109/CISIS.2009.43},
	author = {Vrba, Zeljko and Halvorsen, P{\r a}l and Griwodz, Carsten}
}
@phdthesis {Simula.simula.22,
	title = {Implementation and Performance Aspects of Kahn Process Networks - an Investigation of Problem Modeling, Implementation Techniques, and Scheduling Strategies},
	year = {2009},
	month = {July},
	school = {University of Oslo},
	type = {phd},
	address = {Unipub, Kristian Ottosens hus, Pb. 33 Blindern, 0313 Oslo},
	abstract = {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. KPNs are 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. Because of determinism, it is possible to reliably reproduce faults, an otherwise notoriously difficult problem with parallel programs. KPNs have gained acceptance in simulation and signal-processing communities. 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.},
	author = {Vrba, Zeljko}
}
@inproceedings {Simula.ND.321,
	title = {Kahn Process Networks Are a Flexible Alternative to MapReduce},
	journal = {Proceedings of 11th IEEE International Conference on High Performance Computing and Communications (HPCC)},
	year = {2009},
	pages = {154-162},
	publisher = {IEEE Computer Society},
	type = {Conference},
	abstract = {Experience has shown that development using shared-memory concurrency, the prevalent parallel programming paradigm today, is hard and synchronization primitives nonintuitive because they are low-level and inherently nondeterministic. To help developers, we propose Kahn process networks, which are based on message-passing and shared-nothing model, as a simple and flexible tool for modeling parallel applications. We argue that they are more flexbile than MapReduce, which is widely recognized for its efficiency and simplicity. Nevertheless, Kahn process networks are equally intuitive to use, and, indeed, MapReduce is implementable as a Kahn process network. Our presented benchmarks (word count and k-means) show that a Kahn process network framework permits alternative implementations that bring significant performance advantages: the two programs run by a factor of up to \sim 2.8 (word-count) and \sim 1.8 (k-means) faster than their implementations for Phoenix, which is a MapReduce framework specifically optimized for executing on multicore machines.},
	isbn = {978-0-7695-3738-2},
	doi = {10.1109/HPCC.2009.46},
	author = {Vrba, Zeljko and Beskow, Paul and Halvorsen, P{\r a}l and Griwodz, Carsten}
}
@inproceedings {Simula.ND.325,
	title = {Limits of Work-Stealing Scheduling},
	journal = {Job Scheduling Strategies for Parallel Processing (14th International Workshop, 2009)},
	year = {2009},
	pages = {280-299},
	publisher = {Springer Berlin / Heidelberg},
	type = {Workshop},
	abstract = {The number of applications with many parallel cooperating processes is steadily increasing, and developing efficient runtimes for their execution is an important task. Several frameworks have been developed, such as MapReduce and Dryad, but developing scheduling mechanisms that take into account processing \emph{and} communication requirements is hard. In this paper, we explore the limits of work stealing scheduler, which has empirically been shown to perform well, and evaluate load-balancing based on graph partitioning as an orthogonal approach. All the algorithms are implemented in our Nornir runtime system, and our experiments on a multi-core workstation machine show that the main cause of performance degradation of work stealing is when very little processing time, which we quantify exactly, is performed per message. This is the type of workload in which graph partitioning has the potential to achieve better performance than work-stealing.},
	isbn = {978-3-642-04632-2},
	doi = {10.1007/978-3-642-04633-9\_15},
	author = {Vrba, Zeljko and Espeland, H{\r a}vard and Halvorsen, P{\r a}l and Griwodz, Carsten},
	editor = {Frachtenberg, Eitan and Schwiegelshohn, Uwe}
}
@inproceedings {Simula.ND.397,
	title = {The Nornir Run-Time System for Parallel Programs Using Kahn Process Networks},
	journal = {Proceedings of 6th International Conference on Network and Parallel Computing (NPC)},
	year = {2009},
	pages = {1-8},
	publisher = {IEEE Computer Society},
	type = {Conference},
	abstract = {Shared-memory concurrency is the prevalent paradigm used for developing parallel applications targeted towards small- and middle-sized machines, but experience has shown that it is hard to use. This is largely caused by synchronization primitives which are low-level, inherently nondeterministic, and, consequently, non-intuitive to use. In this paper, we present the \textit{Nornir} run-time system. Nornir is comparable to well-known frameworks like MapReduce and Dryad, but has additional support for process structures containing cycles. It is based on the formalism of Kahn process networks, which we deem as a simple and deterministic alternative to shared-memory concurrency. Experiments with real and synthetic benchmarks on up to 8 CPUs show that performance in most cases improves almost linearly with the number of CPUs, when not limited by data dependencies.},
	isbn = {978-0-7695-3837-2},
	author = {Vrba, Zeljko and Halvorsen, P{\r a}l and Griwodz, Carsten and Beskow, Paul and Johansen, Dag}
}
