Makespan Minimization for Multiprocessor Real-Time Systems under Thermal and Timing Constraints
Abstract
With the continued scaling of the CMOS device, the exponential increase in power density has strikingly elevated the temperature of on-chip systems. In this paper, the problem of allocating and scheduling frame-based real-time applications is addressed to multiprocessors to minimize the makespan under the thermal and timing constraints. The proposed algorithms consist of offline and online components. The offline component assigns the applications accepted at static time to processors in a way that the finish time of processors are balanced. The online component firstly selects the processor with the highest allocation probability for each application accepted at runtime. The allocation probability is calculated by taking the processor workload and temperature profiles into consideration. The higher allocation probability of a processor shows the better performance with respect to makespan and temperature can be achieved by executing the application on this processor. Then, the operating frequencies of applications are determined by making the most of slack in order to reduce the peak temperature under the timing constraint. Extensive simulations were performed to validate the effectiveness of the proposed approach. Experimental results have shown that the static makespan of the proposed scheme is very close to the optimal schedule length within a small margin varying from 0.118s to 0.249s, and the dynamic makespan of the proposed scheme can be adapted to satisfy varying system design constraints. The peak temperature of the proposed algorithms can be up to lower than that of the benchmarking schemes.
This paper was recommended by Regional Editor Tongquan Wei.
