Buffer minimization in pipelined SDF scheduling on multi-core platforms

Yuankai Chen*, Hai Zhou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

With the increasing number of cores available on modern processors, it is imperative to solve the problem of mapping and scheduling a synchronous data flow graph onto a multi-core platform. Such a solution should not only meet the performance constraint, but also minimize resource usage. In this paper, we consider the pipeline scheduling problem for acyclic synchronous dataflow graph on a given number of cores to minimize the total buffer size while meeting the throughput constraint. We propose a two-level heuristic algorithm for this problem. The inner level finds the optimal buffer size for a given topological order of the input task graph; the outer level explores the space of topological order by applying perturbation to the topological order to improve buffer size. We compared our proposed algorithm to an enumeration algorithm which is able to generate optimal solution for small graphs, and a greedy algorithm which is able to run on large graphs. The experimental results show that our two-level heuristic algorithm achieves near-optimal solution compared to the enumeration algorithm, with only 0.8% increase in buffer size on average but with much shorter runtime, and achieves 38.8% less buffer usage on average, compared to the greedy algorithm.

Original languageEnglish (US)
Title of host publicationASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference
Pages127-132
Number of pages6
DOIs
StatePublished - Apr 26 2012
Event17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 - Sydney, NSW, Australia
Duration: Jan 30 2012Feb 2 2012

Other

Other17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
CountryAustralia
CitySydney, NSW
Period1/30/122/2/12

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Buffer minimization in pipelined SDF scheduling on multi-core platforms'. Together they form a unique fingerprint.

Cite this