An efficient multi-functional duplication-based scheduling framework for multiprocessor systems

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%.