A3: Scheduling and Load Balancing

Principal Investigators:

Prof. P. Sanders

Scientific Researchers:

Dr. D. Luxen, J. Speck


A key innovation of invasive computing is added flexibility. Subproject A3 investigates algorithms that use this flexibility to actually improve performance. In particular, these load balancing algorithms have to decide how much parallelism to use, where to assign parallel jobs, and how to dynamically change these decisions. In these decisions, processor resources, communication costs, and competing requirements of the jobs have to be taken into account and the load balancing algorithms themselves have to scale to large, possibly heterogeneous systems with stringent latency requirements.
Project A3 terminated after the first funding phase.


[1] Peter Sanders, Jochen Speck, and Raoul Steffen. Work-efficient matrix inversion in polylogarithmic time. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, pages 214–221. ACM, 2013. [ DOI ]
Keywords: linear algebra, matrix inversion, newton approximation, numerics, parallel algorithms, polylogarithmic time, strassen's inversion algorithm
[2] Patrick Flick, Peter Sanders, and Jochen Speck. Malleable sorting. In Parallel Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on, number ISSN 1530-2075, pages 418–426, 2013. [ DOI ]
Keywords: Arrays;Complexity theory;Instruction sets;Linux;Optimal scheduling;Sorting;Time measurement
[3] Peter Sanders and Jochen Speck. Energy efficient frequency scaling and scheduling for malleable tasks. In Christos Kaklamanis, Theodore Papatheodorou, and Paul Spirakis, editors, Euro-Par 2012 Parallel Processing, volume 7484 of Lecture Notes in Computer Science, pages 167–178. Springer Berlin Heidelberg, 2012. [ DOI ]
[4] Jürgen Teich, Jörg Henkel, Andreas Herkersdorf, Doris Schmitt-Landsiedel, Wolfgang Schröder-Preikschat, and Gregor Snelting. Invasive computing: An overview. In Michael Hübner and Jürgen Becker, editors, Multiprocessor System-on-Chip – Hardware Design and Tool Integration, pages 241–268. Springer, Berlin, Heidelberg, 2011. [ DOI ]
[5] Peter Sanders and Jochen Speck. Efficient parallel scheduling of malleable tasks. In International Parallel and Distributed Processing Symposium (IPDPS), pages 1156–1166. IEEE Computer Society, 2011. [ DOI ]
[6] Jürgen Teich. Invasive algorithms and architectures. it - Information Technology, 50(5):300–310, 2008.