Name
Abstract | ||
|---|---|---|
Many-core architectures enable the concurrent execution of multiple application programs. In this context, the well-known problem of feasibly mapping applications, i.e., their tasks and communication, to such architectures has gained importance due to the large number of cores and limited inter-processor communication capacities. This challenge is tackled by so-called Hybrid Application Mapping (HAM) approaches: These combine a design-time analysis to extract sets of mapping constraints that characterize feasible, respectively optimal mappings with the runtime determination of a concrete mapping in dependence of these mapping constraints and the set of currently available resources. A major strength of HAM approaches has been shown as their ability to give real-time and other guarantees for statically characterized application programs even in highly dynamic workload scenarios while avoiding the pessimism of static resource partitionings. However, finding a feasible mapping is an NP-complete problem. This work discusses arising implications for HAM approaches in general and investigates two exact techniques for solving the mapping constraints at runtime in particular: (I) a problem-specific backtracking approach, and (II) an approach that adopts a general-purpose SAT solver. Experimental results show that the overhead of the general-purpose solver and, in particular, processing and solving the required SAT formulation becomes significant, whereas the problem-specific backtracking technique achieves significantly lower execution times. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/MCSoC2018.2018.00038 | 2018 IEEE 12th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC) |
Keywords | Field | DocType |
Many Core Architectures,Hybrid Application Mapping,Constraint Solving | Resource management,Task analysis,Workload,Computer science,Parallel computing,Boolean satisfiability problem,Solver,Backtracking | Conference |
ISBN | Citations | PageRank |
978-1-5386-6690-6 | 1 | 0.35 |
References | Authors | |
11 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tobias Schwarzer | 1 | 27 | 5.60 |
| Sascha Roloff | 2 | 30 | 4.14 |
| Valentina Richthammer | 3 | 3 | 1.76 |
| Rami Khaldi | 4 | 1 | 0.35 |
| Stefan Wildermann | 5 | 156 | 26.00 |
| Michael Glaß | 6 | 510 | 45.33 |
| Jürgen Teich | 7 | 15 | 9.70 |