An efficient multi-functional duplication-based scheduling framework for multiprocessor systems
- PDF / 1,527,530 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 176 Views
An efficient multi‑functional duplication‑based scheduling framework for multiprocessor systems Qi Tang1 · Li‑Hua Zhu2 · Jin Lian2 · Li Zhou1 · Ji‑Bo Wei1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Timing performance and energy consumption are the most critical performance indicators of schedules on multiprocessors. The timing performance of the schedule is limited by the inter-processor communication delay incurred by inter-task data dependence, especially for communication-intensive applications. To mitigate the negative impact of the communication delay on timing performance of the schedule, task duplication strategy, which is based on the fact that the local communication is delay-free, is often utilized. The duplication-based scheduling problem is NP-hard, in terms of optimizing both the schedule latency and energy consumption. However, obtaining the optimal solution is still useful, e.g., help to implement performance-critical system or give insights into the problem. While available works focus on limited performance metrics of the problem and have high time complexity, this paper proposes an efficient and multi-functional duplication-based scheduling framework based on the satisfiability modulo theory with boolean and integer theories, which enables solving the duplication-based scheduling problems quickly; besides, strategies for modeling the non-preemptive condition in static schedule are studied to improve the efficiency of the proposed framework. The proposed framework is applied to optimize different objectives, including the schedule length, the energy consumption, etc. The proposed framework is tested on a set of applications and platforms. The experimental results demonstrate that the proposed method is more than 10 times quicker than the available method and can reduce the energy consumption by up to 70%. Keywords Satisfiability modulo theory · Task duplication · Multiprocessor · Energy-aware schedule
* Qi Tang [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Q. Tang et al.
1 Introduction Schedule length and energy consumption are two critical aspects of the static schedule that consists of task mapping, ordering and timing. Many scheduling algorithms focus on improving the schedule performance in terms of schedule length using heuristics [1–11] or constraint programming [12, 13]. However, the schedule performance is limited by the inter-processor communication delay incurred by inter-task data precedence, especially for the communication-intensive application. To improve the schedule performance, task duplication is often utilized [14–25]. The duplication-based scheduling algorithm is demonstrated to outperform those algorithms that are free of task duplication. However, the performance improvement gained by task duplication sacrifices computation resources, resulting in more processor occupation, used processor number and energy consumption. To reduce the energy consumption, available dupl
Data Loading...
