Reasoning About Permutations in Regular Arrays
Bjorn Lisper, Sanjay Rajopadhye
Committee:
Technical Report(Aug 1991)
Keywords:

We present a general theoretical model for reasoning about prescheduled data transfers in processor arrays, using a notation called transfer relations. We show how our model can be used for the verification of such transfer operations, and also present necessary and sufficient conditions under which they can be implemented with purely local control. We indicate how it is possible to automate the verification and synthesis. We illustrate our model by describing a class of data permutation networks, designed as interfaces between different systolic arrays. The permutations performed by such networks include many standard operations such as skewing, rotation, reflection, transposition, etc.