Optimal assignment with guaranteed confidence probability for trees on heterogeneous DSP systems

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 var ied execution time as a probabilistic random variable and solves heterogeneous assignment with probability (HAP) problem. The solutions to the HAP problem are useful for both hard real time and soft real time systems. We propose optimal algorithms for the HAP problem when the input is a tree or a simple path. The experiments show that our algorithms can effectively obtain the optimal solutions to simple paths and trees. For example, with our algorithms, we can obtain an average reduction of 32.5% on total cost with 90% confidence probability compared with the previ ous work using worst-case scenario.