HDA: Hierarchical and dependency-aware task mapping for network-on-chip based embedded systems

To support more efficient parallel processing, Network-on-Chip (NoC) is being increasingly adopted as a new alternative interconnection architecture. With the limited number of processing elements (PEs) on an NoC, to perform application tasks efficiently on the PEs has become a key issue. To ensure the completeness of data transmission between tasks in an application, the region-based scheme is used in the most existing task mapping methods. However, due to the dependency of tasks, not all the tasks in an application are executed on the corresponding PEs at the same time, and thus some PEs mapped by tasks are still idle when the required data are not received. This would lead to the issue of low utilization of PEs. In this work, we propose a hierarchical and dependency-aware (HDA) task mapping that covers the concepts of spatial mapping and inter-task dependency (temporal factors) to enhance the elasticity of task mapping. This proposed HDA method adopts a hierarchical task mapping, by using which when a previously mapped task finishes, its corresponding PE can be released and mapped by another unmapped task. As a result, in the region selection phase, fewer PEs in a region are required. This can not only enhance the elasticity of future task mapping but also result in lower communication latencies and higher utilization of PEs. Experiments show that, compared to the existing task mapping methods, including the first-fit mapping, the region-based mapping, and the elastic superposition mapping, the proposed HDA method can result in an average 24.32% enhancement in system performance and an average 44.76% reduction in the energy consumptions. To apply the HDA method to real applications such as embedded systems synthesis benchmarks suite (E3S), compared to the existing task mapping methods, system performance can be enhanced significantly, especially when the number of PEs on an NoC is fewer. Furthermore, the HDA method can also achieve 34.93% reduction in the energy consumptions.