Digital processor for simulating operation of a parallel process

Details Digital processor for simulating operation of a parallel process Digital processor for simulating operation of a parallel process

1993-02-12

1998-12-01

Treat, William M.

395800, G06F 1582, G06F 1300

Patent

active

058451234

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

1. Field of the Invention
This Invention relates to a digital processor for simulating operation of a parallel processing array, such as a systolic array.
2. Discussion of Prior Art
The field of parallel processing arrays was developed to overcome a well-known problem in conventional digital computers, the "Von Neumann bottleneck". This problem arises from the serial nature of conventional computers, in which program steps or Instructions are executed one at .a time and in succession. This means that the computer operating speed is restricted to the rate at which its central processing unit executes individual instructions.
To overcome the operating speed problem of conventional computers, parallel processors based on systolic array architectures have been developed One such is disclosed in British Patent No. OB 2, 151, 378B, which corresponds to U.S. Pat. No. 4,727,503. IL consists of a triangular array of internal and boundary cells. The boundary cells form the array diagonal and are interconnected via delay latches. The internal cells art in above-diagonal locations. The array includes nearest-neighbor cell interconnection lines defining rows and columns of cells. The cells are activated cyclically by a common system clock. Signal flow is along the rows and down the columns at the rate of one cell per clock cycle. Each cell executes a computational function on each clock cycle employing data input to the array and/or received from neighboring cells. Computation results are output to neighboring cells to provide input for subsequent computations. The computations of individual cells are comparatively simple, but the systolic array as a whole performs a much more complex calculation, and does so In a recursive manner at potentially high speed. In effect, the array subdivides the complex calculations into a series of much smaller cascaded calculations which are distributed over the array processing cells. An external control computer Is not required. The cells are clock-activated, each operates on every clock cycle. The maximum clock frequency or rate of processing is limited only by the rate at which the slowest individual cell can carry out its comparatively simple processing function. This results in a high degree of parallelism, with potentially high speed if fast processing cells are employed. The "bottleneck" of conventional computers is avoided.
The disadvantage of prior art systolic arrays is that, in all but the simplest problems, large numbers of cells are required. As will be described later in more detail, a prior art triangular array for dealing with an n-dimensional computation requires in the order of n.sup.2 /2 internal cells. In consequence, the number of internal cells required grows as the square of the number of dimensions of the computation. The number of boundary cells grows only linearly with number of dimensions. One important application of a triangular systolic array relates to processing signals from an array of sensors, such as a phased array of radar antennas. Typical radar phased arrays incorporate in the region of one thousand or more antennas, and a systolic array to process the antenna signals would require of the order of one million processing cells. Each cell requires the processing functions and connectivity capabilities of a transputer to enable communications between neighboring cells. Special purpose integrated circuits could also be used, in which "cells" constitute respective areas of a silicon chip or wafer. Since transputers are priced in excess of approximately $150 each, the cost of a systolic array would be prohibitively expensive for radar phased array purposes. It is also prohibitively expensive for many other signal processing applications characterized by high dimensionality.
There is a need for digital processing apparatus which has a degree of parallelism to overcome conventional computer disadvantages, but which requires fewer processing cells than a prior art systolic array.
It is known from EP-A-0 021 404 to employ an arra

REFERENCES:
patent: 4247892 (1981-01-01), Lawrence
patent: 4773038 (1988-09-01), Hillis et al.
patent: 4827403 (1989-05-01), Steele, Jr. et al.
patent: 4922418 (1990-05-01), Dolechek
patent: 4943909 (1990-07-01), Huang
patent: 5018065 (1991-05-01), McWhirter et al.
patent: 5136717 (1992-08-01), Morley et al.
patent: 5179714 (1993-01-01), Graybill
patent: 5193202 (1993-03-01), Jackson et al.
patent: 5249274 (1993-09-01), Sztipanovits et al.
patent: 5249301 (1993-09-01), Keryvel et al.
patent: 5377306 (1994-12-01), Broomhead et al.
Parallel Algorithms & Architectures: Roceedings of the International Workshop on Parallel et al, 14 Apr. 1986, Luminy, France pp. 349-358. Milcom 88, vol. 1, 23 Oct. 1988, San Diego, USA, pp. 205 209.
Systolic Processor Array for Radar and Communications; Lackey et al, see p. 207, right col. line 1--p. 208, right col. line 14, figure 4. International Conference on Systolic Arrays, 25 May 1988, San Diego, USA pp. 125-134.
Tnimoto et al., An Image Based on an Array of Pipelines, 1981 IEEE Workshop on Computer Arch.; Nov. 11, 1981; pp. 201-208.

Affiliated with

Also associated with

Rating

Digital processor for simulating operation of a parallel process does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Digital processor for simulating operation of a parallel process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital processor for simulating operation of a parallel process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2402474