Shulou(Shulou.com)06/01 Report--

Because I was so sleepy last night, my eyes were dazzled and my brain was short-circuited when explaining the problem. When I got up in the morning, I found that my family was still asleep, so I wanted to continue to talk about what I didn't say last night.

My explanation diagram

Give my hardware forwarding schematic again:

Please note that there is no optimization, you can try to further optimize it with a few tricks, or you can map it directly with the standard TCAM. In this figure, I show in detail how the "longest prefix" logic is done, and in the example of TCAM routing forwarding table, it is often painted as a black box, called "priority logic controller". However, this logic circuit is relatively simple, and I believe you can design it yourself with a little thought.

In fact, in the image above, there is a container called "inverse mask", which is arranged bit by bit next to the bit line comparison key at the back of the decoder, which is a standard TCAM practice.

About content addressing and address addressing

We all know that cache is expensive, so it can't be too big, but the content can be very big, because it's cheaper.

But can you explain it from a technical level? In fact, the difference between expensive and cheap is caused by technical reasons. Let's take a look at the circuit of the memory array:

This is a very typical matrix, and it's very simple. But for CAM circuits, it's not that simple, as shown in the following figure:

For TCAM, the need to add a care logic, it is more complex, not only the circuit complex, power consumption also increased, you know, in the process of CAM/TCAM matching, all parts of the circuit work at the same time.

About hardware HASH

Many people say that there is a hardware HASH in CPU cache, such as taking the nth to m bits of the address, which is in fact a shift, modular operation! From the programmer's point of view, the simplest HASH algorithm programmers know is more complex than this. In fact, hardware engineers are dismissive of programmers, because their focus is on how to make the circuit work at the same time with the lowest power consumption and smaller circuit size. CAM/TCAM uses hardware HASH, a very simple hardware HASH, but the circuit can work at the same time. This is a big problem for software hash, which aims to make hash distribution more uniform and average performance better. In this way, the average variance of the conflict list length is minimum. The software hash is designed to resolve conflicts, but the hardware HASH does not need to do so, because the hardware can do it at the same time when the software seems to have to traverse the collision list serially.

Sequentially executed CPU

When the computer was designed, it was a model of sequential execution, and instructions were executed one by one. This is because it completely simulates human behavior in the real world. This means that all the algorithmic steps running on the computer are implemented sequentially over time, and a good algorithm is designed to minimize the time spent. However, the design of the hardware circuit does not follow the way people do things in the real world, or at least not very much. It is impossible for a person to do many things at the same time, the execution process of the hardware circuit is more like the process of flooding, due to the potential energy, the flood at the same time (attention, at the same time!) All the places it could go swallowed up everything in an instant.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.