Efficient exploration of nonuniform space-time transformations for optimal systolic array synthesis

A method is presented for mapping conditional affine resources equations (CAREs) into systolic-type architectures. The tasks of localization and of space-time reindexing are formulated as a single branch and broad search problem. The combined formulation allows these problems to be solved concurrently and thus ensures that true optimal solutions are derived. The employed space-time reindexing method applies different affine transforms to different array variables. The employed space-time reindexing method applies different affine transforms to different array variables. Multistage localization is effected by a search-based technique which exploits specific characteristics of the combined formulation. The search procedure comprehensively explores the space of designs defined by the constraints of these methods. For a given input, all legal designs which optimize a delay-based objective function are generated. The method has been implemented as part of the array synthesis system DESCARTES. Example problems are presented to demonstrate the feasibility of the technique