文章基本信息

标题：Fault-Free Maximal Submeshes in Faulty Torus-Connected Multicomputers
本地全文：下载
作者：Seong-Moo Yoo ; Hee Yong Youn ; Hyunseung Choo 等
期刊名称：Informatica
印刷版ISSN：1514-8327
电子版ISSN：1854-3871
出版年度：2004
卷号：28
期号：3
页码：289-296
出版社：The Slovene Society Informatika, Ljubljana
摘要：In a parallel computer system with faulty processors, it is highly desirable to reconfigure the system by eliminating the faulty ones and thereby restore the system to some operational state. In the reconfiguration maintaining the maximum size fault-free subsystem is the main problem. In this paper, we propose an efficient scheme for identifying maximum size fault-free submeshes in a faulty torus-connected multicomputer system. For this, the relations between two submeshes have been defined. Then we take two-phase approach. In the first phase, an efficient algorithm for determining maximal faulty submeshes in a faulty torus has been introduced. In the second phase, we have introduced a procedure to identify the maximal fault-free submeshes by removing all faulty submeshes from a whole torus. The time complexity of the proposed scheme is O(N_f³) where N_f is the number of faulty processors in a 2D torus. The proposed scheme can be utilized to the task allocation in 2D tori in the presence of failed nodes.
关键词：fault-free subsystem; maximal submeshes; reconfiguration; torus-connected multicomputers; virtual submeshes