CAM memory architecture and a method of forming and operating a device according to a CAM memory architecture

A method for a content addressable memory that includes receiving a first data value for evaluation at a first memory block during a first time interval, receiving a second data value for evaluation at a second memory block during a second time interval and evaluating said both the first and second data values during a third time interval. According to one embodiment of the invention the first and second time intervals are separate so that the first and second data blocks receive unique data out of phase with one another from a single address bus. Evaluation of both data values takes place substantially simultaneously in the respective memory blocks. Also included is a device architecture and a device adapted to control data transfer to two CAM memory blocks in response to alternate phase transitions of a control signal.

FIELD OF THE INVENTION

The present invention relates to a memory architecture and device, and more particularly to a content addressable memory architecture and device.

BACKGROUND OF THE INVENTION

A content addressable memory (CAM) is a memory device that permits rapid parallel searching of stored data to find a particular data value. In contrast to most other memory formats (such as ROM and RAM memory), which are based on address-driven storage architectures, the typical CAM memory device offers both address-driven and content-driven data access.

Address-driven memory device architectures are well-known. According to an address-driven architecture, during a memory access, a user supplies an address and stores data, or retrieves data previously stored, at that specific address. For example, in an address-driven architecture, data values may be stored at a particular logical address by specifying the address on an address bus, and supplying data on a data bus to be stored at the specified address. In the same fashion, data may be retrieved on the data bus in response to a memory address supplied on the address bus.

As noted, the typical CAM memory device can be accessed in both address-driven and content-driven fashion. Storage of data in a CAM may be performed in an address-driven mode, as described above. Additionally, some CAM memory devices allow storage of data in a “first available storage location.” For example a logical flag may be provided for each storage location of the CAM device, indicating whether a storage location contains stored data, or is available to receive new data. When a new data item is presented to the CAM device, each logical flag of the logical flag set is tested simultaneously and an unused storage location is identified. The new data item is then stored in the unused storage location, and the logical flag associated with that location is reconfigured to indicate that the location is in use.

As with data storage, data retrieval in a CAM memory may be performed on an address-driven basis. More importantly, however, CAM memory provides content-driven data retrieval. In a content-driven data retrieval, a data pattern is presented to the CAM memory device. If the CAM memory device contains a previously stored data item of the same data pattern, that presence is indicated and the location in the CAM where the searched data is stored is identified and an address connected with the matched data is returned. The CAM memory device is structured to perform the search on a highly parallel basis, conducting the search on all the data in the CAM substantially simultaneously. Consequently, a CAM can provide search results much more rapidly than an address-driven memory device, in which searches are typically performed serially, one address at a time.

The content-driven data retrieval facility of a CAM memory is typically implemented by providing an array of storage cells connected in an extensive wired-or configuration. This architecture allows a multi-bit data word applied to an input of the CAM device to be compared, substantially simultaneously, with the data words stored in every location of the CAM.

FIG. 1shows a simplified schematic representation of a CAM memory device10, as known in the art. The CAM device includes a search register12and a plurality of storage words14. Each storage word14includes multiple CAM memory cells16. The search register12includes a corresponding plurality of search register bits18. The search register12is coupled to each of the storage words14by a parallel bus20, so that each cell16(for example cell22) of a storage word14is coupled to a corresponding bit (for example24) of the search register12. Each storage word is coupled to a corresponding match line26. The match line26exhibits electrical capacitance (represented as lumped capacitance28) and can be pre-charged to a particular electrical potential by a precharge circuit30.

As shown at22each CAM memory cell16of each storage word14includes a circuit34adapted to switchingly couple a particular match line27to ground32. The circuit includes an input36coupled to the data bus20. The input36is coupled to a gate of a transistor38. Transistor38is coupled in series with another transistor40between the particular match line27and ground32. Input36is also coupled, through an inverter42, to a gate of another transistor44. Transistor44is coupled in series with another transistor46between the particular match line27and ground32. A gate of transistor46is coupled to a memory element50. The memory element50controls the gate of transistor46according to a binary value D stored within memory element50. A gate of transistor40is coupled to a memory element48. The memory element48controls the gate of transistor40according to a binary value equal to the complement of D stored within memory element48.

