Task allocation algorithms for maximizing reliability of distributed computing systems

被引:95
作者
Kartik, S [1 ]
Murthy, CSR [1 ]
机构
[1] INDIAN INST TECHNOL, DEPT COMP SCI & ENGN, MADRAS 600036, TAMIL NADU, INDIA
关键词
task allocation; distributed computing; reliability; optimality; search tree; heuristics;
D O I
10.1109/12.600888
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we consider the problem of finding an optimal and suboptimal task allocation (i.e., to which processor should each module of a task or program be assigned) in distributed computing systems with the goal of maximizing the system reliability (i.e., the probability that the system can run the entire task successfully). The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. Here we present an algorithm for this problem, which uses the idea of branch and bound with underestimates for reducing the computations in finding an optimal task allocation. The algorithm reorders the list of modules to allow a subset of modules that do not communicate with one another to be assigned last, for further reduction in the computations of optimal task allocation for maximizing reliability. We also present a heuristic algorithm which obtains suboptimal task allocations in a reasonable amount of computational time. We study the performance of the algorithms over a wide range of parameters such as the number of modules, the number of processors, the ratio of average execution cost to average communication cost, and the connectivity of modules. We demonstrate the effectiveness of our algorithms by comparing with recent competing task allocation algorithms for maximizing reliability available in the literature.
引用
收藏
页码:719 / 724
页数:6
相关论文
共 11 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]   TASK ALLOCATION IN FAULT-TOLERANT DISTRIBUTED SYSTEMS [J].
BANNISTER, JA ;
TRIVEDI, KS .
ACTA INFORMATICA, 1983, 20 (03) :261-281
[3]   PARTITIONING PROBLEMS IN PARALLEL, PIPELINED, AND DISTRIBUTED COMPUTING [J].
BOKHARI, SH .
IEEE TRANSACTIONS ON COMPUTERS, 1988, 37 (01) :48-57
[4]   PARAMETRIC COMBINATORIAL COMPUTING AND A PROBLEM OF PROGRAM MODULE DISTRIBUTION [J].
GUSFIELD, D .
JOURNAL OF THE ACM, 1983, 30 (03) :551-563
[5]  
HARIRI S, 1986, P IEEE ACM 1986 FALL, P344
[6]  
KARTIK S, 1994, THESIS INDIAN I TECH
[7]  
Nilsson N. J., 1971, Problem -solving methods in artificial intelligence
[8]   TASK ALLOCATION FOR MAXIMIZING RELIABILITY OF DISTRIBUTED COMPUTER-SYSTEMS [J].
SHATZ, SM ;
WANG, JP ;
GOTO, M .
IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (09) :1156-1168
[10]   MULTIPROCESSOR SCHEDULING WITH AID OF NETWORK FLOW ALGORITHMS [J].
STONE, HS .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1977, 3 (01) :85-93