Constant time fault tolerant algorithms for a linear array with a reconfigurable pipelined bus system

摘要

Recently, researchers have proposed many models using reconfigurable optically pipelined buses. Most algorithms developed for these models assume that a healthy system is available. The only previous work in this area considers faulty processors or hardware for an N-processor linear array with a reconfigurable pipelined bus system (LARPBS), resulting in fault tolerant algorithms that run in O(log N) time. We extend and improve upon previous results by considering new fault scenarios and slight modifications to the LARPBS model. By modifying the switches on the receiving segment of an LARPBS, a reasonable, low-cost extension to the model, we are able to achieve fault tolerant algorithms that execute in O(1) time rather than O(log N) time. The fault tolerant algorithms that we consider are key basic fundamental algorithms, such as compaction, binary prefix sums, and sorting, that all execute in constant time on a healthy LARPBS. As the algorithms improved are building blocks for more complex algorithms, the results presented in this paper will extend to those more complex algorithms as well. (c) 2004 Elsevier Inc. All rights reserved.