If the binary data received at input36is not equal to D, then the particular match line27is switchingly coupled to ground32through either transistor38and transistor40or transistor44and transistor46. If the binary data received at input36is equal to D, then the particular circuit34does not ground the particular match line27. If the data values received at the other respective inputs of the particular storage word29all match the corresponding “D” values of the respective memory cells16of storage word29, then the particular match line27is not grounded at all. Accordingly, match line27remains at a detectably high potential, and a data match between the data values held in the search register12and the particular storage word29is indicated.

In operation, each match line is charged to a precharge voltage by the action of the precharge circuit30. A binary value is stored in the search register12. Corresponding binary values are applied to the storage words14over the parallel bus20. If a bit value in the search register differs from a corresponding bit value in a search word14, that search word switches to provide an electrical path between the respective match line26and ground32. The capacitance28of the match line26is thus discharged, indicating, by a resulting low match line voltage, that the value in the storage word14does not match the value in the search register12. If a match line remains high (ungrounded), this indicates that the storage word14coupled to that match line26contains the same value as that present in the search register12.

In at least some prior art CAM devices, memory cells are arranged in a plurality of memory blocks on a substrate. Each memory block is connected to a respective dedicated data bus that supplies data to the memory block. Different data can be provided on each dedicated data bus. As a result different data may be searched in different memory blocks at the same time. A device100constructed according to this architecture is shown in FIG.2.

FIG. 2shows a substrate201on which are formed first202and second204memory blocks. Each memory block includes a plurality of CAM memory cells16formed on the substrate. The first memory block202has a first data input port206coupled to a first search register208. The second memory block204has a second data input port210coupled to a second search register212. The first208and second212search registers are each coupled to a respective search data bus215,217. A first control line219is coupled to a first control input218of the first memory block202and a second control input222of the first search register208. A second control line221is coupled to a third control input220of the second memory block204and to a fourth control input224of the second search register212.

A control circuit226is coupled to the control lines219,221. The control circuit226is adapted to apply respective control signals to the control lines219,221, thereby initiating comparisons between the values in the search registers208,212and storage words made up of memory cells16within the corresponding memory blocks202,204. Because each memory block has its own data bus219,221, this arrangement is costly in terms of device complexity and associated manufacturing yields, device real estate, and device energy and thermal budgets.

This costliness is a factor in the economics of CAM applications. Accordingly it is desirable to produce a CAM a memory integrated circuit having an improved data bus architecture.

BRIEF SUMMARY OF THE INVENTION

An exemplary embodiment of the present invention includes an architecture for a memory integrated circuit that exhibits greater areal efficiency and reduced complexity as compared with prior art designs. In one aspect of the invention, data on a data bus is time multiplexed so as to reduce the requirement for data conductors on an integrated circuit. Consequently, in one embodiment, the present invention includes a CAM that is compact as compared with prior art CAM devices. According to one embodiment of the invention, a CAM device includes an integrated circuit device with two or more memory blocks of CAM memory cells. The memory blocks of CAM memory cells are supported by a substrate. The substrate also supports a data bus that is mutually coupled to two search registers of at least two of the memory blocks respectively. The data bus supplies data to the two search registers according to alternating transitions of a periodic clock signal.

According to one embodiment, the invention includes a method for operating a content addressable memory that includes receiving a first data value for evaluation at a first memory block during a first time interval, receiving a second data value for evaluation at a second memory block during a second time interval and evaluating said both the first and second data values during a third time interval. According to one embodiment of the invention the first and second time intervals are separate so that the first and second data blocks receive unique data out of phase with one another from a single address bus. Evaluation of both data values takes place substantially simultaneously in the respective memory blocks.

The above and other features and advantages of the invention will be more readily understood from the following detailed description of the invention which is provided in connection with the accompanying drawings.

DETAILED DESCRIPTION OF THE INVENTION

In one exemplary embodiment, the present invention includes a CAM memory device architecture in which a single data bus is used to convey data to two memory blocks of a single CAM memory device in time multiplexed form. Respective data values are provided to the two memory blocks according to alternating phase transitions of a control signal. Consequently, a single data bus serves the function of two separate prior art data buses. The result is a savings in integrated circuit real estate and complexity, since one data bus is provided rather than two. Various exemplary aspects of the invention are directed to the architecture, and its method of formation, and to operation of a CAM memory device according to the invention.

