Hewlett Packard Enterprise Development LP

Other

Giacomo Pedretti

Catherine Graves

John Paul Strachan

Thomas Van Vaerenbergh

Tobias Frederic Ziegler

Ron Roth

Sergey Serebryakov

Pedro Henrique Rocha Bruel

John Moon

Zhong Sun

Daniele Ielmini

Thomas Maurits M Van Vaerenbergh

Luca Buonanno

Todd Richmond

Lei Zhao

Examples of the presently disclosed technology provide a methodology for detecting and correcting errors in a summing content-addressable memory (Σ-CAM) while the Σ-CAM is performing a computational task (i.e., 'on-access' error correction). The methodology involves adding redundancy columns to a Σ-CAM used to store a task-driven matrix (i.e., a matrix having values comporting with a computational task). Examples can leverage an encoder to compute redundancy values for the redundancy columns such that the Σ-CAM stores a codeword of a linear code (C) in each row. Examples also modify the linear code (C) used to compute redundancy values. Namely, examples modify the linear code (C) so that it includes the all-one vector. With this modification, a system of the presently disclosed technology can detect and correct errors in an output vector from a Σ-CAM based on this modified/particularized linear code (C).

On-access error correction for content-addressable memory

In an implementation, a device includes: a first inverter; a first sense amplifier connected to the first inverter; a first match line connected to the first sense amplifier; a first analog content addressable memory cell including: a first pull-down transistor; a second pull-down transistor, the first pull-down transistor and the second pull-down transistor being connected in series between the first match line and a reference node; a first memory circuit configured to store a first upper bound of a first range and to activate the first pull-down transistor when an analog input value is less than the first upper bound of the first range; and a second memory circuit configured to store a first lower bound of the first range and to activate the second pull-down transistor when the analog input value is greater than the first lower bound of the first range.

Analog content addressable memory for general computing

A technique for compressing an analog content addressable memory (CAM) array is provided. Random input data is applied to the analog CAM array, and an average measure of similarity is calculated for each output row of the analog CAM array. Rows of the analog CAM array that have measures of similarity that are close to each other can be eliminated, such as by removing similar rows or merging together similar rows. Thus, the analog CAM array size can be reduced without a loss in accuracy of a model stored on the analog CAM array.

Compression of analog content addressable memory

Examples of the presently disclosed technology provide CAM-based circuits specially constructed to implement Boolean satisfiability problems involving k-XOR-SAT clauses. With the strategic addition of auxiliary counting and logic circuits that evaluate match line voltage outputs of a CAM at k discrete times in order to determine whether a counted number of matches returned by a match line satisfies a pre-determine parity condition—where k represents a number of literals of a k-XOR-SAT clause of a Boolean satisfiability problem—a circuit of the present technology can leverage a common CAM (i.e., the same CAM) to implement the k-XOR-SAT clause and k-SAT clauses. Accordingly, this extremely versatile circuit can be used to implement k-XOR-SAT and k-SAT-k-XOR-SAT hybrid problems in less time, and with less hardware and power consumption than existing hardware accelerators.

Compact k-XOR-SAT filtering with cams

Systems and methods are provided for employing analog content addressable memory (aCAMs) to achieve low latency complex distribution sampling. For example, an aCAM core circuit can include an aCAM array. Amplitudes of a probability distribution function are mapped to a width of one or more aCAM cells in each row of the aCAM array. The aCAM core circuit can also include a resistive random access memory (RRAM) storing lookup information, such as information used for processing a model. By randomly selecting columns to search of the aCAM array, the mapped probability distribution function is sampled in a manner that has low latency. The aCAM core circuit can accelerate the sampling step in methods relying on sampling from arbitrary probability distributions, such as particle filter techniques. A hardware architecture for an aCAM Particle Filter that utilizes the aCAM core circuit as a central structure is also described.

CAMs for low latency complex distribution sampling

