Author(s)

Chih-Yung Chang Yuh-Shyan Chen and Chu-Bo Kuo

Abstract

A generalized fault-tolerant sorting algorithm on product network Chih-Yung Chang % Yuh-Shyan Chen" and Chu-Bo Kuo~ 'Department of Computer Information Science, Aletheia University, Taiwan ^Department of Computer Science and Information Engineering, Chun-Hua University, Taiwan Abstract Product networks define a class of topologies that are used very often such as mesh, tori, and hypercube, etc. This paper proposes a generalized algorithm for fault-tolerant parallel sorting in the product networks. To tolerate multiple faulty nodes, product network is partitioned into a number of subgraphs such that each subgraph contains at most one fault. Our generalized sort algorithm is divided into two steps. First, a single-fault sorting operation is presented to correctly execute on each faulty subgraph containing one fault. Second, each subgraph is consid- ered as a supernode, and a fault-tolerant multiway merge operation is presented to recursively merge two sorted subsequences into one s

Keywords