FIG. 3shows an exemplary CAM memory device200according to one embodiment of the invention. The CAM device200includes a substrate201. The substrate may include any supporting structure including, but not limited to a semiconductor substrate that has an exposed substrate surface. The substrate may be a semiconductor substrate or other substrate. Semiconductor substrates should be understood to include silicon, silicon-on-insulator (SOI), silicon-on-sapphire (SOS), doped and undoped semiconductors, epitaxial layers of silicon supported by a base semiconductor foundation, and other semiconductor structures. The substrate may include regions or junctions in or over the base semiconductor or foundation formed during preparatory process steps.

A plurality of CAM memory cells16are formed on the substrate. According to one embodiment, the cells are arranged into discrete memory blocks202,204. One of the memory blocks202has a first data input port206coupled to a first search register208. Another of the memory blocks204has a second data input port210coupled to a second search register212. The first208and second212search registers are mutually coupled to a single search data bus214.

The search data bus consists of a plurality of data lines coupled to provide data in parallel format to the first search register208and second search register212. In an alternative embodiment of the invention, the data bus may consist of one or more data lines adapted to provide data in serial format to the first search register208and second search register212. The data lines may include various transmission media such as strip-lines, micro-strip lines, or waveguide structures including optical waveguide structures. In one embodiment, the inverter42(as shown inFIG. 1) is omitted from the CAM memory cells16, and the data bus214includes complemented data lines.

A control line216is mutually coupled to a first control input218of the first memory block202and a second control input220of the second memory block204. The control line216is also mutually coupled to a third control input222of the first search register208and to a fourth control input224of the second search register212. The control line may be formed of conductive material such as polysilicon or metallic material, or the control line may be formed as a waveguide, such as an optical waveguide. A control circuit226is formed on the substrate201and coupled to the control line216. The control circuit226is adapted to apply a control signal304(as discussed below in relation to inFIG. 4) to the control line216. According to various embodiments of the invention, buffer circuits adapted to amplify control or data signals may be provided on the substrate201in conjunction with the data bus and/or control signal lines.

As shown inFIG. 3, the memory blocks202,204are disposed in spaced relation to one another. The search registers208,212and the search data bus214are disposed between the memory blocks202and204.

FIG. 4shows a timing diagram300indicating signal timing relationships for operation of theFIG. 3CAM memory device. Reference is made to a time axis302. A control signal304is shown as a substantially periodic substantially symmetric square wave signal. The control signal304includes downward transitions306at periodically repeating times308and upward transitions310at periodically repeating times312. Graph314shows the time intervals316when first data, destined for the first search register208, is stable on the search data bus214. These time intervals316begin at periodically repeating times318and end at periodically repeating times320. Graph322shows the further time intervals324when second data, destined for the second search register212, is stable on the search bus214. These further time intervals324begin at periodically repeating times320and end at periodically repeating times318. Graph326shows the time intervals328during which stable output data is available at output port228of memory block202and output port230of memory block204. An evaluation time interval beginning at periodic time312is indicated by reference numeral330.

FIG. 5shows a flowchart500illustrating steps for reading a content502first comparand data is received onto data bus214(as shown in FIG.3). In a second step504the first comparand data is latched into first search register208. The latching of first comparand data into first search register208is triggered by downward transition306of signal304, (as shown in FIG.4). Referring again toFIG. 5, in a third step506second comparand data is received on to data bus214. In a fourth step508second comparand data is latched into second search register212. In the instant embodiment, latching of second comparand data into second search register212is triggered by upward transition310of signal304(a shown in FIG.4). The upward transition310is also received at the first202and second204memory blocks, as shown in step510of FIG.5. As shown in step512, the upward transition310of signal304also initiates the evaluation of fist data in first memory block202and second memory block204. This evaluation takes place during time interval330(as shown in FIG.4). In step514, first evaluation results are received at first output228of first memory block202and at second output230of second memory block204. This takes place during periodic time interval328(as shown in FIG.4).

FIG. 6shows a flowchart600illustrating the steps for manufacturing, according to one embodiment of the invention, a content addressable memory device. In a first step602a substrate is provided. In a second step604a plurality of CAM memory cells are formed on the substrate201. The cells are formed in at least first202and second204blocks of cells. In a third step606, first208and second212search registers are formed on the substrate201. In step608, the first search register208is coupled to the first memory block202and second search registered212is coupled to the second memory block204. In step610data bus214is formed over the substrate201. As described above, the data bus may include a parallel or serial architecture data bus, and may include a variety of transmission media, including conductors, transmission lines, and waveguides including optical waveguides. In step612the data bus is coupled to both the first208and second212search registers. In step614a control line is formed over the substrate. In step616, the control line is coupled to the first208and second212search registers and to the first202and second204memory blocks. In step618a control circuit226is formed over the substrate, and in step620, and output of the control circuit226is coupled to the control line216. In step622first228and second output ports230are formed over the substrate. In step624, the first output port228is coupled to the first memory block202and second output port230is coupled to the second memory block204.

