24.08.2018 Invited Talk Prof. Teich at National University Singapore (NUS)
Prof. Teich gave his invited talk “Mixes Static/Dynamic Application Mapping for NoC-Based MPSoCs with Guarantees on Timing, Reliability and Security”.at National University of Singapore (NUS).
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.