Abstract | ||
---|---|---|
We tackle pipeline workflow applications that are executed on a distributed platform with setup times. Several computation stages are interconnected as a linear application graph, and each stage holds a buffer of limited size where intermediate results are stored and a processor setup time occurs when passing from one stage to another. In this paper, we focus on interval mappings (consecutive stages mapped on a same processor), and the objective is the throughput optimization. Even when neglecting setup times, the problem is NP-hard on heterogeneous platforms and we therefore restrict to homogeneous resources. We provide an optimal algorithm for constellations with identical buffer capacities. When buffer sizes are not fixed, we deal with the problem of allocating the buffers in shared memory and present a b/(b+1)-approximation algorithm. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-36949-0_8 | international conference on parallel processing |
Keywords | Field | DocType |
identical buffer capacity,setup time,consecutive stage,pipeline workflow scheduling,approximation algorithm,heterogeneous platform,computation stage,buffer size,homogeneous resource,processor setup time,throughput optimization,optimal algorithm | Graph,Workflow scheduling,Shared memory,Computer science,Parallel computing,Constellation,Throughput,Workflow,restrict,Computation,Distributed computing | Conference |
Volume | ISSN | Citations |
7640 | 0302-9743 | 4 |
PageRank | References | Authors |
0.42 | 10 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anne Benoit | 1 | 14 | 2.10 |
Mathias Coqblin | 2 | 4 | 0.76 |
Jean-Marc Nicod | 3 | 95 | 18.10 |
Laurent Philippe | 4 | 71 | 12.95 |
Veronika Rehn-sonigo | 5 | 62 | 9.62 |