Mapping loop algorithms into reconfigurable mesh connected processor array

A method for mapping loop algorithms into mesh processor arrays is presented. The method can automatically detect and utilize parallelism in the algorithm. It is faster than similar methods with such capabilities, and it produces near-optimal solutions in most cases. Thus, it is suitable for mapping algorithms into reconfigurable systems. When the processors have local memories, the search space of the mapping can be reduced by storing data in the local memories, and the method takes advantage of this possibility. A technique to reduce data dependencies by distributing the functions in a loop body to different processors is also discussed. Since data dependencies determine the connections and the search space, this technique is useful in reducing the connections as well as speeding up the mapping. In order to explain the realization issues of the mapping, a novel mesh architecture with enhanced reconfigurable communication is briefly described.<>