Algorithms for high-performance recurrent affine data and signal processing and a method of improving its input-output locality

The paper proposes a new method for customizing patterns of input-output access to data in order to improve its locality in implementations of high-performance signal and data processing based on recurrent affine transformation. This method is implemented in a proposed parallel algorithm with improved data locality which, together with alternative methods of parallelization, is formally described and presented in the paper. The formalism is expressed in terms of abstract algebraic structures and as such the method is applicable to a wide range of data and signal processing problems which are based on the recurrent affine transform. The applicability of the proposed algorithm is derived from its "single program-multiple data" class of parallel problems and implementing architectures. The latter are widespread due to relative simplicity of their implementation compared to other classes which require separate management of parallel threads of execution. These architectures include, for example, vector, signal and graphical multiprocessors. Use of the proposed method and algorithm, as an example, is specified in the paper for the problems of parallel generation of pseudorandom numbers, parallel implementation of linear and affine feedback registers as well as a parallel implementation of affine block and stream ciphers based on the recurrent affine transform which are employed in modern algorithms of confidential image encryption.