TY - JOUR
T1 - Redundant Task-Allocation in Multicomputer Systems
AU - Cherkassky, Vladimir
AU - Chen, Chien In Henry
PY - 1992/9
Y1 - 1992/9
N2 - This paper describes a simple yet effective method to improve multicomputer/multiprocessor system reliability via redundant allocation of tasks to computers (processors). Given any known (nonredundant) scheduling strategy, tasks are allocated to processors statically and redundantly using k-circular shifting (kCS) algorithm, so that if some processors fail during the execution, all tasks can be completed on the remaining processors (but at a longer time). Due to static pre-allocation of tasks this method is simpler and thus more practical than wellknown dynamic reconfiguration and rollback recovery techniques in multiprocessor systems. We discuss in detail redundant allocation of independent tasks to identical processors (computers), subject to real-time constraints on total execution time, and derive analytic reliability estimates for this case. The Longest Processing Time scheduling is given as an example of nonredundant deterministic scheduling for independent tasks. Finally, we discuss processor utilization for redundant task-allocation, and compare it with standby redundancy; our kCS algorithm achieves much higher processor utilization than standby redundancy.
AB - This paper describes a simple yet effective method to improve multicomputer/multiprocessor system reliability via redundant allocation of tasks to computers (processors). Given any known (nonredundant) scheduling strategy, tasks are allocated to processors statically and redundantly using k-circular shifting (kCS) algorithm, so that if some processors fail during the execution, all tasks can be completed on the remaining processors (but at a longer time). Due to static pre-allocation of tasks this method is simpler and thus more practical than wellknown dynamic reconfiguration and rollback recovery techniques in multiprocessor systems. We discuss in detail redundant allocation of independent tasks to identical processors (computers), subject to real-time constraints on total execution time, and derive analytic reliability estimates for this case. The Longest Processing Time scheduling is given as an example of nonredundant deterministic scheduling for independent tasks. Finally, we discuss processor utilization for redundant task-allocation, and compare it with standby redundancy; our kCS algorithm achieves much higher processor utilization than standby redundancy.
KW - Graceful degradation
KW - Multiprocessor system
KW - Processor utilization
KW - Redundant task-allocation
KW - Reliability prediction
UR - http://www.scopus.com/inward/record.url?scp=0026925322&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026925322&partnerID=8YFLogxK
U2 - 10.1109/24.159795
DO - 10.1109/24.159795
M3 - Article
AN - SCOPUS:0026925322
SN - 0018-9529
VL - 41
SP - 336
EP - 342
JO - IEEE Transactions on Reliability
JF - IEEE Transactions on Reliability
IS - 3
ER -