Hierarchical encoder including timing and data detection...

Details Hierarchical encoder including timing and data detection... Hierarchical encoder including timing and data detection...

1999-10-27

2001-06-19

Tran, Andrew Q. (Department: 2824)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S230030, C365S189050, C365S189120

Reexamination Certificate

active

06249449

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a mass storage associative memory, which is divided into a plurality of associative memory subblocks, and an encoder, which is applied to this associative memory, for encoding addresses corresponding to hit flags as a result of match retrieval between retrieval data and the contents of each memory word or otherwise addresses corresponding to empty flags indicative of whether or not the contents of each memory word are valid as objects for match retrieval so that the addresses may efficiently be encoded in the predetermined priority order.
Heretofore, associative memories, that is, fully parallel CAMs (Content Addressable Memories), have been widely known as semiconductor storage devices having the functions of performing the match detection of retrieval data and stored data concurrently in terms of all bits and outputting the match address of stored data or stored data (see “Design of CMOS VLSI,” pp 176-177, edited by Tetsuya Iizuka and supervised by Takuo Sugano, Baifukan, 1989).
Content-addressed retrieval, instead of retrieval by means of physical memory addresses, is common to content addressable memories (CAMs). Therefore, the basic function of CAM, unlike an ordinary memory, is to input retrieval data for example so as to output a word address at which data matching the retrieval data has been stored. However, only one word is not necessarily matching and there may be a plurality of them. When the plurality of match words are obtained like this, a correct encode output is unavailable with an ordinary encoder. Consequently, CAM is equipped with a priority encoder for encoding and outputting a plurality of match (hit) signals in the order of predetermined priorities.
In a bulk CAM, however, the number of words is generally very large in contrast to the word length. For this reason, a cell array is divided into a plurality of blocks and it is an important problem how priority encoders are arranged. In other words, the priority encoders will occupy a large area and power consumption will also be on the increase if the priority encoder is provided for every block of CAM. As the number of blocks increases because of the division of the array, the area thus occupied thereby and the power consumption proportionally increase further.
As a result, there has been proposed a content addressable memory in which one main priority encoder is provided for the plurality of blocks and a block priority encoder to be separately provided is used for the block in which encoding is carried out by the main priority encoder.
FIG. 30
shows such a content addressable memory (CAM). As shown in
FIG. 30
, the content addressable memory
200
is divided into four CAM blocks
202
and each CAM block
202
is further divided into eight CAM subblocks
204
. A priority encoder
210
is structurally hierarchical in that there are installed four main priority encoders
212
, each being intended for the CAM block
202
having eight of the CAM subblocks
204
, and one subblock priority encoder
214
is provided every four CAM blocks
202
. As shown in
FIG. 31
, further, the CAM subblock
204
comprises a CAM subarray
206
having a predetermined number of CAM words with predetermined word length and its control unit including a hit signal register
208
for holding a hit signal resulting from the hitting of retrieval data against a CAM word.
At the time of match retrieval in the CAM block
202
, the hit signals of all words in each subblock
204
are held by the hit signal register
208
and a subblock hit signal indicating the presence of a match word in the subblock
204
is simultaneously generated by an OR circuit (not shown) of the control unit in each CAM subblock
204
. On receiving the signal, the subblock priority encoder
214
subsequently generates a subblock selection signal indicating the highest priority CAM subblock
204
and the subblock priority encoder
214
also generates an encoded subblock address.
On receiving the block selection signal, a switch circuit (not shown) of the subblock thus selected is then activated to transfer the data (hit signal) held in the hit signal register
208
to the main priority encoder
212
as an output signal. Thereafter, the main priority encoder
212
generates a hit memory word address resulting from the hit signal thus transferred and encoded in the order of predetermined priorities in the CAM subblock
204
. The priority encoder
210
combines the hit memory word address and the aforementioned subblock address and outputs the encoding logical address of the hit memory word of the CAM
200
.
In the conventional CAM
200
shown in
FIGS. 30 and 31
, the priority encoder (encoder)
210
comprises the main priority encoder (priority encoder)
212
for controlling the plurality of CAM subblocks
204
and the subblock priority encoder
214
for assigning priority to the CAM subblocks
204
for performing the encoding operation. The order of priorities is first determined among the plurality of the subblocks
204
and before being encoded, the output signal of the first priority subblock
204
is applied to the main priority encoder
212
. The encoder can thus be made relatively small in configuration, whereas the circuit area relative to the whole circuit scale of the CAM
200
is reduced, whereby large scale integration is made feasible.
Notwithstanding, subblock-to-subblock switch time becomes necessary until the encoding of the output signal (hit signal data (hereinafter called “flag data”)) from the second priority CAM subblock
204
is started after the output signal (flag data) from the first priority subblock
204
is encoded by the main priority encoder
212
and output. In other words, it takes time to transfer the flag data from the hit signal register
208
of the second priority subblock
204
after an encoded address is output from the main priority encoder
212
and there still exists a problem arising from low encoding efficiency.
In an apparatus using an associative memory, on the other hand, the operation of updating the contents of a memory word is frequently performed by, for example, holding the contents of a plurality of memory words matching with retrieval data as a result of match retrieval and sequentially writing new data to the memory words that have been erased after the content of a memory word mismatching with retrieval data are erased in order to improve the use efficiency of each memory word of the associative memory.
In an apparatus such as a switching hub in which a plurality of computers are connected so as to build up an integrated network environment, for example, an associative memory is used to obtain additional data such as a port number corresponding to a MAC address existing in the header portion of packet data, based on which the packet data transferred from the source computer is output from a port corresponding to the port number obtained, whereby the additional data is properly transferred to a destination computer.
When a port for use in connecting a certain computer is changed from a port
1
to a port
3
in that case, unless the port number which is stored in the additional data of the memory word in which the data of a MAC address corresponding to this computer is stored, is updated from the port
1
to the port
3
, packet data to be transferred to this computer is output from the port
1
to which this computer has been connected previously instead of the port
3
to which this computer is actually connected now. In order to prevent this trouble, the port number to which each computer has been connected should be updated thereon at all times.
Moreover, the number of memory words in an associative memory is generally smaller than the total number of computers on a network and only information of specific computers is selectively stored in each of the memory words. In order to improve the use efficiency of an associative memory, for example, time stamp information for managing an operating duration is stored in the additional data and the time sta

Affiliated with

Also associated with

Rating

Hierarchical encoder including timing and data detection... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hierarchical encoder including timing and data detection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical encoder including timing and data detection... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2450957