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

M. Qiu, M. Liu, X. Chun, Zili Shao, Q. Zhuge, E.H.M. Sha

Research output: Unpublished conference presentation (presented paper, abstract, poster)Conference presentation (not published in journal/proceeding/book)Academic researchpeer-review


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.
Original languageEnglish
Number of pages6
Publication statusPublished - 2005
EventIASTED International Conference on Parallel and Distributed Computing Systems -
Duration: 1 Jan 2005 → …


ConferenceIASTED International Conference on Parallel and Distributed Computing Systems
Period1/01/05 → …


  • Assignment
  • Probability
  • Heterogeneous
  • Real time
  • DSP
  • Synthesis

Cite this