A system for facilitating an enhanced k-SAT solver is provided. The system can include a set of analog content addressable memory (aCAM) modules that can represent an expression in a conjunctive normal form (CNF), wherein a respective aCAM module corresponds to a clause of the expression. The system can also include a set of data lines that can provide input candidate values to the set of aCAM modules. A controller of the system can program the set of aCAM modules with respective analog values to represent the expression. The system can also include sensing logic block to determine a distance of a current solution from a target solution based on a combination of respective outputs from the set of aCAM modules. The controller can then iteratively modify an input value for a subset of data lines until the current solution converges based on a convergence condition.

Enhanced k-SAT solver using analog content addressable memory

The disclosure generally provides for a method of solving a K-SAT problem. The method comprises programming one or more clauses of a Boolean expression for a K-SAT problem written in negated disjunctive normal form (DNF) to a ternary-CAM (TCAM) array comprising columns and rows of TCAM cells, applying an interpretation comprising one or more binary variables expected to solve the Boolean expression as an input along the columns to the TCAM array, returning a binary value for each clause and updating one or more variables within the interpretation if at least one clause is violated.

Compact K-SAT verification with TCAMs

Systems and methods are provided for implementing a low power and area ternary content addressable memory (TCAM). An example of a TCAM comprises a match line, and a plurality of TCAM cells connected along the match line. Each TCAM cell stores a state of a threshold value. The TCAM cells are configured to pull down a signal over the match line in response to inequality between an input search and the threshold value. The plurality of TCAM cells comprises a number of TCAM cells that is less than the threshold value. The input values can be encoded according to a first encoding scheme and the threshold value can be encoded according to one of a second and a third encoding scheme based on an inequality check mapped to the plurality of TCAM cells.

Inequality check with ternary cam

Embodiments of the disclosure provide a system, method, or computer readable medium for providing a differentiable content addressable memory (aCAM) that implements an analog input analog storage and analog output learning memory. The analog output of the differentiable CAM can provide input to a learning algorithm, which may compute the gradients in comparison to historic values and reduce data inaccuracies and power consumption.

Differentiable content addressable memory

Embodiments of the disclosure provide a system, method, or computer readable medium for programming a target analog voltage range of an analog content addressable memory (aCAM) row. The method may comprise calculating a threshold current sufficient to switch a sense amplifier (SA) on and discharge a match line (ML) connected to a cell of the aCAM; and based on calculating the threshold current, programming a match threshold value by setting a memristor conductance in association with the target analog voltage range applied to a data line (DL) input. The target analog voltage range may comprise a target analog voltage range vector.

Iterative programming of analog content addressable memory

The disclosure generally provides for a method of solving a K-SAT problem. The method comprises programming one or more clauses of a Boolean expression for a K-SAT problem written in negated disjunctive normal form (DNF) to a ternary-CAM (TCAM) array comprising columns and rows of TCAM cells. The method further includes applying an interpretation comprising one or more binary variables expected to solve the Boolean expression as an input along the columns to the TCAM array, returning a binary value for each clause, randomly selecting one matched match line, determining a selected clause from one or more violated clause, and altering one or more literals within the interpretation using a break count for each variable of the selected clause.

Stochastic local search accelerator based on cams for solving constraint satisfaction problems

Examples increase precision for aCAMs by converting an input signal (x) received by a circuit into a first analog voltage signal (V(x)) representing the most significant bits of the input signal (x) and a second analog voltage signal (V(x)) representing the least significant bits of the input signal (x). By dividing the input signal (x) bit-wise into the first analog voltage signal (V(x)) and the second analog voltage signal (V(x)), the circuit can utilize aCAM sub-circuits implementing a combination of Boolean operations to search the input signal (x) against 2programmable levels, where 'M' represents the number of programmable bits for each aCAM sub-circuit. Thus, using similar circuit hardware, example circuits square the number of programmable levels of conventional aCAMs (which generally only have 2programmable levels). Accordingly, examples provide new aCAMs that can carry out more complex computations than conventional aCAMs of comparable cost, size, and power consumption.

Growing community of inventors

Cernusco sul Naviglio, Italy

Giacomo Pedretti