EMPER

The Extensible Micro-Parallelism Execution Runtime (EMPER) is a concurrency platform to execute parallel applications.

The runtime system of EMPER implements the wait-free "Nowa" continuation-stealing approach as described in the IPDPS 2021 paper by Schmaus et al. This allows for efficient fork-join parallelism for two reasons. First, continuation-stealing enables dynamic task parallelism: The concurrency expressed at the programming-language layer is only lifted into parallelism by the runtime system if there are available workers. Secondly, the wait-free Nowa approach allows for scalability on systems with many cores.

emper_fibril auto fib(int n) -> int {
	if (n < 2) return n;

	Fibril fibril;
	int a, b;

	fibril.fork(&a, fib, n - 1);

	b = fib(n - 2);

	fibril.join();

	return a + b;
}

Scheduling

EMPER provides a modular architecture allowing for different scheduling strategies. Currently two scheduling strategies are implemented:

• Work stealing scheduling (WS)
• Locality aware and work stealing scheduling (LAWS)

License

EMPER is licensed under the GNU Lesser General Public License, version 3 (or any later version). See the file 'LGPL-3' for the full text of this license.

Acknowledgements

Nicolas Pfeiffer wrote the first prototypical implementation of continuation-stealing for EMPER. Much of his code was re-used for the current implementation.

Florian Fischer wrote the EMPER interface for "pseudo-blocking system calls" based on Linux's io_uring. We would also like to thank Jens Axboe and Pavel Begunkov for creating and constantly improving io_uring.

This work was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 146371743 – TRR 89 "Invasive Computing".

Literature

[schmaus2021modern] Schmaus, Florian, Florian Fischer, Timo Hönig, and Wolfgang Schröder-Preikschat. Modern Concurrency Platforms Require Modern System-Call Techniques. Tech. rep. CS-2021-02. Friedrich-Alexander Universität Erlangen-Nürnberg, Technische Fakultät, Nov. 23, 2021. doi: 10.25593/issn.2191-5008/CS-2021-02. url: https://www4.cs.fau.de/~flow/papers/schmaus2021modern.pdf

[schmaus2021nowa] Schmaus, Florian, Nicolas Pfeiffer, Timo Hönig, Jörg Nolte, and Wolfgang Schröder- Preikschat. “Nowa: A Wait-Free Continuation-Stealing Concurrency Platform”. In: 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS). May 2021, pp. 360–371. doi: 10.1109/IPDPS49936.2021.00044. url: https://www4.cs.fau.de/~flow/papers/schmaus2021nowa.pdf

[pfeiffer2020cactus] Pfeiffer, Nicolas. A Wait-Free Cactus Stack Implementation for a Microparalelism Runtime. Master's thesis. MA-I4-2020-02. Mar. 2, 2020. url: https://www4.cs.fau.de/~flow/papers/pfeiffer2020cactus.pdf