Bitonic sort on a network computer with a node failure

✍ Scribed by Hiromi Kobayashi; Hidetake Funaki; Hiroaki Yamamaoto; Hiroo Yamaura

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 610 KB
• Volume: 25
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690251002

✦ Synopsis

Abstract

Massively parallel computers are being realized for aiming at high performance. Bitonic sort is an efficient algorithm for network computers. But generally, it is impossible to use a bitonic sort algorithm on a network computer with a node failure.

This paper presents a fault‐tolerant scheme of bitonic sort algorithm for a network computer that makes it possible to tolerate a node failure without an additional hardware cost. The method does not have hardware redundancy but has software redundancy. The method does not depend on the network topology. However, the method takes about two times as many steps as that of original bitonic sort.

This paper also shows that the method is applicable to a chordal ring connected computer as an example.