On-access error correction for content-addressable memory
View Patent ↗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).
1 . A system comprising:
a summing content addressable memory (CAM) comprising CAM cells arranged into a number (l) rows and a number (n) columns, wherein the summing CAM is configured to sum outputs from a number (l) CAM cells connected along a respective column of the number (n) columns; and
one or more processing resources operative to program the CAM cells to store a matrix (A) having dimensions (l×n), wherein:
each row of the matrix (A) comprises a codeword of a linear code (C), and
the linear code (C) includes an all-one vector of dimension (n) as a codeword.
2 . The system of claim 1 , wherein:
CAM cells connected along a number (k) columns of the number (n) columns comprise task-driven CAM cells; and
CAM cells connected along a number (n−k) columns of the number (n) columns comprise redundancy CAM cells such that the respective row of the summing CAM comprises a number (k) task-driven CAM cells and a number (n−k) redundancy CAM cells.
3 . The system of claim 2 , wherein programming the summing CAM to store the matrix (A) having dimensions (l×n) comprises:
programming the number (k) task-driven CAM cells of the respective row to store task-driven values comporting with a computational task;
computing redundancy values for the number (n−k) redundancy CAM cells of the respective row based on the programmed task-driven values and the linear code (C); and
programming the number (n−k) redundancy CAM cells of the respective row to store the computed redundancy values such that the respective row stores a codeword of the linear code (C).
4 . The system of claim 3 , wherein computing the redundancy values for the number (n−k) redundancy CAM cells of the respective row based on the programmed task-driven values and the linear code (C) comprises:
computing the redundancy values for the number (n−k) redundancy CAM cells of the respective row such that the task-driven values and the redundancy values include a sequence of ones and zeros prescribed by the linear code (C).
5 . The system of claim 2 , wherein the one or more processing resources are operative to:
detect and correct one or more errors in an output vector (c) from the summing CAM based on the linear code (C).
6 . The system of claim 5 , wherein:
the output vector (c) has dimension (n);
the output vector (c) comprises a concatenation of a task-driven output vector (c′) and a redundancy output vector (c″);
the task-driven output vector (c′) has dimension (k) and corresponds to a summation between:
a vector-matrix multiplication between a transformation of an input vector (x) of dimension (l) received by the summing CAM and a task-driven stored matrix (A′) of dimension (l×k) stored by the task-driven CAM cells of the summing CAM, and
a vector multiplication between the all-one vector of dimension (n) and a constant value;
the redundancy output vector (c″) has a dimension (n−k) and corresponds to a summation between:
a vector-matrix multiplication between the transformation of the input vector (x) and a redundancy stored matrix (A″) of dimension (l×(n−k)) stored by the redundancy CAM cells of the summing CAM, and
a vector multiplication between the all-one vector of dimension (n) and the constant value; and
detecting and correcting one or more errors in the output vector (c) from the summing CAM based on the linear code (C) comprises detecting and correcting the one or more errors in the task-driven output vector (c′) based on the linear code (C) and the redundancy output vector (c″).
7 . The system of claim 1 , wherein:
a respective CAM cell of the summing CAM comprises one or more programmable memristors; and
programming the respective CAM cell comprises programming conductance of the one or more programmable memristors.
8 . A system comprising:
one or more processing resources operative to:
program a summing content addressable memory (CAM) to store a matrix (A) having dimensions (l×n), wherein:
each row of the matrix (A) comprises a codeword of a linear code (C), and
the linear code (C) includes an all-one vector of dimension (n) as a codeword; and
detect and correct one or more errors in an output vector (c) from the summing CAM based on the linear code (C).
9 . The system of claim 8 , further comprising the summing CAM.
10 . The system of claim 9 , wherein:
the summing CAM comprises CAM cells arranged into a number (l) rows and a number (n) columns; and
the summing CAM is configured to sum outputs from a number (l) CAM cells connected along a respective column of the number (n) columns.
11 . The system of claim 10 , wherein the one or more processing resources are operative to:
program a number (k) task-driven CAM cells of the respective row to store task-driven values comporting with a computational task;
compute redundancy values for a number (n−k) redundancy CAM cells of the respective row based on the programmed task-driven values and the linear code (C); and
program the number (n−k) redundancy CAM cells of the respective row to store the computed redundancy values such that the respective row stores a codeword of the linear code (C).
12 . The system of claim 11 , wherein computing the redundancy values for the number (n−k) redundancy CAM cells of the respective row based on the programmed task-driven values and the linear code (C) comprises:
computing the redundancy values for the number (n−k) redundancy CAM cells of the respective row such that the task-driven values and the redundancy values include a sequence of ones and zeros prescribed by the linear code (C).
13 . The system of claim 11 , wherein:
the output vector (c) has dimension (n);
the output vector (c) comprises a concatenation of a task-driven output vector (c′) and a redundancy output vector (c″);
the task-driven output vector (c′) has dimension (k) and corresponds to a summation between:
a vector-matrix multiplication between a transformation of an input vector (x) of dimension (l) received by the summing CAM and a task-driven stored matrix (A′) of dimension (l×k) stored by the task-driven CAM cells of the summing CAM, and
a vector multiplication between the all-one vector of dimension (n) and a constant value;
the redundancy output vector (c″) has a dimension (n−k) and corresponds to a summation between:
a vector-matrix multiplication between the transformation of the input vector (x) and a redundancy stored matrix (A″) of dimension (l×(n−k)) stored by the redundancy CAM cells of the summing CAM, and
a vector multiplication between the all-one vector of dimension (n) and the constant value; and
detecting and correcting one or more errors in the output vector (c) from the summing CAM based on the linear code (C) comprises detecting and correcting the one or more errors in the task-driven output vector (c′) based on the linear code (C) and the redundancy output vector (c″).
14 . The system of claim 8 , wherein:
a respective CAM cell of the summing CAM comprises one or more programmable memristors; and
programming the respective CAM cell comprises programming conductance of the one or more programmable memristors.
15 . A method comprising:
programming a summing content addressable memory (CAM) to store a matrix (A) having dimensions (l×n), wherein:
each row of the matrix (A) comprises a codeword of a linear code (C), and
the linear code (C) includes an all-one vector of dimension (n) as a codeword; and
detect and correct one or more errors in an output vector (c) from the summing CAM based on the linear code (C).
16 . The method of claim 15 , wherein:
the summing CAM comprises CAM cells arranged into a number (l) rows and a number (n) columns; and
the summing CAM is configured to sum outputs from a number (l) CAM cells connected along a respective column of the number (n) columns.
17 . The method of claim 16 , wherein programming the summing CAM to store the matrix (A) having dimensions (l×n) comprises:
programing a number (k) task-driven CAM cells of the respective row to store task-driven values comporting with a computational task;
computing redundancy values for a number (n−k) redundancy CAM cells of the respective row based on the programmed task-driven values and the linear code (C); and
programming the number (n−k) redundancy CAM cells of the respective row to store the computed redundancy values such that the respective row stores a codeword of the linear code (C).
18 . The method of claim 17 , wherein computing the redundancy values for the number (n−k) redundancy CAM cells of the respective row based on the programmed task-driven values and the linear code (C) comprises:
computing the redundancy values for the number (n−k) redundancy CAM cells of the respective row such that the task-driven values and the redundancy values include a sequence of ones and zeros prescribed by the linear code (C).
19 . The method of claim 17 , wherein:
the output vector (c) has dimension (n);
the output vector (c) comprises a concatenation of a task-driven output vector (c′) and a redundancy output vector (c″);
the task-driven output vector (c′) has dimension (k) and corresponds to a summation between:
a vector-matrix multiplication between a transformation of an input vector (x) of dimension (l) received by the summing CAM and a task-driven stored matrix (A′) of dimension (l×k) stored by the task-driven CAM cells of the summing CAM, and
a vector multiplication between the all-one vector of dimension (n) and a constant value;
the redundancy output vector (c″) has a dimension (n−k) and corresponds to a summation between:
a vector-matrix multiplication between the transformation of the input vector (x) and a redundancy stored matrix (A″) of dimension (l×(n−k)) stored by the redundancy CAM cells of the summing CAM, and
a vector multiplication between the all-one vector of dimension (n) and the constant value; and
detecting and correcting one or more errors in the output vector (c) from the summing CAM based on the linear code (C) comprises detecting and correcting the one or more errors in the task-driven output vector (c′) based on the linear code (C) and the redundancy output vector (c″).
20 . The method of claim 15 , wherein:
a respective CAM cell of the summing CAM comprises one or more programmable memristors; and
programming the respective CAM cell comprises programming conductance of the one or more programmable memristors.