TY - JOUR

T1 - Scheduling multisource divisible loads on arbitrary networks

AU - Jia, Jingxi

AU - Veeravalli, Bharadwaj

AU - Weissman, Jon B

PY - 2010/4/1

Y1 - 2010/4/1

N2 - Scheduling multisource divisible loads is a challenging task as different sources should cooperate and share their computing power with others to balance their loads and minimize total computational time. In this study, we attempt to address a generalized divisible load scheduling problem for handling loads from multiple sources on arbitrary networks. This problem is all the more challenging as 1) the topology is arbitrary, 2) in such networks, it is difficult to decide from which source and which route a processing node should receive loads, and 3) processing nodes must be allocated to different sources when they become available. We study two distinct cases of interest, static case and dynamic case, and propose two novel strategies, referred to as Static Scheduling Strategy (SSS) and Dynamic Scheduling Strategy (DSS), respectively. Both strategies work in an iterative fashion. In each iteration, they will use a novel Graph Partitioning (GP) scheme to partition the network such that each source in the network gains a portion of network resources and then these sources cooperate to process their loads. We analyze the performance of DSS using queuing theory and derive upper bounds on a load's average waiting time and a source's average queue length. We use simulation to verify the usefulness and effectiveness of SSS and DSS. Our findings reveal an interesting load insensitive property of SSS and also verify the theoretical upper bound of average queue length at each source in the dynamic case.

AB - Scheduling multisource divisible loads is a challenging task as different sources should cooperate and share their computing power with others to balance their loads and minimize total computational time. In this study, we attempt to address a generalized divisible load scheduling problem for handling loads from multiple sources on arbitrary networks. This problem is all the more challenging as 1) the topology is arbitrary, 2) in such networks, it is difficult to decide from which source and which route a processing node should receive loads, and 3) processing nodes must be allocated to different sources when they become available. We study two distinct cases of interest, static case and dynamic case, and propose two novel strategies, referred to as Static Scheduling Strategy (SSS) and Dynamic Scheduling Strategy (DSS), respectively. Both strategies work in an iterative fashion. In each iteration, they will use a novel Graph Partitioning (GP) scheme to partition the network such that each source in the network gains a portion of network resources and then these sources cooperate to process their loads. We analyze the performance of DSS using queuing theory and derive upper bounds on a load's average waiting time and a source's average queue length. We use simulation to verify the usefulness and effectiveness of SSS and DSS. Our findings reveal an interesting load insensitive property of SSS and also verify the theoretical upper bound of average queue length at each source in the dynamic case.

KW - Arbitrary network

KW - Communication delay

KW - Divisible loads

KW - Multisource

KW - Processing time

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

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

U2 - 10.1109/TPDS.2009.62

DO - 10.1109/TPDS.2009.62

M3 - Article

AN - SCOPUS:77649269910

VL - 21

SP - 520

EP - 531

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 4

M1 - 4815230

ER -