Constructing Compact Logical Arrays under Flexible Rerouting Schemes

In a multiprocessor array, some processing elements (PEs) fail to function normally due to hardware defects or soft faults caused by overheating, overload or occupancy by other running applications. Fault-tolerant reconfiguration reorganizes fault-free PEs to a logical topology by changing the interconnection among PEs. This paper develops an efficient heuristic algorithm, denoted as CLA, to construct maximum logical array (MLA) with short interconnects under flexible rerouting schemes. In CLA, two MLAs are generated using an existing algorithm FLX, and are then utilized to produce the target logical array. The middle column of the target logical array is generated by forming the straightest column on an area bounded by two logical columns of the two MLAs. Other columns are generated by forming compact columns on relative areas. The problem of finding a compact logical column on an given area is solved by modeling it as a shortest path problem on a directed graph with weights where both vertices and edges of the graph are associated with nonnegative costs. Experimental results validate the efficiency of the the proposed algorithm. For 128 × 128 host arrays with 40% unavailable PEs, the proposed approach improves existing algorithm up to 44% in terms of interconnection length. In addition, the improvement increases with the increasing fault density, implying that CLA is more scalable than the existing algorithm.