Name
Abstract | ||
|---|---|---|
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) intractable 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1950365.1950406 | ASPLOS |
Keywords | Field | DocType |
stream graph transformation,larger stream graph,data rate transfer model,2-approximation algorithm,stream program,deploying stream graph,stream graph,multicore architecture,mapping stream program,data rate transfer function,arrival rate,closed form,transfer function,lower bound,graph transformation,multicore | Approximation algorithm,Bottleneck,Data stream clustering,Computer science,Parallel computing,Combinatorial optimization,Theoretical computer science,Multiprocessing,Integer programming,Linear programming,Multi-core processor | Conference |
Volume | Issue | ISSN |
39 | 1 | 0163-5964 |
Citations | PageRank | References |
20 | 0.80 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sardar M. Farhad | 1 | 28 | 2.68 |
| Yousun Ko | 2 | 38 | 3.49 |
| Bernd Burgstaller | 3 | 133 | 17.54 |
| Bernhard Scholz | 4 | 104 | 10.59 |