EMPER

The Efficient Massive-Parallelism Execution Realm (EMPER) is a concurrency platform to develop and execute parallel applications.

EMPER's primary objective is to support the research of different aspects of parallel execution of a potentially massive amount of concurrent strands of execution on current and future many-core systems. Those aspects include, for example, scheduling strategies, synchronization primitives, and ultimately the overall coordination of concurrent strands of execution concerning optimal resource usage, including locality and energy efficiency. We believe that a concurrency platform can only achieve outstanding results if the runtime system and operating system cooperate closely. Hence another research focus of EMPER is the interface between the user-space runtime system and the operating system. For example, EMPER uses modern asynchronous system request techniques and a novel approach called "I/O-stealing" to dispatch the operating system's responses back into the user-space runtime system.

The research with EMPER follows a focused approach to demonstrate and prove the viability of researched concepts in a concrete implementation. Furthermore, EMPER strives for correctness so that the results of evaluations involving EMPER are reliable. While developed as part of academic activity, we develop EMPER to produce a usable end-product in mind, wherever possible and sensible.

To enable every efficient fork/join parallelism, 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 implementation allows for very 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".

Publications

[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

Literature

The dwarf sees farther than the giant, when he has the giant's shoulder to mount on.

• Samuel Taylor Coleridge, The Friend (1828)

EMPER uses concepts, ideas and algorithms from the following publications. You will find the key of a publication, e.g., [chase2005dynamic] sometimes mentioned in EMPER's source code.

[chase2005dynamic] Chase, David and Yossi Lev. “Dynamic Circular Work-Stealing Deque”. In: Pro- ceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. SPAA ’05. Las Vegas, Nevada, USA: Association for Computing Machinery, 2005, pp. 21–28. isbn: 1581139861. doi: 10.1145/1073970.1073974.

[le2013correct] Lê, Nhat Minh, Antoniu Pop, Albert Cohen, and Francesco Zappa Nardelli. “Correct and Efficient Work-Stealing for Weak Memory Models”. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP ’13. Shenzhen, China: Association for Computing Machinery, 2013, pp. 69–80. isbn: 9781450319225. doi: 10.1145/2442516.2442524. url: https://hal.inria.fr/hal-00802885/document

[norris2013cdschecker] Norris, Brian and Brian Demsky. “CDSchecker: Checking Concurrent Data Structures Written with C/C++ Atomics”. In: Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages Applications. OOPSLA ’13. Indianapolis, Indiana, USA: Association for Computing Machinery, 2013, pp. 131–150. isbn: 9781450323741. doi: 10.1145/2509136.2509514. url: http://plrg.eecs.uci.edu/publications/c11modelcheck.pdf