Generalised transform factorisation for massive parallelism

A formalism and an algorithm for configuring and sequencing parallel to massively parallel processors for the application of generalised spectral analysis transforms are presented. Successive partial rotations of a base-p hypercube, where p is an arbitrary integer, are shown to produce dynamic contention-free memory allocation, in a generalised parallelism processor architecture. The approach is illustrated by factorisations involving the processing of matrices of transforms which are functions of four variables. Parallel operations are implemented as matrix multiplications. Each matrix, of dimension N × N, where N = pⁿ, n integer, has a structure that depends on a variable parameter k. The level of parallelism, in the form of M = p^m processors, can be chosen arbitrarily by varying m between zero and its maximum value of n - 1. The result is an equation describing the generalised parallelism factorisation as a function of the four variables n, p, k and m. Applications of the approach are shown in relation to complex matrix structures of image processing generalised spectral analysis transforms. The same approach can be applied to a much larger class of parallel and multiprocessing systems for digital signal processing applications.