5653

Orchestration by approximation: mapping stream programs onto multicore architectures

Sardar M. Farhad, Yousun Ko, Bernd Burgstaller, Bernhard Scholz
The University of Sydney, Sydney, Australia
Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems, ASPLOS ’11, 2011

@inproceedings{farhad2011orchestration,

   title={Orchestration by approximation: mapping stream programs onto multicore architectures},

   author={Farhad, S.M. and Ko, Y. and Burgstaller, B. and Scholz, B.},

   booktitle={Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems},

   pages={357–368},

   year={2011},

   organization={ACM}

}

Download Download (PDF)   View View   Source Source   

802

views

We present a novel 2-approximation algorithm for deploying stream graphs on multicore computers and a stream graph transformation that eliminates bottlenecks. The key technical insight is a data rate transfer model that enables the computation of a "closed form", i.e., the data rate transfer function of an actor depending on the arrival rate of the stream program. A combinatorial optimization problem uses the closed form to maximize the throughput of the stream program. Although the problem is inherently NP-hard, we present an efficient and effective 2-approximation algorithm that provides a lower bound on the quality of the solution. We introduce a transformation that uses the closed form to identify and eliminate bottlenecks. We show experimentally that state-of-the art integer linear programming approaches for orchestrating stream graphs are (1) in-tractable or at least impractical for larger stream graphs and larger number of processors and (2) our 2-approximation algorithm is highly efficient and its results are close to the optimal solution for a standard set of StreamIt benchmark programs.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: