Title :
Performance bounds in list scheduling of redundant tasks on multiprocessors
Author_Institution :
Allied-Signal Aerosp. Technol. Center, Columbia, MD, USA
Abstract :
The author studies the worst-case performance of the LPT (longest processing time first) scheduling algorithm for independent tasks with redundancies on multiprocessor systems. The performance bounds for the case of no redundancy are derived first and are then used to compute those for the case with redundancies. For cases without redundancy, Graham\´s bound w/w/sub 0/>
Keywords :
fault tolerant computing; multiprocessing systems; performance evaluation; scheduling; list scheduling; longest processing time first; multiprocessors; performance bounds; redundancies; redundant tasks; worst-case performance; Fault tolerant systems; Processor scheduling; Real time systems; Redundancy; Scheduling algorithm; Voting;
Conference_Titel :
Fault-Tolerant Computing, 1992. FTCS-22. Digest of Papers., Twenty-Second International Symposium on
Conference_Location :
Boston, MA, USA
Print_ISBN :
0-8186-2875-8
DOI :
10.1109/FTCS.1992.243600
