Incremental search content addressable memory for increased data compression efficiency

• US 5,369,605 A
• Filed: 07/07/1993
• Issued: 11/29/1994
• Est. Priority Date: 07/07/1993
• Status: Expired due to Term

• Current Assignee: Dell USA LP (Dell Technologies Inc.)
• Original Assignee: Dell USA LP (Dell Technologies Inc.)
• Inventors: Parks, Terry J.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/088,966
• Time in Patent Office: 510 Days
• Field of Search: 364/715.09, 364/715.11, 340/146.2
• US Class Current: 708/210
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

A content addressable memory (CAM) which is capable of performing string search functions in hardware. The implementation of string search in hardware eliminates the requirement of software to perform this function and thus significantly increases data compression performance. Each byte or memory storage unit of the CAM includes a comparator and a single bit flip-flop. The comparator asserts a match signal to the flip-flop if the contents of a memory storage unit match external data and a prior memory storage unit match signal is asserted. Two types of comparison operations are provided by each memory storage unit. The first ignores the contents of a previous flip-flop, and this comparison operation is used for the first character of a string search. The second type of comparison operation takes into account the value latched in the preceding byte of the CAM. For example, the comparison for byte N only matches if the previous comparison for byte N-1 matched. Thus long sequences of bytes can be searched for with a byte wide CAM. Therefore, string searches can be performed in hardware, thus increasing data compression performance.

Claims

1. A memory system which performs string searches in hardware, comprising:

a plurality of memory storage units 1 to N, wherein each of said plurality of memory storage units is capable of storing associated data and is capable of comparing said associated data with external data and generating one or more compare signals indicative thereof;

wherein at least one memory storage unit included within a subset of said memory storage units comprises;

a comparator which receives said one or more compare signals associated therewith and a match signal from a prior memory storage unit which indicates whether a match occurred in said prior memory storage unit, wherein said comparator asserts a respective match signal if said one or more compare signals associated therewith indicate that said associated data of said at least one memory storage unit matches said external data and said prior memory storage unit match signal is asserted;

wherein said comparator provides said respective match signal to a subsequent memory storage unit.

2. The memory system of claim 1, wherein said at least one memory storage unit of said subset of said memory storage units further comprises:

a storage element which receives and stores said respective match signal from said comparator and provides said respective match signal to said subsequent memory storage unit.

3. The memory system of claim 1, wherein said subset includes several memory storage units, wherein said several memory storage units comprised in said subset each further includes an input receiving a first signal indicating a first type of comparison;

wherein each of said comparators comprised in said subset of said memory storage units does not consider said prior memory storage unit match signal in asserting said respective match signal if said first signal is asserted; and

wherein each of said comparators comprised in said subset of said memory storage units considers said prior memory storage unit match signal if said first signal is not asserted and does not assert said respective match signal if said first signal is not asserted and said prior memory storage unit match signal is not asserted.

4. The memory system of claim 3, wherein said several memory storage units comprised in said subset each includes logic which receives said prior memory storage unit match signal and said first signal and provides an output match signal to said comparator, wherein said output match signal is asserted if either said prior memory storage unit match signal or said first signal is asserted.

5. The memory system of claim 3, wherein said first type of comparison comprises comparing the first character of a character string being searched.

6. The memory system of claim 1, further comprising:

an encoder which receives said respective match signals from each of said at least one memory storage unit comprised in said subset;

wherein said encoder outputs an encoded value representing which of said respective match signals are asserted.

7. The memory system of claim 6,

wherein said encoder comprises a priority encoder which outputs an encoded value representing one of said respective match signals which is asserted.

8. The memory system of claim 1, wherein said subset comprises memory storage units 2 to N of said memory system.

9. The memory system of claim 1, wherein said memory storage units are comprised of content addressable memory.

10. The memory system of claim 1, wherein said comparator comprises an AND gate.

11. A memory system which can perform string searches in hardware, comprising:

a plurality of memory storage units 1 to N for storing data, wherein each said memory storage unit is capable of storing associated data and is capable of comparing said associated data with external data and generating one or more compare signals indicative thereof;

wherein said memory storage unit 1 includes a comparator which receives said one or more compare signals associated therewith and asserts a respective match signal if said one or more compare signals associated therewith indicate that said associated data of said memory storage unit matches said external data; and

wherein said memory storage units 2 to N each includes a comparator which receives said one or more compare signals associated therewith and a match signal from a prior memory storage unit which indicates whether a match occurred in said prior memory storage unit, wherein said comparator asserts a respective match signal if said one or more compare signals associated therewith indicate that said associated data of said memory storage unit 2 to N matches said external data and said prior memory storage unit match signal is asserted.

12. The memory system of claim 11, wherein each of said memory storage units 1 to n further comprises:

a storage element which receives and stores said respective match signal from said comparator and provides said respective match signal as an output;

wherein said storage element comprised in memory storage units 1 to N-1 each output said respective match signal to a subsequent memory storage unit.

13. The memory system of claim 11, wherein said memory storage units 2 to N each further include an input receiving a first signal indicating a first type of comparison;

wherein each of said comparators in said memory storage units 2 to N does not consider said prior memory storage unit match signal in asserting said respective match signal if said first signal is asserted; and

