Dynamic Task Reconfiguration in the Faulty Hypercube Multiprocessor


IEICE TRANSACTIONS on Information and Systems   Vol.E74-D   No.2   pp.435-446
Publication Date: 1991/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing

Full Text: PDF>>
Buy this Article

This paper considers processor utilization in faulty hypercube multiprocessor. The utilization is proportional to the continuity of processor allocation model based on Gray code. Busy and faulty processors make this model fragmented. That prevents assigning of larger tasks onto hypercube and decreases processor utilization. A set of procedures is derived which reassigns active tasks so that a new task configuration along with faulty processors makes as little damage as possible to the continuity of allocation model. First, a hypercube fragmentation measure is defined and a task reassigning technique presented. Then, procedures are given which determine: (1) active tasks to be reassigned, (2) their new optimal locations and (3) the shortest reassigning paths. At last, it is proved that while increasing processor utilization, presented scheme minimizes task reconfiguration overhead.