Method and System for Emulating Content-Addressable Memory Primitives

Abstract

A method and system for emulating content-addressable memory (CAM) primitives (e.g., a read operation) is disclosed. According to one embodiment, a method is provided for emulating a read operation on a plurality of CAM elements utilizing a read input including match input data and a CAM element selection index. In the described method, match reference data is distributed among a plurality of random-access memory (RAM) elements by storing match reference data corresponding to each of the plurality of CAM elements within a first RAM element of the plurality. Thereafter, a first record is identified within the first RAM element utilizing a first portion of the match input data and the CAM element selection index. A read operation result is then generated utilizing the first record.

1 . An apparatus for emulating a read operation on a plurality of content-addressable memory elements utilizing a read input, wherein said read input comprises match input data and a content-addressable memory element selection index, said apparatus comprising:
 means for distributing match reference data among a plurality of random-access memory elements, wherein said means for distributing includes means for storing match reference data corresponding to each of said plurality of content-addressable memory elements within a first random-access memory element of said plurality of random-access memory elements;   means for identifying a first record within said first random-access memory element utilizing a first portion of said match input data and said content addressable memory element selection index; and   means for generating a read operation result utilizing said first record; wherein:
 said means for distributing further includes means for storing match reference data corresponding to each of said plurality of content-addressable memory elements within a second random-access memory element of said plurality of random-access memory elements, 
 said apparatus further comprises means for identifying a second record within said second random-access memory element utilizing a second portion of said match input data and said content addressable memory element selection index, and 
 said means for generating includes means for generating said read operation result utilizing said first record and said second record. 
   
   
   
       2 . The apparatus of  claim 1 , wherein said match reference data comprises cache tag match reference data. 
   
   
       3 . The apparatus of  claim 2 , wherein
 said read input data comprises a data processing system memory address;   said match input data comprises cache tag data of said data processing system memory address; and   said content addressable memory element selection index comprises a cache set index of said data processing system memory address.   
   
   
       4 . The apparatus of  claim 3 , wherein
 said means for identifying said first record comprises means for identifying first cache tag match reference data of said cache tag match reference data within said first random-access memory element,   said means for identifying said second record comprises means for identifying second cache tag match reference data of said cache tag match reference data within said second random-access memory element, and   said means for generating said read operation result utilizing said first record and said second record comprises means for logically combining said first cache tag match reference data and said second cache tag match reference data.   
   
   
       5 . The apparatus of  claim 3 , wherein said means for generating said read operation result comprises means for generating a cache tag lookup result and said apparatus further comprises means for accessing a cache memory element utilizing said cache tag lookup result. 
   
   
       6 . An apparatus for emulating a read operation on a plurality of content-addressable memory elements utilizing a read input, wherein said read input comprises match input data and a content-addressable memory element selection index, said apparatus comprising:
 a first random-access memory element to store a first match reference data record, wherein said first random-access memory element includes:
 a read input port to receive a first portion of said match input data and said content-addressable memory element selection index; and 
 a read output port to present said first match reference data record; 
   a second random-access memory element to store a second match reference data record, wherein said second random-access memory element includes:
 a read input port to receive a second portion of said match input data and said content-addressable memory element selection index; and 
 a read output port to present said second match reference data record; and combinatorial logic, coupled to said first random-access memory element and said second random-access memory element, to generate a read operation result utilizing said first record and said second record; wherein
 said read input data comprises a data processing system memory address; 
 said match input data comprises cache tag data of said data processing system memory address; and 
 said content addressable memory element selection index comprises a cache set index of said data processing system memory address. 
 
   
   
   
       7 . The apparatus of  claim 6 , wherein said combinatorial logic comprises a logical AND gate element.