Optimal parallel and pipelined processing through a new class of matrices with application to generalized spectral analysis

摘要

A new class of general-base matrices, named sampling matrices, which are meant to bridge the gap between algorithmic description and computer architecture is proposed. "Poles," "zeros," "pointers," and "spans" are among the terms introduced to characterize properties of this class of matrices. A formalism for the decomposition of a general matrix in terms of general-base sampling matrices is proposed. "Span" matrices are introduced to measure the dependence of a matrix span on algorithm parameters and, among others, the interaction between this class of matrices and the general-base perfect shuffle permutation matrix previously introduced. A classification of general-base parallel "recirculant" and parallel pipelined processors based on memory topology, access uniformity and shuffle complexity is proposed. The matrix formalism is then used to guide the search for algorithm factorizations leading to optimal parallel and pipelined processor architecture.