A reconfigurable boolean n-cube architecture under faults

A reconfigurable modular Boolean n-cube (RMB_n) is proposed in this paper. We embed spare elements, including nodes (processors), switches and links, into each module in order to reconfigure a failed system. The proposed scheme is constructed in two levels. The first level is to build a fault-tolerant module (FTM), using an original 4-cube of 16 nodes with 4 spare nodes and some switches with links. Then, in the second level, we use several FTMs to construct the desired RMB_n, n ≥ 4, via connecting the corresponding nodes between any two adjacent FTMs. In our scheme, each spare node can replace any faulty node in the FTM via rebuilding the interconnections, i.e., each FTM can tolerate 4 faulty nodes. A reconfiguration algorithm is developed to choose an adequate spare node such that a faulty node can be replaced. We also develop a distributed routing algorithm to route messages from any source node to any destination node around the faulty nodes. Finally, the RMB_n is evaluated and compared with previous works. It is shown that the proposed scheme can achieve the same or higher reliability while using fewer hardware costs.