Patent
1993-05-18
1995-03-14
Harvey, Jack B.
G06F 1200
Patent
active
053983220
DESCRIPTION:
BRIEF SUMMARY
This invention relates to the generation of number theory mappings and their application to the addressing of matrix structures in computer systems. The invention provides particular advantages when used in computer architectures that include systolic processors.
BACKGROUND OF THE INVENTION
Address generation has been a continuing problem for computers, particularly as operation speeds have increased. As the number and range of applications has expanded, there has arisen a need for address generators to produce a range of non-sequential address sequences. A common example is the bit- reversed addressing for the FFT.
Common Digital Signal Processing (DSP) addressing patterns include:
These patterns are in common usage as a result of the vector nature of the common computer architectures. Reference can be made to the paper by ZOBEL, R. N., "Some alternative techniques for hardware address generators for digital signal processors", ISCAS'88, CH2458-8/88 pp. 69-72, 1988, for a description of hardware which implements these addressing patterns. Another paper which describes a versatile hardware address indexing unit is by NWACHUKWU, E. O., "Address generation in an array processor", IEEE Trans. on Computers, Vol. C-34, No. 2, pp. 170-173, February 1985. A further paper which in part describes a general purpose address generation technique is the paper by HALL, F. E. and ROCCO Jr., A. G., "A compact programmable array processor", The Lincoln Laboratory Journal, Volume 2, Number 1, 1989.
In all of these papers the address generation techniques are designed to optimise vector-based algorithms. Matrices and matrix algorithms are supported as operations upon sets of vectors. These approaches have limitations when matrix algorithms are implemented which can not readily be expressed in terms of sets of vectors. An example of such an algorithm is the one-dimensional Fourier transform implemented with the prime factor algorithm.
The object of this invention is the provision of an address generator which is optimised for general matrix algorithms and which is capable of applying `on-the-fly` number theory mappings to matrix operands as they are fetched from memory.
MAPPING GENERATOR ARCHITECTURE
A conventional approach to the problem of addressing matrices stored in a linear memory space is to consider addressing the elements of the matrix in terms of strides. The strides specify the linear distance between successive elements of rows or columns respectively. The problem with this approach is that it is not possible to both fetch matrix operands and simultaneously apply general number theory mappings. The mappings must be applied to the matrices as separate operations. These operations must be done in software in a conventional machine and incur significant time penalties.
Examination of conventional matrix storage schemes shows that they can be considered as simple mappings between one-dimensional and multi-dimensional subspaces. Address generation for the matrices can therefore be performed by carrying out a particular mapping from one dimension to or from two or more dimensions. This can be provided by constructing a hardware implementation of a general number theory mapping. The hardware must provide a general capability to support mappings from one dimension to multi-dimensional subspaces.
The solution to the problem is therefore to replace the conventional address generator with a hardware architecture which implements a general number theory mapping, which unlike prior software for the implementation of particular linear transform algorithms is generally applicable to a range of problems which includes but is not limited to linear transforms.
SUMMARY OF THE INVENTION
In its broadest from the invention is an address generator to generate at its output, output addresses of elements of an N-dimensional matrix comprising matrix structure, wherein, of an n-dimensional matrix and representative of the values of two finite address differences, input said difference descriptors and an initially zero previously ca
REFERENCES:
patent: 4051551 (1977-09-01), Lawrie et al.
patent: 4370732 (1983-01-01), Kogge
patent: 4484265 (1984-11-01), Czekalski
patent: 4563750 (1986-01-01), Clarke
patent: 4809156 (1989-02-01), Taber
patent: 4819152 (1989-04-01), Deerfield et al.
patent: 4959776 (1990-09-01), Deerfield et al.
patent: 5293596 (1994-03-01), Toyokura et al.
E. O. Nwachukwu "Address Generation in an Array Processor," IEEE Transactions on Computers, vol. C-34, No. 2, Feb. 1985, pp. 170-173.
R. N. Zobel, "Some Alternative Techniques for Hardware Address Generators for Digital Signal Processors," ISCAS, 1988, pp. 69-72.
F. E. Hall and A. G. Rocco, Jr., "A Compact Programmable Array Processor," The Lincoln Laboratory Journal, vol. 2, No. 1, 1989, pp. 41-62.
Harvey Jack B.
Luminis Pty. Ltd.
Whitfield Michael A.
LandOfFree
Number theory mapping generator for addressing matrix structures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Number theory mapping generator for addressing matrix structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Number theory mapping generator for addressing matrix structures will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-718492