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

Abstract

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
Pages623-630
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

Conference

ConferenceThe 12th International Conference on Parallel and Distributed Systems [ICPADS]
CountryUnited States
CityMinneapolis
Period12/07/0615/07/06

Cite this