Snippets Groups Projects

"...0d0cea2424ae97b27447dc64a7dbfae83c036c45b403392f0e8ba.png" did not exist on "cf3ac3ed97945a4ba9da3f6edc3ea87dfca1205e"

Add support for continuation stealing

Florian Schmaus authored 3 years ago

Thanks to Nicolas Pfeiffer for writing the initial prototypical
implementation of continuation stealing and the cactus stack
mechanism, on which this is based.

Co-authored-by: Nicolas Pfeiffer <pfeiffer@cs.fau.de>

cf3ac3ed

cf3ac3ed 3 years ago

Name	Last commit	Last update
apps
compile_commands_wo_subprojects
doc
emper
eval
stresstest
subprojects
tests
tools
.clang-format
.clang-tidy
.dir-locals.el-disabled
.editorconfig
.git-blame-ignore-revs
.gitignore
.gitlab-ci.yml
LGPL-3
LICENSE
Makefile
README.md
compile_commands.json
docker.sh
iwyu-mappings.imp
meson-migration.org
meson.build
meson_options.txt

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