Optimal time-varying load sharing for divisible loads

被引:17
作者
Sohn, J [1 ]
Robertazzi, TG [1 ]
机构
[1] SUNY Stony Brook, Dept Elect Engn, Stony Brook, NY 11794 USA
关键词
D O I
10.1109/7.705897
中图分类号
V [航空、航天];
学科分类号
08 ; 0825 ;
摘要
A load sharing problem involving the optimal load allocation of divisible loads in a distributed computing system consisting of N processors interconnected through a bus-oriented network is investigated, For a divisible load, the workload is infinitely divisible so that each fraction of the workload can be distributed and independently computed on each processor. For the first time in divisible load theory, an analysis is provided in the case when the processor speed and the channel speed are time varying due to background jobs submitted to the distributed system with nonnegligible communication delays. A numerical method to calculate the average of the time-varying processor speed and the channel speed and an algorithm to find the optimal allocation of the workload to minimize the total processing finish time are proposed via a deterministic analysis. A stochastic analysis which makes use of Markovian queueing theory is introduced for the case when arrival and departure times of the background jobs are not known.
引用
收藏
页码:907 / 923
页数:17
相关论文
共 21 条
[1]  
[Anonymous], 1996, Scheduling Divisible Loads in Parallel and Distributed Systems
[2]  
BATAINEH S, 1991, PROCEEDINGS OF THE 25TH ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS, P709
[3]   BUS-ORIENTED LOAD SHARING FOR A NETWORK OF SENSOR DRIVEN PROCESSORS [J].
BATAINEH, S ;
ROBERTAZZI, TG .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1991, 21 (05) :1202-1205
[4]   CLOSED-FORM SOLUTIONS FOR BUS AND TREE NETWORKS OF PROCESSORS LOAD SHARING A DIVISIBLE JOB [J].
BATAINEH, S ;
HSIUNG, TY ;
ROBERTAZZI, TG .
IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (10) :1184-1196
[5]  
BATAINEH S, 1997, IEEE T AEROSPACE OCT
[6]  
Bataineh S., 1992, P C INF SCI SYST PRI, P794
[7]   MULTI-INSTALLMENT LOAD DISTRIBUTION IN TREE NETWORKS WITH DELAYS [J].
BHARADWAJ, V ;
GHOSE, D ;
MANI, V .
IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS, 1995, 31 (02) :555-567
[8]   AN EFFICIENT LOAD DISTRIBUTION STRATEGY FOR A DISTRIBUTED LINEAR-NETWORK OF PROCESSORS WITH COMMUNICATION DELAYS [J].
BHARADWAJ, V ;
GHOSE, D ;
MANI, V .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1995, 29 (09) :95-112
[9]   OPTIMAL SEQUENCING AND ARRANGEMENT IN DISTRIBUTED SINGLE-LEVEL TREE NETWORKS WITH COMMUNICATION DELAYS [J].
BHARADWAJ, V ;
GHOSE, D ;
MANI, V .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (09) :968-976
[10]   Scheduling divisible jobs on hypercubes [J].
Blazewicz, J ;
Drozdowski, M .
PARALLEL COMPUTING, 1995, 21 (12) :1945-1956