Efficient Assignment with Guaranteed Probability for Heterogeneous Parallel DSP
Meikang Qiu, Chun Jason Xue, Zili Shao, Qingfeng Zhuge, Meilin Liu, Edwin H.‐M. Sha · 2006
In real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs), it is critical to select the best FU for each task. However, some tasks may not have fixed execution times. This paper models each varied execution time as a probabilistic random variable and solves heterogeneous assignment with probability (HAP) problem. The solution of the HAP problem assigns a proper FU type to each task such that the total cost is minimized while the timing constraint is satisfied with a guaranteed confidence probability. The solutions to the HAP problem are useful for both hard real-time and soft real-time systems. Two algorithms, one is optimal and the other is heuristic, are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost with guaranteed confidence probabilities satisfying timing constraints. For example, our algorithms achieve an average reduction of 33.5 % on total cost with 90 % confidence probability satisfying timing constraints compared with the previous work using worstcase scenario. 1