Assignment and scheduling of real-time DSP applications for heterogeneous functional units

Zili Shao, Qingfeng Zhuge, Yi He, Chun Xue, Meilin Liu, Edwin H.M. Sha

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

1 Citation (Scopus)

Abstract

In high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs), an important problem is how to assign a proper FU type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. In this paper, we propose a two-phase approach to solve this problem. In the first phase, we solve heterogeneous assignment problem, i.e., how to assign a proper FU type to a DSP application such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained from the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. We prove heterogeneous assignment problem is NP-complete and propose several algorithms to solve it. The experiments show that Algorithm DFG_Assign_Repeat is the best that gives a reduction of 25.7% on total cost compared with the previous work.
Original languageEnglish
Title of host publicationProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Pages851-860
Number of pages10
Volume18
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) - Santa Fe, NM, United States
Duration: 26 Apr 200430 Apr 2004

Conference

ConferenceProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
CountryUnited States
CitySanta Fe, NM
Period26/04/0430/04/04

ASJC Scopus subject areas

  • Engineering(all)

Cite this