Design methodology for the implementation of multidimensional circular convolution

A systematic methodology for the parallel implementation of the multidimensional circular convolution algorithm is introduced. The methodology can be applied when at least one of the convolved sequences is separable. The multidimensional algorithm is described hierarchically by two levels of two-dimensional directed graphs. The top level corresponds to a graph, each node of which represents a onedimensional convolution, while the lower level graph specifies the elementary operations within the one-dimensional algorithm. The array architectures result systematically from the application of novel partitioning and scheduling techniques onto the top-level graph. Depending on the proposed partitioning strategy, highlypipelined architectures with either serial or parallel loading of data can be derived. Multidimensional circular convolution, Dependence graph. Partitioning techniques. Mapping algorithms onto hardware