Ternary Computing

Posted Jan 14, 2020 21:26 UTC (Tue) by jccleaver (guest, #127418)
Parent article: Accelerating netfilter with hardware offload, part 1

I had no idea ternary memory and logic was being used at that low level. Brings to mind the aborted attempts to actually run full ternary computers (https://en.wikipedia.org/wiki/Ternary_computer) up into the 1970s.

Surprised to see that logic used there (although the 1/0/NULL of SQL is another example of modern usage) -- I wonder if ternary silicon is an area of research for this hardware.

Ternary Computing

Posted Jan 14, 2020 21:48 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link] (6 responses)

In TCAM the third level is more like a wildcard for addressing.

But there are many other silicon devices that use multiple levels, like MLC flash cells. After all, the world is analog.

Ternary Computing

Posted Jan 15, 2020 22:27 UTC (Wed) by leromarinvit (subscriber, #56850) [Link] (5 responses)

At least Wikipedia (the world's One True Single Source Of Truth, obviously) says it's typically implemented with a second bit rather than relatively exotic multi-level logic. That would have been my gut feeling as well, that designers would rather avoid complicating their design and process for saving what's essentially peanuts in transistor count.

Also, this is SRAM. MLC flash works by storing different charge levels in the cell. The closest equivalent I can think of for SRAM would be different voltages - more or less impossible to achieve using a single supply, without first generating a second voltage from that. Which wastes chip area and power for no real gain, making the two-bit solution look even better in comparison.

Ternary Computing

Posted Jan 15, 2020 22:36 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link]

For MLCs it's implemented as a true multi-level device. It basically uses different charge levels to encode different bit combinations.

Ternary Computing

Posted Jan 15, 2020 23:51 UTC (Wed) by Sesse (subscriber, #53779) [Link] (2 responses)

TCAM may be peanuts in a NIC with 256 entries, but not in a large switch/router. It's how switches manage to do route lookups in wirespeed; you have one entry (IIRC, typically 192 TCAM bits for matching, well, various stuff) per route, and then something like 512k routes. More in modern devices, now that the IPv4 routing table is larger than that… so think 1M routes, 192 bits for each, so now you have 192M SRAM cells and comparators to run in parallel! And each line card has the same amount! So if you could somehow design those with exotic logic instead of two bits, it would be a win.

Someone once described TCAM to me as “the stuff you upgrade in your router, and then the power bill goes up”.

Ternary Computing

Posted Jan 16, 2020 0:02 UTC (Thu) by leromarinvit (subscriber, #56850) [Link] (1 responses)

Interesting perspective, thanks! That is indeed a lot of SRAM.

Ternary Computing

Posted Jan 16, 2020 8:30 UTC (Thu) by leromarinvit (subscriber, #56850) [Link]

On second thought, maybe if you can implement TCAM with DRAM, you could get the X state by charging the capacitor a little less (shorter / via a higher resistance path). Then design the comparator such that it accepts both 0 and 1 if the other input is in this "middle band". If the refresh cycle is fast enough that a 1 won't decay into an X (or an X into a 0), then maybe this could work.

But I'm sure people much smarter than me have tried to optimize TCAM for many years, and are already using ideas much better than I can think of, so I'll stop now.

Ternary Computing

Posted Jan 31, 2020 21:07 UTC (Fri) by brouhaha (subscriber, #1698) [Link]

At least Wikipedia (the world's One True Single Source Of Truth, obviously) says it's typically implemented with a second bit rather than relatively exotic multi-level logic.

The TCAM used in network switches, routers etc. definitely works that way, storing the ternary values as two bits each. It is ternary in the same sense that BCD is decimal; both are encoded using only binary digits. A TCAM cell is effectively much more than twice the size of a normal SRAM cell because it also contains the comparator logic. This is one reason why TCAM chips are orders of magnitude more expensive than an equivalent amount of SRAM.

It would be possible to build SRAM using multilevel cells, but most likely that would result in larger and slower memory than using binary.

On the other hand, two-bit-per-cell masked ROM technology exists. Each cell has transistors chosen from four transistor sizes resulting in four possible on-state resistances. Reading from it works the same way as MLC flash; the sense amplifier feeds analog comparators to distinguish the levels. The microcode of the original Intel 8087 numeric coprocessor was stored in two-bit-per-cell masked ROM.