Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1998-08-26
2001-02-27
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S013000, C712S014000, C712S018000, C712S015000, C711S128000, C711S168000
Reexamination Certificate
active
06195738
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to associative processors, and, more particularly, to a combined architecture featuring an associative processor and a random access memory. By combining these two elements the performance of the associative processor associative processor is greatly enhanced and the cost is reduced making the product cost effective for consumer applications, such as digital still cameras, digital camcorders, multi-function peripherals, 2-D and 3-D graphics accelerators, video effects.
In associative processors, each associative word typically contains a data element and all elements are processed in parallel. In applications that require a large number of parameters, such as geometric transformations, the large number of parameters for calculating the transform for each pixel has required very large associative memory words (or several memory words) to process each element. For example, polygon transformation and rendering in 3-D graphics dealing with polygons having three vertices, requires ten parameters per vertex (x,y,z vertex coordinates (30 bits); Nx,Ny,Nz coordinates of the vertex's normal vector (30 bits); R,G,B 24-bit vertex color (24 bits); and an object ID(20 bits)) and three vertices are required for each polygon. This requires a total of 300 bits to store the initial parameters alone. When calculating the transformation, additional temporary storage are required as well for a total of over 1000 bits per polygon. The relatively large die size of associative memory cells makes this solution expensive.
Alternatively, the parameters and temporary results can be stored outside the associative array. This solution too, is less than satisfactory because input and output are done serially for each word and thus consume a large amount of time. It would be highly advantageous to have an architecture capable of storing large amounts of data required for processing in standard, non-associative memory cells while providing parallel access and communication between these cells and the associative array.
By contrast, if the polygon transformation is executed on an architecture in which temporary results and parameters are stored in standard memory cells in parallel communication with the associative memory cells, high performance is maintained using only few associative memory cells to perform the actual calculations.
Furthermore, an entire image can be stored in a very small random access memory (such as DRAM) die size. By providing massively parallel communication between the associative processor array and the random access memory, via the tags unit, a super-high bandwidth is achieved between the associative processor array and the image memory that eliminates the I/O bottleneck that restricts the performance of other processors. For example, an associative array of 8,192 associative memory words using a tags unit which is in parallel communication with all associative words (the tags unit will therefore typically store 8,192 bits) would provide a communication bus of 8,192 bits. At a clock rate of 100 MHz, this provides bandwidth of 100 giga-byte per second. There is thus a widely recognized need for, and it would be highly advantageous to have, an associative memory processor architecture that is in parallel communication with standard random access memory.
SUMMARY OF THE INVENTION
According to the present invention there is provided an associative processor array, that includes a plurality of associative memory words, in parallel communication with a standard memory, such as but not limited to, random access memory.
The present invention teaches a signal processing apparatus featuring: an associative memory array that includes a plurality of associative memory words operative to perform parallel associative compare and parallel associative write operations;
a random access memory; and,
a tags unit in communication with a plurality of the associative memory words and in communication with the random access memory.
The tags unit can be realized in many forms, such as, but not limited to, a simple register, an array of registers, a logic cell array, shift registers, full adders, half-adders. The tags unit is operative as a source for parallel write operations and as a destination for parallel compare operations. A parallel write operation is an associative write operation whereby at least one bit position is selected by a bit-selector unit (typically featuring a mask register, see
FIG. 1
) and a plurality of associative memory words are selected by the tags unit and all bits thus selected are written to in parallel. In this capacity, the tags unit serves as a source as it selects words that will be written to. The data that is written in parallel is typically contained in a pattern register (see FIG.
1
), but could also be part of the write instruction or defined as a value of ‘1.’
A parallel compare operation selects at least one bit position using a mask register and selects words in which the selected bit position will be compared. This instruction can also select all words and thereby compare the selected bit position in all words. The pattern searched for can be stored in the pattern register, be part of the instruction or be a set value of ‘1.’ All successful matches issue a responder to the tags unit. Thus, in this compare operation, the tags unit serves as a destination for the results of the compare operation.
The tags unit is further operative to read and write thousands of data elements to and from the random access memory. The tags unit can write its entire contents to the random access memory in a single cycle. The tags unit can also read data from the random access memory in a single machine cycle. In this way, the tags unit serves as a conduit for information flowing between the associative memory array and the random access memory.
According to further features in preferred embodiments of the invention described below, the signal processing apparatus includes a plurality of tags units. These units are operative to enable performing an associative compare or write operation using at least one of the tags units while another of the tags units is used to perform a read or write operation with the random access memory.
According to still further features in preferred embodiments of the invention described below, the random access memory is an embedded DRAM.
According to further features in preferred embodiments of the invention described below, the tags units are also operative to perform parallel communication between non-adjacent associative memory words in a single machine cycle.
According to further features in preferred embodiments of the invention described below, the non-adjacent associative memory words are processing non-adjacent samples in an image.
According to further features in preferred embodiments of the invention described below, the signal processing apparatus is contained on a single silicon die.
The present invention successfully addresses the shortcomings of the presently known configurations by providing a low-cost associative parallel architecture capable of executing highly complex functions requiring a large number of parameters and temporary storage space using associative processing methods without the requisite cost of large associative memories for storing these parameters and results, and providing fast parallel communication between thousands of associative memory words and random access memory.
REFERENCES:
patent: 4376974 (1983-03-01), Stewart et al.
patent: 5343559 (1994-08-01), Lee
Associative Computing Ltd.
Friedman Mark M.
Pan Daniel H.
LandOfFree
Combined associative processor and random access memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combined associative processor and random access memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined associative processor and random access memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2567195