Analog content addressable memory cell and array for soft decision boundaries and soft decision tree computation system using the same
A SDT computation system is provided. The SDT computation system includes a SDT module, an ACAM array, and a mapping module. The SDT module is for outputting a final probability and configured to provide a SDT structure with a root node and deeper inner nodes for calculating probability, in which the final probability of each leaf node of the SDT structure is a product of all of node probabilities along a path from the root node to each leaf node, and wherein a final output of the SDT module is from a leaf with the highest probability. The mapping module is configured to map the SDT structure into the ACAM array, such that each of the ACAM cells in the ACAM array has a threshold programmed to be a parameter for a node in a path leading towards the leaf node of the SDT structure.
1 . An analog content addressable memory (ACAM) cell for mapping a well-trained SDT into an analog CAM configuration, comprising:
a first floating-gate transistor (FG-FET) and a second FG-FET;
a match line electrically coupled to drains of the first and second FG-FETs;
a source coupled line electrically coupled to sources of the first and second FG-FETs;
a first search line electrically coupled to a gate of the first FG-FET; and
a second search line electrically coupled to a gate of the second FG-FET, the first and second FG-FETs are collectively configured to serve for a dynamic process which is started with pre-charging the match line to a high-level voltage and then applying a voltage to the first search line or the second search line to increase electrical potential of the corresponding gate of the first FG-FET or the second FG-FET, such that the match line discharges to the source coupled line, resulting in a reduction in a match-line voltage, permitting the match-line voltage to decrease for approaching to zero within a matching range of a search-line voltage;
wherein the ACAM cell is configured to operate to provide the match-line voltage without conversion by a sense amplifier into a binary match/mismatch signal.
2 . The ACAM cell of claim 1 , wherein, when the voltage applied to the first search line is smaller than a threshold voltage of the first FG-FET, the first FG-FET works at a subthreshold region, and a drain current of the first FG-FET is described as:
I
d
,
sub
=
I
0
e
q
(
V
g
-
V
t
h
)
n
K
T
(
1
-
e
-
q
V
d
K
T
)
,
where V g is a gate voltage of the first FG-FET, V d is a drain voltage of the first FG-FET, V th is the threshold voltage of the first FG-FET, and I 0 , q, n, K and T are all constants.
3 . The ACAM cell of claim 2 , wherein, when the voltage applied to the first search line is higher than the threshold voltage of the first FG-FET, the first FG-FET initially operates in the saturation region, and the drain current of the first FG-FET is described as:
I
d
,
sat
=
K
P
2
W
L
(
1
+
λ
V
d
)
(
V
g
-
V
t
h
)
2
,
where KP, λ,
W
L
are constants associated with the processing dynamic process of the first FG-FET.
4 . The ACAM cell of claim 3 , wherein the first FG-FET then switches to a linear region as the drain voltage V d of the first FG-FET decreases, and the drain current of the first FG-FET is described as:
I
d
,
lin
=
K
P
W
L
(
1
+
λ
V
d
)
(
V
g
-
V
t
h
-
V
d
2
)
V
d
.
(
Eq
.
5
)
5 . The ACAM cell of claim 1 , wherein each of the first FG-FET and the second FG-FET has a threshold voltage in a range from 0.56 V to 1.59 V.
6 . An analog content addressable memory (ACAM) array for mapping a well-trained SDT into an analog CAM configuration, comprising:
an input controller;
an output receiver; and
a plurality of ACAM cells of claim 1 electrically coupled between the input controller and the output receiver and arranged as multiple rows and multiple columns, wherein the ACAM cells in the same row share a voltage from the same match line, and wherein the first search lines and the second search lines are electrically connected to the input controller, and the match lines are electrically connected to the output receiver, such that the ACAM cells are configured to map signals from the input controller and output match-line voltages to the output receiver in response to a mapping result during the dynamic process.
7 . The ACAM array of claim 6 , wherein the input controller is configured to feed an input signal to each of the ACAM cells in the same column via a voltage interval.
8 . The ACAM array of claim 7 , wherein the output receiver comprises a WTA (Winner-Takes-All) circuit to compare match-line voltages of different rows according to the match lines, so as to find the largest one among them to determine a final output.
9 . The ACAM array of claim 8 , wherein the output receiver is further configured to process the final output as a probability signal to be output from the ACAM array, and the ACAM array further comprises at least one blank cell arranged adjacent to at least one of the ACAM cells, wherein the blank cell is without mapping thresholds and is configured to respond with a probability of 1.
10 . The ACAM array of claim 9 , wherein the blank cell is adjacent to at least one of the ACAM cells in the same row.
11 . The ACAM array of claim 9 , wherein the blank cell is adjacent to at least one of the ACAM cells in the same column.
12 . The ACAM array of claim 6 , wherein the ACAM array is a N*N array, where N is a positive integer greater than 1.
13 . The ACAM array of claim 6 , wherein the match-line voltages generated by the ACAM cells are supplied to the output receiver without an intermediate sense amplification stage converting match-line voltages to digital match indicators.
14 . A soft decision tree (SDT) computation system, comprising:
a SDT module for outputting a final probability and configured to provide a SDT structure with a root node and deeper inner nodes for calculating probability, wherein the final probability of each leaf node of the SDT structure is a product of all of node probabilities along a path from the root node to each leaf node, and wherein a final output of the SDT module is from a leaf with the highest probability;
an analog content addressable memory (ACAM) array of claim 6 ;
a mapping module configured to map the SDT structure into the ACAM array, such that each of the ACAM cells in the ACAM array has a threshold programmed to be a parameter for a node in a path leading towards the leaf node of the SDT structure.
15 . The SDT computation system of claim 14 , wherein I-V characteristics of the ACAM cells in the ACAM array within an interval of the search-line voltage during the dynamic process are captured for mapping a well-trained SDT by the mapping module.
16 . The SDT computation system of claim 14 , wherein threshold voltages of two FG-FETs in each of the ACAM cells in the ACAM array are adjusted between high and low matching bounds, so as to act as an inner node in the SDT structure.
17 . The SDT computation system of claim 14 , wherein the ACAM array further comprises at least one blank cell arranged adjacent to at least one of the ACAM cells, which is without mapping thresholds and is configured to respond with a probability of 1.
18 . The SDT computation system of claim 14 , wherein the SDT structure is applied to a decision-making process in autonomous driving, the root node and inner nodes correspond to initial processing of sensor data and environmental factors, and the leaf nodes represent potential actions containing stopping, turning, and accelerating, and wherein the decision-making process in the autonomous driving is mapped to the ACAM array by the mapping module to accurately and reliably determine an appropriate action for the autonomous driving.
19 . The SDT computation system of claim 14 , wherein the match-line voltages generated by the ACAM array are processed as continuously varying analog responses corresponding to soft decision boundaries of the deeper inner nodes of the SDT structure to determine the final output.