Efficient assignment with guaranteed probability for heterogeneous parallel DSP

In real-time digital signal processing (DSP) architec-tures using heterogeneous functional units (FUs), it is crit-ical to select the best FU for each task. However, some tasks may not have fixed execution times. This paper mod-els each varied execution time as a probabilistic random variable and solves heterogeneous assignment with prob-ability (HAP) problem. The solution of the HAP problem assigns a proper FU type to each task such that the to-tal cost is minimized while the timing constraint is satis-fied with a guaranteed confidence probability. The solu-tions 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 ef-fectively 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 worst-case scenario.