Efficient Variable Partitioning and Scheduling for DSP Processors With Multiple Memory Modules

Qingfeng Zhuge, Edwin Hsing Mean Sha, Bin Xiao, Chantana Chantrapornchai

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)


Multiple on-chip memory modules are attractive to many high-performance digital signal procesisng (DSP) applications. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to be executed in parallel. However, making effective use of multiple memory modules remains difficult. The performance gain in this kind of architecture strongly depends on variable partitioning and scheduling techniques. In this paper, we propose a graph model known as the variable independence graph (VIG) and algorithms to tackle the variable partitioning problem. Our results show that VIG is more effective than interference graph for solving variable partitioning problem. Then, we present a scheduling algorithm known as the rotation scheduling with variable repartition (RSVR) to improve the schedule lengths efficiently on a multiple memory module architecture. This algorithm adjusts the variable partitions during scheduling and generates a compact schedule based on retiming and software pipelining. The experimental results show that the average improvement on schedule lengths is 44.8% by using RSVR with VIG. We also propose a design space exploration algorithm using RSVR to find the minimum number of memory modules and functional units satisfying a schedule length requirement. The algorithm produces more feasible solutions with equal or fewer number of functional units compared with the method using interference graph.
Original languageEnglish
Pages (from-to)1090-1099
Number of pages10
JournalIEEE Transactions on Signal Processing
Issue number4
Publication statusPublished - 1 Apr 2004
Externally publishedYes


  • DSP processor
  • Retiming
  • Scheduling
  • Variable partitioning

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing

Cite this