wherein each of said comparators in said memory storage units 2 to N considers said prior memory storage unit match signal if said first signal is not asserted and does not assert said respective match signal if said first signal is not asserted and said prior memory storage unit match signal is not asserted.

14. The memory system of claim 13, wherein said memory storage units 2 to N each includes logic which receives said prior memory storage unit match signal and said first signal and provides an output match signal to said comparator, wherein said output match signal is asserted if either said prior memory storage unit match signal or said first signal is asserted.

15. The memory system of claim 13, wherein said first type of comparison comprises comparing the first character of a character string being searched.

16. The memory system of claim 11, further comprising:

an encoder which receives said respective match signals from each of said memory storage units 1 to N;

wherein said encoder outputs an encoded value representing which of said respective match signals are asserted.

17. The memory system of claim 16, wherein said encoder comprises a priority encoder which outputs an encoded value representing one of said respective match signals which is asserted.

18. The memory system of claim 11, wherein each of said memory storage units are comprised of content addressable memory.

19. The memory system of claim 11, wherein said comparator comprises an AND gate.

20. A method for performing a string search in a system comprising a buffer for storing a character string to be searched and a memory storeage system which performs string searches in hardware, wherein the memory storage system comprises a plurality of memory storage units 1 to n for storing data, wherein each said memory storage unit 1 to N is capable of comparing associated contents with external data and generating one or more compare signals indicative thereof, and wherein each said memory storage units 2 to N each includes a comparator which receives said one or more compare signals in addition to a match signal from a prior memory storage unit which indicates whether a match occurred in said prior memory storage unit, wherein said comparator asserts a respective match signal if said one or more compare signals indicate that said associated contents of said each memory storage unit 2 to N matches said external data and said prior memory storage unit match signal is asserted;

the method comprising;

comparing the first character of the character string in the buffer with the contents of each of the memory storage units 1 to N in the memory storage system, wherein said memory storage units 1 to N assert said respective match signals without considering said prior memory storage unit match signals;

comparing a subsequent character of the character string in the buffer with the contents of each of the memory storage units 2 to N in the memory storage system after said step of first character comparing, wherein said subsequent character only matches the contents of a respective memory storage unit if said prior memory storage unit match signal is asserted;

returning to said step of subsequent character comparing if a match occurred in said step of subsequent character comparing;

examining the respective match signals last asserted by each of said memory storage units 1 to N if a match did not occur in said step of subsequent character comparing; and

finding the longest string in the memory storage system which matches the character string int he buffer using said last asserted match signals.

21. The method of claim 20, further comprising:

determining if any matches occurred between the first character of the character string in the buffer and the associated contents of each of the memory storage units 1 to N in the memory storage system;

wherein said step of subsequent character comparing is performed only if a match was determined to have occurred in said step of determining.

22. The method of claim 20, wherein the memory storage system further comprises an encoder which receives said respective match signals from each of said memory storage units 1 to N and outputs a value representing one of said respective match signals that is asserted;

wherein said step of examining comprises examining the value last asserted by said encoder.

23. The method of claim 20, further comprising:

incrementing a variable n after each of said steps of first character comparing and subsequent character comparing;

wherein said step of finding uses said incremented variable n in finding said longest string.

24. A method for performing data compression in a system comprising a look-ahead buffer for storing a character string to be searched and a history buffer which performs string searches in hardware, wherein the history buffer comprises a plurality of memory storage units 1 to N for storing data, wherein each said memory storage unit 1 to N is capable of comparing associated contents with external data and generating one or more compare signals indicative thereof, and wherein each said memory storage units 2 to N includes a comparator which receives said one or more compare signals in addition to a match signal from a prior memory storage unit which indicates whether a match occurred in said prior memory storage unit, wherein said comparator asserts a respective match signal if said one or more compare signals indicate that said associated contents of said each memory storage unit 2 to N matches said external data and said prior memory storage unit match signal is asserted;

the method comprising;

comparing the first character of the character string in the look-ahead buffer with the contents of each of the memory storage units 1 to N in the history buffer, wherein said memory storage units 1 to N assert said respective match signals without considering said prior memory storage unit match signals;

comparing a subsequent character of the character string in the look-ahead buffer with the contents of each of the memory storage units 2 to N in the history buffer after said step of first character comparing, wherein said subsequent character only matches the contents of a respective memory storage unit if said prior memory storage unit match signal is asserted;

returning to said step of subsequent character comparing if a match occurred in said step of subsequent character comparing;

examining the respective match signals last asserted by each of said memory storage units 1 to N if a match did not occur in said step of subsequent character comparing; and

finding the longest string in the history buffer which matches the character string in the look-ahead buffer using said last asserted match signals.

25. The method of claim 24, further comprising:

determining if any matches occurred between the first character of the character string in the look-ahead buffer and the associated contents of each of the memory storage units 1 to N in the history buffer;

wherein said step of subsequent character comparing is performed only if a match was determined to have occurred in said step of determining.

26. The method of claim 24, wherein the history buffer further comprises an encoder which receives said respective match signals from each of said memory storage units 1 to N and outputs a value representing one of said respective match signals that is asserted;

wherein said step of examining comprises examining the value last asserted by said encoder.

27. The method of claim 24, further comprising:

incrementing a variable n after each of said steps of first character comparing and subsequent character comparing;

wherein said step of finding uses said incremented variable n in finding said longest string.