Fault tolerant mapping onto VLSI/WSI processor arrays

This paper deals with efficient methods for mapping arbitrary parallel algorithms onto faulty general purpose VLSI/WSI data-driven array. First, a brief overview of several architectural designs of the array is given. Next, three directions for the algorithmic improvement of a certain mapping scheme are presented. None of these directions takes into account the possibility of the defects in the array. Therefore, we present two methods which can be used to adapt any of the above algorithmic improvements for the case where defects are present in the array. In the first Map-onto-faulty-array method, faulty cells are taken into consideration during all the phases of the mapping/improvement process. In contrast, the second Map-and-correct method initially ignores faulty cells and takes care of them in the correction phase following the mapping/improvement process