Efficient assignment with guaranteed probability for heterogeneous parallel DSP

M. Qiu, C. Xue, Zili Shao, Q. Zhuge, M. Liu, E. Sha

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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.
Original languageEnglish
Title of host publicationThe 12th IEEE International Conference on Parallel and Distributed Systems (ICPADS 2006), Minneapolis, MN, USA, July 2006
PublisherIEEE Computer Society
Number of pages8
Publication statusPublished - 2006
EventThe 12th International Conference on Parallel and Distributed Systems [ICPADS] - Minneapolis, United States
Duration: 12 Jul 200615 Jul 2006


ConferenceThe 12th International Conference on Parallel and Distributed Systems [ICPADS]
Country/TerritoryUnited States

Cite this