Run-Time Application Mapping in Many-Core Architectures
Department of Computer Science
Friedrich-Alexander-Universitat Erlangen-Nurnberg (FAU)
Germany
COM1 Level 3
MR1, COM1-03-19
Abstract:
Many-core architectures enable the concurrent execution of multiple applications within a system. In this context, the well-known problem of feasibly mapping application to resources, i.e., tasks and their communication, has gained attention again due to the large number of cores and limited communication capacities between cores.
Whereas the general graph-based mapping problem is known to be NP-complete, we present a decomposition approach called hybrid mapping (HAM) that characterizes classes of feasible, even optimal mappings wrt. to a set of non-functional properties at compile-time. For the reduced search space run-time mapping problem, two exact approaches for parallel problem solving are then proposed and compared: a backtracking and an approach based on a parallel SAT-solver. For the latter, we present a novel scheme to partition the architecture and efficiently search in subarchitectures for feasible mappings. Solver instances encoding the complete architecture are only required in the case of the absence of feasible implementations on subarchitectures.
For a class of benchmark applications, the two run-time approaches are analyzed for execution times on different scales of NoC-based many-core targets. Interestingly, the execution times go down for parallel solvers over a single solver instance in both approaches. Also, the backtracking approach can determine solutions within an average of a few milliseconds for large scale architectures even, whereas the parallel SAT-solver techniques suffer from a quite long initialization overhead.
Biodata:
Jurgen Teich is with Friedrich-Alexander-Universitat Erlangen-Nurnberg (FAU), Germany, where he is Head of the Chair of Hardware/Software Codesign since 2003. He received the M.Sc. degree (Dipl.-Ing.; with Honors) from the University of Kaiserslautern, Germany, in 1989 and the Ph.D. degree (Dr.-Ing.; Summa Cum Laude) from the University of Saarland, Saarbrucken, Germany, in 1993.
Prof. Teich has organized various ACM/IEEE conferences/symposia as program chair including CODES+ISSS 2007, FPL 2008, ASAP 2010, DATE 2016, and was vice general chair of DATE 2018. he currently serves as the general chair of DATE 2019 and in the editorial boards of diverse journals such as ACM TODAES, IEEE Design and Test, IET Cyber-Physical Systems, and JES. He has edited two textbooks on hardware/software codesign and recently the Handbook on of Hardware/Software Codesign (Springer).
Since 2010, he has also been the principal coordinator of the transregional research center 89 INVASIVE COMPUTING on multicore research funded by the German Research Foundation (DFG). He is a member of Academia Europaea, the academy of Europe, and a Fellow of the IEEE.