Efficient assignment and scheduling for heterogeneous DSP systems

Zili Shao, Qingfeng Zhuge, Chun Xue, Edwin H.M. Sha

Research output: Journal article publicationJournal articleAcademic researchpeer-review

58 Citations (Scopus)


This paper addresses high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs). For such special purpose architecture synthesis, 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. We propose a two-phase approach to solve this problem. In the first phase, we solve the heterogeneous assignment problem, i.e., how to assign proper FU types to applications such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained in 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 that the heterogeneous assignment problem is NP-complete. Efficient algorithms are proposed to find an optimal solution when the given DFG is a simple path or a tree. Three other algorithms are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost compared with the previous work.
Original languageEnglish
Pages (from-to)516-525
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number6
Publication statusPublished - 1 Jun 2005
Externally publishedYes


  • Assignment
  • DSP
  • Heterogeneous
  • High level synthesis
  • Real-time
  • Scheduling

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this