Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1998-08-05
2002-06-04
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C015S003100
Reexamination Certificate
active
06401189
ABSTRACT:
FIELD OF THE INVENTION
A formalism and an algorithm for the general base parallel dispatch and sequencing state assignment of optimal general-base massively parallel multiprocessing architecture are presented. Transformations of a base-p hypercube, where p is an arbitrary integer, are shown to effect a dynamic contention-free general base optimal memory allocation of the parallel to massively parallel multiprocessing architecture. The formalism is shown to provide a single unique description of the architecture and sequencing of parallel operations. The approach is illustrated by factorizations involving the processing of matrices, which are function of four variables. Parallel operations are implemented matrix multiplications. Each matrix, of dimension N×N, where N=p
n
, n integer, is a sampling matrix of which the structure depends on a variable parameter k. The degree of parallelism, in the form of M=p
m
processors can be chosen arbitrarily by varying m between zero to its maximum value of n−1. The result is an equation describing the solution as a function of the four variables n, p, k and m.
Applications of the approach are shown in relation with complex matrix structures of image processing and generalized spectral analysis transforms but cover a much larger class of parallel processing and multiprocessing systems.
BACKGROUND OF THE INVENTION
Most computer arithmetic operations encountered in information processing algorithms in general and signal processing and sorting algorithms in particular call for iterative multiplications of large matrices. An approach and a formalism for designing optimal parallel/pipelined algorithms and processor architectures for effecting such operations has been recently proposed in Optimal Parallel and Pipelined Processing Through a New Class of Matrices with Application to Generalized Spectral Analysis”, Michael J. Corinthios, IEEE Trans. Comput., Vol. 43, April 1994, pp. 443-459. The algorithms are optimal in their minimization of addressing requirements, of shuffle operations and of the number of memory partitions they call for. The algorithms and corresponding architectures involve general base matrix factorizations. As an application, the factorizations and corresponding optimal architectures are developed in Optimal Parallel and Pipelined Processing Through a New Class of Matrices with Application to Generalized Spectral Analysis”, Michael J. Corinthios, IEEE Trans. Comput., Vol. 43, April 1994, pp. 443-459, to obtain optimal parallel-pipelined processors for the Generalized Walsh-Chrestenson transform, of which the Discrete (fast) Fourier transform is but a special case.
SUMMARY OF THE INVENTION
This invention describes a technique for designing optimal multiprocessing parallel architectures which employ multiples of general-base processors operating in parallel in an optimal global architecture. A formalism and closed forms are developed defining the state and sequencing assignments in a programmable hierarchical level of parallelism at each step of the algorithm execution.
A class of hierarchically parallel multiprocessing architectures employing general-base universal processing elements previously introduced as basic tools for multiprocessing as in 3-D cellular arrays for parallel/cascade image/signal processing”, Michael J. Corinthios, in Spectral Techniques and Fault Detection, M. Karpovsky, Ed. New York: Academic Press, 1985, “The Design of a class of Fast Fourier Transform Computers”, Michael J. Corinthios IEEE Trans. Comput., Vol. C-20, pp. 617-623, June 1971 is presented. Applications of the perfect shuffle matrices and hypercube representations to other classes of problems such as sorting and interconnection networks have received attention over the course of many years in 3-D cellular arrays for parallel/cascade image/signal processing”, Michael J. Corinthios in Spectral Techniques and Fault Detection, M. Karpovsky, Ed. New York: Academic Press, 1985, “The Design of a class of fast Fourier Transform Computers”, Michael J. Corinthios IEEE Trans. Comput., Vol. C-20, pp. 617-623, June 1971, “A Parallel Algorithm for State Assignment of Finite State Machines”, G. Hasteer and P. Banerjee, IEEE Trans. Comput., vol. 47, No. 2, pp. 242-246, February 1998, “Hypercube Algorithms and Implementations”, O. A. Mc Bryan and E. F. Van De Velde, SIAM J. Sci. Stat. Comput., Vol. 8, No. 2, pp. s227-287, Mar. 1987, “Parallel Processing with the Perfect”, H. S. Stone, IEEE Trans. Comput. Vol. C-20, No. 2, pp. 153-161, February 1971, “Design of a Massively Parallel Processor”, K. E. Batcher, IEEE Trans. Comput, pp 836-840, September 1980. Advances in state assignment and memory allocation for array processors, using processing elements as multiprocessing cells, and their interconnection networks have been made in the last two decades by Parallel Processing with the Perfect”, H. S. Stone, IEEE Trans. Comput. Vol. C-20, No. 2, pp. 153-161, February 1971, “Hierarchical Fat Hypercube Architecture for Parallel Processing Systems”, Galles, Michael B., U.S. Pat. No. 5,669,008, September 1997. Many of these contributions applied parallel and multiprocessing architectures to signal processing applications and in particular spectral analysis algorithms. In more recent years applications of parallel and multiprocessing techniques have focused on generalized spectral analysis, Discrete Cosine, Haar, Walsh and Chrestenson Transforms, among others in Optimal Parallel and Pipelined Processing Through a New Class of Matrices with Application to Generalized Spectral Analysis”, Michael J. Corinthios, IEEE Trans. Comput., Vol. 43, April 1994, pp. 443-459.”, “3-D cellular arrays for parallel/cascade image/signal processing”, Michael J. Corinthios in Spectral Techniques and Fault Detection, M. Karpovsky, Ed. New York: Academic Press, 1985, “Parallel Processing with the Perfect”, H. S. Stone, IEEE Trans. Comput. Vol. C-20, No. 2, pp. 153-161, February 1971, “Access and Alignment of Data in an Array Processor”, D. H. Lawrie, IEEE Trans. Comput., vol C-24, No. 2, December 1975, pp 1145-1155, “Fast Fourier Transforms over Finite Groups by Multiprocessor Systems”, Roziner, T. D., Karpovsky, M. G., and Trachtenberg, L. A., IEEE Trans. Accous., Speech, and Sign. Proc., ASSP, vol. 38, No. 2, February 1990, pp 226-240, “An Architecture for a Video Rate Two-Dimensional Fast Fourier Transform processor”, Taylor, G. F., Steinvorth, R. H., and MacDonald J., IEEE Trans. Comput., vol. 37, No. 9, September 1988, pp 1145-1151. “Fault tolerant FFT Networks”, IEEE Trans. Comput., vol. 37, No. 5, May 1988, pp. 548-561, Jou, Y.-Y. and Abraham, J. A., “Design of Multiple-Valued Systolic System for the Computation of the Chrestenson Spectrum”, Moraga, Claudio, IEEE Trans. Comput., Vol. C-35, No. 2, February 1986, pp 183-188. “Matrix Representation for Sorting and the Fast Fourier Transform”, Sloate, H., IEEE Trans. Circ. And Syst., Vol. CAS-21, No. 1, January 1974, pp 109-116, “Processor for Signal processing and Hierarchical Multiprocessing Structure Including At Least One Such Processor”, Luc Mary and Barazesh, Bahman, U.S. Pat. No. 4,845,660, July 1989. In 3-D cellular arrays for parallel/cascade image/signal processing”, Michael J. Corinthios, in Spectral Techniques and Fault Detection, M. Karpovsky, Ed. New York: Academic Press, 1985, three-dimensional parallel and pipelined architectures of cellular array multiprocessors employ Configurable Universal Processing Elements (CUPE) forming what were referred to as ‘Isostolic Arrays’, applied to signals as well as images in Optimal Parallel and Pipelined Processing Through a New Class of Matrices with Application to Generalized Spectral Analysis”, Michael J. Corinthios, IEEE Trans. Comput., Vol. 43, April 1994, pp. 443-459.”, “3-D cellular arrays for parallel/cascade image/signal processing”, Michael J. Corinthios, in Spectral Techniques and Fault Detection, M. Karpovsky, Ed. New York: Academic Press, 1985.
Many patents of invention deal with the subject of hypercube transformations such as described in U.S.
Donaghue Larry D.
Jacobson & Holman PLLC
LandOfFree
General base state assignment for optimal massive parallelism does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with General base state assignment for optimal massive parallelism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General base state assignment for optimal massive parallelism will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2961045