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

dc.contributor.authorCheng, Sheng-Tzongen_US
dc.contributor.authorAgrawala, Ashok K.en_US
dc.date.accessioned2004-05-31T22:22:59Z
dc.date.available2004-05-31T22:22:59Z
dc.date.created1994-10en_US
dc.date.issued1998-10-15en_US
dc.description.abstractWe 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 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 the complexity of 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. (Also cross-referenced as UMIACS-TR-93-4.1)en_US
dc.format.extent481944 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/579
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3020.1en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-93-4.1en_US
dc.titleOptimal Replication of Series-Parallel Graphs for Computation-Intensive Applicationsen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3020.1.ps
Size:
470.65 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3020.1.pdf
Size:
314.49 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3020.1.ps