Coding techniques for fault-tolerant parallel prefix computations in Abelian groups

Abstract

This paper presents coding techniques that can be used to provide fault tolerance to a parallel prefix computation that is performed on a binary tree of processing nodes. More specifically, we discuss how a parallel prefix computation in an arbitrary Abelian group can be protected using group homomorphisms. The proposed approach is general enough to handle a variety of group operations of interest and allows for designs ranging from simple parity schemes to full replication. Error detecting and correcting mechanisms are used solely at the leaf nodes and can capture faults at any node or link within the binary tree architecture on which the parallel prefix computation is performed. Furthermore, by tracking the propagation of errors in the binary tree, our method can identify a processing node that has permanently failed based on information from simple error detecting mechanisms at the leaf nodes. © The British Computer Society; all rights reserved.