Browse Prior Art Database

A Very Large Bit-wise Vector Register File for Matching and T-CAM Applications

IP.com Disclosure Number: IPCOM000237828D
Publication Date: 2014-Jul-15
Document File: 2 page(s) / 67K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a novel micro architecture that can be used for matching a large number of values with a key when using ternary Content-Addressable Memories (CAMs) for matching in analytics applications. The presented design consists of a long vector register file and bit-wise access.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 01 of 2

A Very Large Bit-wise Vector Register File for Matching and T-CAM Applications

Ternary Content-Addressable Memories (CAMs) are used for matching in several analytics applications. The look-up problem comprises two different variants: testing membership of a search key in a set, and retrieving a previously stored value corresponding to the search key. Traditionally, bitmap indices or Bloom filters are used for the former; hash directories and content addressable memories (CAMs) for the latter. However, scalable implementations are difficult to obtain. For testing membership of a search key in a set, compression techniques or a probabilistic approach with Bloom filters may be used reduce storage requirements. Bloom filters have the disadvantage of possibly returning false positives. Hence, such filters can only be used as a look-up cache. Hash tables are notoriously difficult to implement due to the random access memory patterns. CAMs have similar scalability issues.

The novel contribution is a micro architecture that can be used for matching a large number of values with a key. The presented design consists of a long vector register file and bit-wise access. The bit-based processing method described in the sequel results in a low-complexity digital design with localized connectivity. This permits the instantiation of computation logic for each element in the vector and thus gives rise to a high level of parallelism in the computation.

The novel architecture can be used to compute both exact matches and near matches, (i.e. matches with a bounded number of differing bits) in NW bits of storage and O(W) time steps. Here, N corresponds to the number of terms entered and W the length of a term. As such, it can also be used to build Ternary CAMs (T-CAMs). The approach allows emulation of deep and wide CAMs.

The architecture consists of a set of scalar and vector registers and a hard...