Optimally removing intercore communication overhead for streaming applications on MPSoCs

Yi Wang, Duo Liu, Zhiwei Qin, Zili Shao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)


This paper aims to totally remove intercore communication overhead with joint computation and communication task scheduling for streaming applications on Multiprocessor System-on-Chips (MPSoCs). Our basic idea is to let some computation and communication tasks be executed in earlier periods (the added periods are called the prologue) such that intercore data transfer can be finished before the execution of the tasks that need the data to start. In particular, we solve the following problem: how to do rescheduling in such a way that the schedule length can be minimized with the minimum prologue length (the number of periods in the prologue) while the intercore communication overhead can be totally removed? To solve this problem, we first perform schedulability analysis and obtain the upper bound of the times needed to reschedule each computation task. Then we formulate the problem as an Integer Linear Programming (ILP) formulation and obtain an optimal solution. We evaluate our technique with a set of benchmarks from both real-life streaming applications and synthetic task graphs. The experimental results show that our technique can achieve significant reductions in schedule length and energy consumption compared with the previous work.
Original languageEnglish
Article number6109236
Pages (from-to)336-350
Number of pages15
JournalIEEE Transactions on Computers
Issue number2
Publication statusPublished - 2 Jan 2013


  • intercore communication
  • MPSoC
  • retiming
  • streaming applications
  • Task scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this