Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications

Sheng Tzong Cheng, Ashok K. Agrawala

Research output: Contribution to journalArticle

Abstract

We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for a suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has complexity O(n22nM), while the approximation solution has O(n4M2), where n is the number of processors in the system and M is the number of tasks in the graph.

Original languageEnglish
Pages (from-to)113-129
Number of pages17
JournalJournal of Parallel and Distributed Computing
Volume28
Issue number2
DOIs
Publication statusPublished - 1995 Aug 1

Fingerprint

Series-parallel Graph
Replication
Costs
Optimal Solution
Interprocessor Communication
Task Graph
Branch and Bound Method
Communication
Communication Cost
Approximation
Assignment Problem
Graph in graph theory
Branch and bound method
NP-complete problem
Minimise
Numerical Results

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this

@article{27c1dd91ceeb441f951fcc8eda99b552,
title = "Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications",
abstract = "We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for a suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has complexity O(n22nM), while the approximation solution has O(n4M2), where n is the number of processors in the system and M is the number of tasks in the graph.",
author = "Cheng, {Sheng Tzong} and Agrawala, {Ashok K.}",
year = "1995",
month = "8",
day = "1",
doi = "10.1006/jpdc.1995.1094",
language = "English",
volume = "28",
pages = "113--129",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "2",

}

Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications. / Cheng, Sheng Tzong; Agrawala, Ashok K.

In: Journal of Parallel and Distributed Computing, Vol. 28, No. 2, 01.08.1995, p. 113-129.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications

AU - Cheng, Sheng Tzong

AU - Agrawala, Ashok K.

PY - 1995/8/1

Y1 - 1995/8/1

N2 - We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for a suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has complexity O(n22nM), while the approximation solution has O(n4M2), where n is the number of processors in the system and M is the number of tasks in the graph.

AB - We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for a suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has complexity O(n22nM), while the approximation solution has O(n4M2), where n is the number of processors in the system and M is the number of tasks in the graph.

UR - http://www.scopus.com/inward/record.url?scp=58149323733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58149323733&partnerID=8YFLogxK

U2 - 10.1006/jpdc.1995.1094

DO - 10.1006/jpdc.1995.1094

M3 - Article

AN - SCOPUS:58149323733

VL - 28

SP - 113

EP - 129

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 2

ER -