Optimizing the Reliability of Streaming Applications Under Throughput Constraints

Benoit, Anne; Bouziane, Hinde; Robert, Yves
October 2011
International Journal of Parallel Programming;Oct2011, Vol. 39 Issue 5, p584
Academic Journal
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.


Related Articles

  • A Message-Passing Hardware/Software Cosimulation Environment for Reconfigurable Computing Systems. SaldaƱa, Manuel; Ramalho, Emanuel; Chow, Paul // International Journal of Reconfigurable Computing;2009, p1 

    High-performance reconfigurable computers (HPRCs) provide a mix of standard processors and FPGAs to collectively accelerate applications. This introduces new design challenges, such as the need for portable programming models across HPRCs and system-level verification tools. To address the need...

  • Configuration of fully replicated distributed database system over wide area networks. Gavish, Bezalel; Suh, Myung W. // Annals of Operations Research;1992, Vol. 36 Issue 1-4, p167 

    The cost and performance of a distributed database system (DDS) depends on data distribution and database server configuration across the network. An inappropriate allocation of data and database servers could result in a DDS which is either too costly or unacceptably slow. This paper models the...

  • An Efficient Supplier Side Scheduling Algorithm for P2P Live Streaming System. Hongyun Yang; Xiaoliang Zhu; Xuhui Chen // International Journal of Multimedia & Ubiquitous Engineering;Nov2013, Vol. 8 Issue 6, p377 

    Chunk scheduling is one of the key components in P2P streaming systems. Most of previous research works focus on receiver side's chunk/peer selection strategies and neglect the service order and available uplink bandwidth allocation problem at supplier side, which will cause the user's video...

  • Statistical measures for quantifying task and machine heterogeneities. Al-Qawasmeh, Abdulla M.; Maciejewski, Anthony A.; Haonan Wang; Smith, Jay; Siegel, Howard Jay; Potter, Jerry // Journal of Supercomputing;Jul2011, Vol. 57 Issue 1, p34 

    We study heterogeneous computing (HC) systems that consist of a set of different machines that have varying capabilities. These machines are used to execute a set of heterogeneous tasks that vary in their computational complexity. Finding the optimal mapping of tasks to machines in an HC system...

  • On linear programs with linear complementarity constraints. Hu, Jing; Mitchell, John; Pang, Jong-Shi; Yu, Bin // Journal of Global Optimization;May2012, Vol. 53 Issue 1, p29 

    The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and...

  • An Effective Constructive Heuristic to Find near Optimal Solution for Scheduling and Traveling Salesman Problem. Mirabi, Mohammad // Australian Journal of Basic & Applied Sciences;2011, Vol. 5 Issue 6, p484 

    This paper presents a new constructive approach based on simulated annealing for the large scope of scheduling problem can be assumed as traveling salesman problem (TSP). The main contribution of this research is developing a new definition of TSP. We solve the TSP when there are no roads...

  • Comparing mathematical and heuristic rules for solving single machine scheduling problem with release and due date constraints. Yong Zhan; Haitao Zhu; Yuguang Zhong // Applied Mechanics & Materials;2014, Issue 635-637, p1707 

    The purpose of this paper is to compare a mixed integer programming(MIP) model, and heuristic rules based on their practical efficiency and the accuracy of results to tackle the minimum lateness single machine scheduling problem with release and due date constraints. Extensive numerical...

  • Assembling networks of microbial genomes using linear programming. Holloway, Catherine; Beiko, Robert G. // BMC Evolutionary Biology;2010, Vol. 10, p360 

    Background: Microbial genomes exhibit complex sets of genetic affinities due to lateral genetic transfer. Assessing the relative contributions of parent-to-offspring inheritance and gene sharing is a vital step in understanding the evolutionary origins and modern-day function of an organism, but...

  • LPOCS: A Novel Linear Programming Optimization Coverage Scheme in Wireless Sensor Networks. ZEYU SUN; YUNXING SHU; XIAOFEI XING; WEI WEI; HOUBING SONG; WEI LI // Adhoc & Sensor Wireless Networks;2016, Vol. 33 Issue 1-4, p173 

    Coverage rate is one of important standards for evaluating network system performance of wireless sensor networks. This paper presents a novel coverage optimization algorithm under a complex dynamic parameter model, which shows the expectation and tolerance of sensor node coverage. The process...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics