Mapping multiple algorithms into a reconfigurable systolic array

Systolic array is a well known VLSI architecture to achieve extensive parallel and pipelining computing. Many systolic designs have been reported. All are algorithm based, that is one design is only for solving one specific problem. In this paper, the special purpose systolic architecture has been extended into a reconfigurable one and a systematic design approach to mapping two or more algorithms into a single reconfigurable systolic array is presented. First multiple algorithms are mapped into a reconfigurable systolic array that is able to compute one algorithm at a time with proper control settings. Second the reconfigurable systolic array is extended by using time or space redundancy so that it can compute multiple algorithms simultaneously. In addition, the optimal mapping, which minimizes the total hardware cost and computation time, is explored and the necessary condition of the transformation for computing multiple problem instances is also proposed. According to this condition, the search space of finding the optimal mapping can be significantly reduced.