Employ CAM in Reprogrammable Finite State Machine, ROM Patch, and TLB

Make it to the Right and Larger Audience

Blog/Press Release

Employ CAM in Reprogrammable Finite State Machine, ROM Patch, and TLB

CAM stands for content addressable memory. It sees various applications in signal processing, coding/decoding, compression, etc. I find a 2006 IEEE survey paper, Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey , helpful in understanding CAM function and implementation.

 

Below is the CAM architecture. It compares input search data against a table of stored data, and returns the address of matching data.

In most applications, returned matching addresses are not very helpful unless it is used to address another memory and return that RAM’s content. As shown in below, a search data of “01101” comes in, CAM compares it with stored data and finds a match at address 01 and outputs address “01”, “01” is further used as address to access an RAM and eventually outputs “port B” which is saved in address “01” in RAM.

So what CAM circuitry really does is to simply translate input search data “01101” into pre-programmed “port B”.

 

Let’s take a look of how CAM can be used in reprogrammable FSM or reconfigurable FSM. Finite State Machine (FSM) is normally hard-coded which lacks of flexibility. Reconfigurable FSM is to allow firmware to change FSM behavior such as state transition condition, state output, etc., in field. Here is a 2002 US patent about this topic, Re-programmable finite state machine. The following diagram is extracted from this patent.

In above diagram, Fig1 shows architecture of a typical hard-coded FSM. CSR is current state register, NSL is next state logic, and OL is output logic. As expected, next state is determined by current state as well as input vector and output vector is determined by current state as well as input vector too.

Now the question is how to make hard-coded FSM reprogrammable. The patent adopts CAM-based approach. Each CAM cell contains several bits to indicate “current state” and several bits to indicate “input vector”. OA is output array and it is a RAM which contains several bits for output vector and several bits for “current state” or should be better named “next state”.

At any moment, the combined “input vector” and “current state vector” comes into CAM as the search data. It is compared with the stored data in CAM. CAM outputs address of the matching data. This address is used to access OA RAM. Based on what is saved in OA RAM, output vector is driven and “next state” is generated.

Both CAM and OA are RAM based and can be programmed by firmware. Here we go, a reconfigurable FSM.

One concern may be raised out of above circuitry is the size f CAM. Let’s say 4 bits are used to encode states of FSM and 3 bits to represent three inputs. This is 7 bits in total and a 128×7 CAM is needed to implement this simple FSM?! As a matter of fact, this is not the case otherwise this approach is pretty much unusable in real application. Thanks to the so-called Ternary CAMs (TCAM), entries of CAM can be much reduced and doesn’t need to represent each combination. TCAM allows a third matching state of “X” or “don’t care” for one or more bits in the stored dataword, thus adding flexibility to the search. For example, a ternary CAM might have a stored word of “10XX0” which will match any of the four search words “10000”, “10010”, “10100”, or “10110”. The added search flexibility comes at an additional cost over binary CAM as the internal memory cell must now encode three possible states instead of the two of binary CAM. This additional state is typically implemented by adding a mask bit (“care” or “don’t care” bit) to every memory cell.

 

Now let’s take a look of how CAM is used in TLB and ROM patch. Below diagram is extracted from Wikipedia, Translation lookaside buffer. Translation lookaside buffer (TLB) basically translates page-based virtual or logical address to frame-based physical address. This data to data translation is exactly what CAM can offer. Below diagram shows how a CAM is employed in a TLB design to translate “page number” to “frame number”.

 

I have another post about ROM Patch Circuit. If we compare the ROM patch circuit shown in below with above TLB, they are very similar. Both try to translate one address to another address. So it is straightforward CAM can be used in below ROM patch circuitry too.

 

A CAM is a good choice for implementing this lookup table operation due to its fast search capability. But what is the catch of CAM? Unfortunately the speed of a CAM comes at the cost of increased silicon area and power consumption, two design parameters that designers strive to reduce. As CAM applications grow, demanding larger CAM sizes, the power problem is further exacerbated. Reducing power consumption, without sacrificing speed or area, is the main thread of recent research in large-capacity CAMs.

 

 

 

 
ASIC engineer
Author brief is empty
Groups:

Tags:

6 Comments
  1. rao_mallikarjun 1 year ago
    0
    -0

    nice

    0
  2. rao_mallikarjun 1 year ago
    0
    -0

    goos

    0
  3. Shubu_rahman 2 years ago
    0
    -0

    Yeah

    0
  4. Shubu_rahman 2 years ago
    0
    -0

    Better

    0
  5. Shubu_rahman 2 years ago
    0
    -0

    Good

    0
  6. Shubu_rahman 2 years ago
    0
    -0

    Nice

    0

Contact Us

Thanks for helping us better serve the community. You can make a suggestion, report a bug, a misconduct, or any other issue. We'll get back to you using your private message ASAP.

Sending

©2021  ValPont.com

Forgot your details?