FIG. 7illustrates an exemplary processing system800which utilizes a CAM device200constructed as described above with reference toFIGS. 1-6. The processing system800includes one or more processors801coupled to a local bus804. A memory controller802and a primary bus bridge803are also coupled the local bus804. The processing system800may include multiple memory controllers802and/or multiple primary bus bridges803. The memory controller802and the primary bus bridge803may be integrated as a single device806.

The memory controller802is also coupled to one or more memory buses807. Each memory bus accepts memory components808, which include at least one memory device200of the invention. Alternatively, in a simplified system, the memory controller802may be omitted and the memory components directly coupled to one or more processors801. The memory components808may be a memory card or a memory module. The memory components808may include one or more additional devices809. For example, the additional device809might be a configuration memory. The memory controller802may also be coupled to a cache memory805. The cache memory805may be the only cache memory in the processing system. Alternatively, other devices, for example, processors801may also include cache memories, which may form a cache hierarchy with cache memory805. If the processing system800include peripherals or controllers which are bus masters or which support direct memory access (DMA), the memory controller802may implement a cache coherency protocol. If the memory controller802is coupled to a plurality of memory buses807, each memory bus807may be operated in parallel, or different address ranges may be mapped to different memory buses807.

The primary bus bridge803is coupled to at least one peripheral bus810. Various devices, such as peripherals or additional bus bridges may be coupled to the peripheral bus810. These devices may include a storage controller811, a miscellaneous I/O device814, a secondary bus bridge815, a multimedia processor818, and a legacy device interface820. The primary bus bridge803may also coupled to one or more special purpose high speed ports822. In a personal computer, for example, the special purpose port might be the Accelerated Graphics Port (AGP), used to couple a high performance video card to the processing system800.

The storage controller811couples one or more storage devices813, via a storage bus812, to the peripheral bus810. For example, the storage controller811may be a SCSI controller and storage devices813may be SCSI discs. The I/O device814may be any sort of peripheral. For example, the I/O device814may be an local area network interface, such as an Ethernet card. The secondary bus bridge may be used to interface additional devices via another bus to the processing system. For example, the secondary bus bridge may be a universal serial port (USB) controller used to couple USB devices817via a secondary bus816and the secondary bus bridge815to the processing system800. The multimedia processor818may be a sound card, a video capture card, or any other type of media interface, which may also be coupled to one or more additional devices such as speakers819. The legacy device interface820is used to couple one or more legacy devices821, for example, older styled keyboards and mice, to the processing system800.

The processing system800illustrated inFIG. 7is only an exemplary processing system with which the invention may be used. WhileFIG. 7illustrates a processing architecture especially suitable for a general purpose computer, such as a personal computer or a workstation, it should be recognized that well known modifications can be made to configure the processing system800to become more suitable for use in a variety of applications. For example, many electronic devices which require processing may be implemented using a simpler architecture which relies on a CPU801coupled to CAM memory devices200.

FIG. 8shows a communications network900according to one aspect of the invention. The network includes a modem902having a first port904adapted to be coupled to the Internet906and a second port908adapted to be coupled to a local area network910. A router912has a remote-side port914coupled to the second port908of the modem, and an interface916including a plurality of local ports for connection to local devices. The router912includes a processor918for receiving and processing information received from and/or destined for the local devices. The router also includes a content accessible memory device200according to one embodiment of the invention, as described above. The content accessible memory200is coupled to the processor918and adapted to store and retrieve data under the control of the processor. A variety of local devices are coupled to respective local ports, of the interface916, including general-purpose computers922, telephone devices924, and network router devices926.

The description and drawings presented above illustrate only a few of the many embodiments which achieve the features and advantages of the present invention. Modification and substitutions to specific process conditions and structures can be made without departing from the spirit and scope of the present invention. Accordingly, the invention is not to be considered as being limited by the foregoing description and drawings, but is only limited by the scope of the appended claims.