Back to Search
Start Over
Optimizing the Reliability of Streaming Applications Under Throughput Constraints
- Source :
- International Journal of Parallel Programming, International Journal of Parallel Programming, Springer Verlag, 2011, 39 (5), pp.584-614. ⟨10.1007/s10766-011-0165-6⟩, International Journal of Parallel Programming, 2011, 39 (5), pp.584-614. ⟨10.1007/s10766-011-0165-6⟩
- Publication Year :
- 2011
- Publisher :
- Springer Science and Business Media LLC, 2011.
-
Abstract
- Mapping a pipelined application onto a distributed and parallel platform is a challenging problem. The problem becomes even more difficult when multiple optimization criteria are involved, and when the target resources are heterogeneous (processors and communication links) and subject to failures. This paper investigates the problem of mapping pipelined applications, consisting of a linear chain of stages executed in a pipeline way, onto such platforms. The objective is to optimize the reliability under a performance constraint, i.e., while guaranteeing a threshold throughput. In order to increase reliability, we replicate the execution of stages on multiple processors. We compare interval mappings, where the application is partitioned into intervals of consecutive stages, with general mappings, where stages may be partitioned without any constraint, thereby allowing a better usage of processors and communication network capabilities. However, the price to pay for general mappings is a dramatic increase in the problem complexity. We show that computing the period of a given general mapping is an NP-complete problem, and we give polynomial bounds to determine a (conservative) approximated value. On the contrary, the period of an interval mapping obeys a simple formula, and we provide an optimal dynamic programming algorithm for the bi-criteria interval mapping problem on homogeneous platforms. On the more practical side, we design a set of efficient heuristics, and we compare the performance of interval and general mapping strategies through extensive simulations.
- Subjects :
- Mathematical optimization
Computer science
Pipeline (computing)
Reliability (computer networking)
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
Interval (mathematics)
01 natural sciences
Telecommunications network
Theoretical Computer Science
Dynamic programming
010201 computation theory & mathematics
Theory of computation
0202 electrical engineering, electronic engineering, information engineering
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Heuristics
Throughput (business)
ComputingMilieux_MISCELLANEOUS
Software
Information Systems
Subjects
Details
- ISSN :
- 15737640 and 08857458
- Volume :
- 39
- Database :
- OpenAIRE
- Journal :
- International Journal of Parallel Programming
- Accession number :
- edsair.doi.dedup.....9cefef316670e09a7ba8369ddadcb315