Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-06-26
2003-09-30
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S152000
Reexamination Certificate
active
06629195
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to memory devices. More specifically, the present invention relates to content addressable memory (CAM) devices and implementing semaphores therein.
2. Discussion of the Related Art
In networking applications, fast searches of a database, table, or list, such as in an Ethernet address lookup operation, allow for improved performance. These databases, tables, or lists are often stored in memory devices, such as random access memory (RAM). Memory devices typically store and retrieve data by addressing specific memory locations. However, due to this approach, the speed of memory access is often compromised. A more efficient approach is to locate a piece of stored data by identifying it with the content of the data itself, rather than by its address.
Content addressable memory (CAM), which is an outgrowth of RAM technology, provides a performance advantage over conventional memory devices in that it is able to compare the desired information against the entire list of pre-stored entries simultaneously, resulting in an order-of-magnitude reduction in search time. A CAM semiconductor device permits the contents of the memory to be searched and matched instead of having to specify one or more particular memory location(s) in order to retrieve data from the memory. A CAM device may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice processing and recognition, artificial intelligence, pattern recognition, robotics control, computer and communications networks (e.g., high-speed routers and switches), and arithmetic operations. A CAM device provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously. For example, a binary search through a database of 1,000 entries may take ten separate search steps, whereas a CAM device with 1,000 entries may be searched in a single operation resulting in a search that takes ten times less time. One to example of an application in which CAM devices are often used for a high-speed switching system that needs to rapidly search a routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.
A CAM device is organized differently from typical static RAM (SRAM) or dynamic RAM (DRAM) devices. In particular, data in a CAM device is stored in memory locations in somewhat a random fashion. The memory locations may be selected by an address bus, or the data may be written directly into the first empty memory location. Every location has, for example, a pair of special status bits that keep track of whether the location has valid information in it or is empty, and therefore available for overwriting. As opposed to RAM devices in which information is accessed by specifying a particular memory location, once information is stored in a memory location of the CAM, it may be located by comparing every bit in the memory with data placed in a special register known as a compare register. If there is a match of every bit in a particular memory location with every corresponding bit in the register, a “match flag” is asserted to let the user know that the data in the register was found in the CAM device. A priority encoder may sort out which matching memory location has the top priority if there are more than one matching entry, and makes the address of the matching memory location available to the user so that the user may access the matching data. Thus, with a CAM device, the user supplies a piece of data he/she wants to match to the CAM device and gets back the address of any matching pieces of data in the CAM device.
CAMs are also known as associative memories, which operate more intuitively than RAM devices, and somewhat similarly to human memory. An associative memory is generally one that allows its stored information to be retrieved based on a partial knowledge of that information. Accordingly, CAMs are well-suited for various network-related applications, including Ethernet address lookup, high-bandwidth address filtering, and fast lookup of data for high-performance data switches, firewalls, bridges, and routers. In many network-related applications, such as in a network processor application-specific integrated circuit (ASIC), there may be multiple processor units or devices, all of which may access and modify the same data set or record stored in a shared memory. However, it must be assured that only one processor is working on a specific record at a time, or else the data set or record may become corrupted. Therefore, in order to properly employ CAM devices in network-related applications utilizing multiple processors, for example, it is preferable to utilize a mechanism to control access to a particular data set stored in a memory shared by multiple processors.
REFERENCES:
patent: 6148300 (2000-11-01), Singhal et al.
Berny Goodheart and James Cox, The Magic Garden Explained, Copyright 1994, Prentice Hall, Release 4, Chapter 8: pp. 540-541.*
Alteral Corporation, Technical Brief 56, “Using APEX 20KE CAM for Fast Search Applications”, Aug. 1999, ver.1, p. 2.
Andreas Magnussen
Andreassen Jens K.
Kock Steen V.
Schroeder Jacob J.
Bragdon Reginald G.
Inoa Midys
Pillsbury & Winthrop LLP
LandOfFree
Implementing semaphores in a content addressable 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 Implementing semaphores in a content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementing semaphores in a content addressable memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3033563