Patent Publication Number: US-2023162024-A1

Title: Ternary content addressable memory (tcam)-based training method for graph neural network and memory device using the same

Description:
This application claims the benefit of U.S. provisional application Ser. No. 63/282,696, filed Nov. 24, 2021, and U.S. provisional application Ser. No. 63/282,698, filed Nov. 24, 2021, the subject matters of which are incorporated herein by references. 
    
    
     TECHNICAL FIELD 
     The disclosure relates in general to a training method for neural network and a memory device using the same, and more particularly to a Ternary Content Addressable Memory (TCAM)-based training method for graph neural network and a memory device using the same. 
     BACKGROUND 
     In the development of Artificial intelligence (AI) technology, in-memory computing has applied for system-on-chip (SoC) designs. In-memory computing can speed up the training and the inference of the AI algorithm. Therefore, in-memory computing becomes an important research direction. 
     However, when training in the memory, huge data movement may cause a drop in speed. Researchers are working to improve the training efficiency of the in-memory computing. 
     SUMMARY 
     The disclosure is directed to a Ternary Content Addressable Memory (TCAM)-based training method for graph neural network and a memory device using the same. In the TCAM-based training method, an adaptive data reusing policy is applied in the sampling step, and a TCAM-based data processing strategy and a dynamic fixed-point formatting approach are applied in an aggregation phase. The data movement can be greatly reduced and accuracy can be kept. The training efficiency of the in-memory computing, especially for the Graph Neural Network, is greatly improved. 
     According to one embodiment, a Ternary Content Addressable Memory (TCAM)-based training method for Graph Neural Network is provided. The TCAM-based training method for the Graph Neural Network includes the following steps. Data are sampled from a dataset. The Graph Neural Network is trained according to the data from the dataset. The step of training the Graph Neural Network includes a feature extraction phase, an aggregation phase and an update phase. In the aggregation phase, one TCAM crossbar matrix stores a plurality of edges corresponding to one vertex and outputs a hit vector for selecting some of the edges, and a Multiply Accumulate (MAC) crossbar matrix stores a plurality of features in the edges for performing a multiply accumulate operation according to the hit vector. 
     According to another embodiment, a memory device. The memory device includes a controller and a memory array. The memory array is connected to the controller. In the memory array, one Ternary Content Addressable Memory (TCAM) crossbar matrix stores a plurality of edges corresponding to one vertex and outputs a hit vector for selecting some of the edges, and a Multiply Accumulate (MAC) crossbar matrix stores a plurality of features in the edges for performing a multiply accumulate operation according to the hit vector. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1    shows an example of a graph applied the Graph Neural Network. 
         FIG.  2    shows a flowchart of a TCAM-based training method for the Graph Neural Network according to one embodiment. 
         FIG.  3    shows an example for executing the step S 110 . 
         FIG.  4    illustrates a feature extraction phase, an aggregation phase and an update phase. 
         FIG.  5    shows a crossbar matrix. 
         FIG.  6    shows a TCAM crossbar matrix and a Multiply Accumulate (MAC) crossbar matrix. 
         FIGS.  7  to  10    illustrate the operation of the TCAM crossbar matrix and the MAC crossbar matrix. 
         FIGS.  11  to  13    illustrate the operation of the TCAM crossbar matrix and the MAC crossbar matrix for several batches. 
         FIG.  14    illustrates a pipeline operation in the TCAM-based data processing strategy. 
         FIG.  15    illustrates a dynamic fixed-point formatting approach. 
         FIG.  16    illustrates the bootstrapping approach. 
         FIG.  17    illustrates a graph partitioning approach. 
         FIG.  18    illustrates a non-uniform bootstrapping approach. 
         FIG.  19    shows a flowchart of an adaptive data reusing policy according to one embodiment. 
         FIG.  20    shows a memory device adopted the TCAM-based training method described above. 
     
    
    
     In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed embodiments. It will be apparent, however, that one or more embodiments may be practiced without these specific details. In other instances, well-known structures and devices are schematically shown in order to simplify the drawing. 
     DETAILED DESCRIPTION 
     In the present embodiment, a Ternary Content Addressable Memory (TCAM)-based training method for Graph Neural Network is provided. Please refer to  FIG.  1   , which shows an example of a graph GP applied the Graph Neural Network. The graph GP may include several vertexes VTi and several nodes Nj. The vertexes VTi and the nodes Nj may be any person, any organization, or any department. The edges among the vertexes VTi and the nodes Nj store the features thereof. The Graph Neural Network may be used to make the inference of the relationship between two of the vertexes VTi. 
     The TCAM-based training method can improve the training efficiency of the in-memory computing. Please refer to  FIG.  2   , which shows a flowchart of the TCAM-based training method for Graph Neural Network according to one embodiment. In step S 110 , sampling data from a dataset  900  is executed. Please refer  FIG.  3   , which shows an example for executing the step S 110 . In  FIG.  3   , several batches BCq will be performed the training step (the step S 110 ) in several iterations. 
     In step S 120 , training the Graph Neural Network according to the data from the dataset  900  is executed. The step S 120  includes a feature extraction phase P 1 , an aggregation phase P 2  and an update phase P 3 . Please refer  FIG.  4   , which illustrates the feature extraction phase P 1 , the aggregation phase P 2  and the update phase P 3 . In the feature extraction phase P 1 , features on the edges and the nodes, are extracted. In the aggregation phase P 2 , several computing, such as Multiply Accumulate is executed. In the update phase P 3 , weightings are updated. The aggregation phase P 2  is an input/output-intensive task, and may incur huge data movement. The training performance bottleneck is occurred at the aggregation phase P 2 . 
     To improve the training efficiency, an adaptive data reusing policy is applied in the step S 110  of sampling data from the dataset  900 , and a TCAM-based data processing strategy and a dynamic fixed-point formatting approach are applied in the aggregation phase P 2 . The following illustrates the TCAM-based data processing strategy and the dynamic fixed-point formatting approach first, then illustrates the adaptive data reusing policy. 
     The TCAM-based data processing strategy applied in the aggregation phase P 2  includes an intra-vertex parallelism architecture and an inter-vertex parallelism architecture. Please refer to  FIG.  5   , which shows a crossbar matrix MX. In the present embodiment, a plurality of features x 11 , x 12 , x 13 , x 21 , x 22 , x 23 , x 31 , x 32 , x 33  can be stored in the crossbar matrix MX. The crossbar matrix MX is, for example, a Resistive random-access memory (ReRAM). The crossbar matrix MX includes a plurality of word lines WL 1 , WL 2 , WL 3 , a plurality of bit lines BT 1 , BT 2 , BT 3  and a plurality of cells. The cells store the features x 11 , x 12 , x 13 , x 21 , x 22 , x 23 , x 31 , x 32 , x 33 , instead of weightings. In the aggregation phase P 2 , a plurality of coefficients a 1 , a 2 , a 3  are inputted to the word lines WL 1 , WL 2 , WL 3  and a plurality of multiply accumulate results v 1 , v 2 , v 3  are obtained from the bit lines BL 1 , BT 2 , BT 3 . 0 or 1 can be used to select any of the nodes X 1 , X 2 , X 3 . As shown in  FIG.  4   , [1, 0, 1] is a hit vector HV used to select the nodes X 1 , X 3 . 
     Please refer to  FIG.  6   , which shows a TCAM crossbar matrix MX 1  and a Multiply Accumulate (MAC) crossbar matrix MX 2 . In the aggregation phase P 2 , the TCAM crossbar matrix MX 1  stores a plurality of edges eg 111 , eg 121 , eg 212 , eg 222 , . . . corresponding to one vertex VT 1  and outputs the hit vector HV for selecting some of the edges eg 111 , eg 121 , eg 212 , eg 222 , . . . . The edge eg 111  includes the source node u 11  and the destination node u 1 . The edge eg 121  includes the source node u 12  and the destination node u 1 . The edge eg 212  includes the source node u 21  and the destination node u 2 . The edge eg 222  includes the source node u 22  and the destination node u 2 . 
     The MAC crossbar matrix MX 2  stores a plurality of features U 11 , U 12 , U 21 , U 22 , . . . in the edges eg 111 , eg 121 , eg 212 , eg 222 , . . . , for performing a multiply accumulate operation according to the hit vector HV under the intra-vertex parallelism architecture. Some examples are provided here via the following drawings. 
     Please refer to  FIGS.  7  to  10   , which illustrate the operation of the TCAM crossbar matrix MX 1  and the MAC crossbar matrix MX 2 . As shown in  FIG.  7   , a search vector SV 1  is inputted to the TCAM crossbar matrix MX 1 . The content of the search vector SV 1  is the destination node u 1 . The destination node u 1  of the edge eg 111  matches the search vector SV 1 , so 1 is outputted. The destination node u 1  of the edge eg 121  matches the search vector SV 1 , so 1 is outputted. The destination node u 2  of the edge eg 212  does not match the search vector SV 1 , so 0 is outputted. The destination node u 2  of the edge eg 222  does not match the search vector SV 1 , so 0 is outputted. Therefore, the hit vector HV 1 , which is “[1, 1, 0, 0]”, is outputted to the MAC crossbar matrix MX 2 . 
     The hit vector HV 1  is inputted to the MAC crossbar matrix MX 2  for selecting the features U 11 , U 12 . As shown in  FIG.  7   , a multiply accumulate result U 1 ( 1 ) is obtained (the multiply accumulate result U 1 ( 1 )=the feature U 11 +the feature U 12 ). 
     As shown in  FIG.  8   , a search vector SV 2  is inputted to the TCAM crossbar matrix MX 1 . The content of the search vector SV 2  is the destination node u 2 . The destination node u 1  of the edge eg 111  does not match the search vector SV 2 , so 0 is outputted. The destination node u 1  of the edge eg 121  does not match the search vector SV 2 , so 0 is outputted. The destination node u 2  of the edge eg 212  matches the search vector SV 2 , so 1 is outputted. The destination node u 2  of the edge eg 222  matches the search vector SV 2 , so 1 is outputted. Therefore, the hit vector HV 2 , which is “[0, 0, 1, 1]”, is outputted to the MAC crossbar matrix MX 2 . 
     The hit vector HV 2  is inputted to the MAC crossbar matrix MX 22  for selecting the features U 21 , U 22 . As shown in  FIG.  8   , a multiply accumulate result U 2 ( 1 ) is obtained (the multiply accumulate result U 2 ( 1 )=the feature U 21 +the feature U 22 ). 
     As shown in  FIG.  9   , a TCAM crossbar matrix MX 21  may further store the vertex VT 1 , . . . , the layer L 0 , L 1 , . . . and the edges eg 11 , eg 21 . The edges eg 111 , eg 121 , eg 212 , eg 222  are stored corresponding the vertex VT 1  and the layer L 0 . The edges eg 11 , eg 21  are stored corresponding to the vertex VT 1  and the layer L 1 . The edges eg 11 , eg 21  are stored corresponding to the vertex VT 1  and the layer L 1 . A search vector SV 3  is inputted to the TCAM crossbar matrix MX 21 . The content of the search vector SV 3  is the vertex VT 1  and the layer L 0 . The vertex VT 1 , the layer L 0  and the edges eg 111 , eg 212  corresponding thereto match the search vector SV 3 , so 1 is outputted. The vertex VT 1 , the layer L 0 , and the edges eg 121 , eg 222  corresponding thereto match the search vector SV 3 , so 1 is outputted. The vertex VT 1 , the layer L 1 , and the edges eg 11  corresponding thereto do not match the search vector SV 3 , so 0 is outputted. The vertex VT 1 , the layer  1 , and the edges eg 21  corresponding thereto do not match the search vector SV 3 , so 0 is outputted. Therefore, the hit vector HV 3 , which is “[1, 1, 0, 0]”, is outputted to the MAC crossbar matrix MX 22 . 
     The hit vector HV 3  is inputted to the MAC crossbar matrix MX 22  for selecting the features U 11 , U 21  and selecting the features U 12 , U 22 . As shown in  FIG.  9   , the multiply accumulate results U 1 ( 1 ), U 2 ( 1 ) are obtained. 
     As shown in  FIG.  10   , the MAC crossbar matrix MX 22  further stores the multiply accumulate results U 1 ( 1 ), U 2 ( 1 ) respectively corresponding to the edges eg 11 , eg 21 . A search vector SV 4  is inputted to the TCAM crossbar matrix MX 21 . The content of the search vector SV 4  is the vertex VT 1  and the layer L 1 . The vertex VT 1 , the layer L 0  and the edges eg 111 , eg 212  corresponding thereto do not match the search vector SV 4 , so 0 is outputted. The vertex VT 1 , the layer L 0 , the edges eg 121 , eg 222  corresponding thereto do not match the search vector SV 4 , so 0 is outputted. The vertex VT 1 , the layer L 1  and the edges eg 11  corresponding thereto match the search vector SV 4 , so 1 is outputted. The vertex VT 1 , the layer L 1  and the edges eg 21  corresponding thereto match the search vector SV 4 , so 1 is outputted. Therefore, the hit vector HV 4 , which is “[0, 0, 1, 1]”, is outputted to the MAC crossbar matrix MX 22 . 
     The hit vector HV 4  is inputted to the MAC crossbar matrix MX 22  for selecting the multiply accumulate result U 1 ( 1 ), U 2 ( 1 ). As shown in  FIG.  10   , a multiply accumulate result is obtained. 
     In one embodiment, the TCAM crossbar matrix MX 21  may further store a plurality of edges corresponding to another one vertex under the inter-vertex parallelism architecture. The search vector can be used to select the particular vertex. 
     Base on above, in the inter-vertex parallelism architecture, the bank/matrix-level parallelism is utilized to aggregate different vertexes. And in the intra-vertex parallelism architecture, the column bandwidth of a crossbar matrix is efficiently utilized to disperse the computation of the aggregation. 
     Please refer to  FIGS.  11  to  13   , which illustrate the operation of the TCAM crossbar matrix MX 311 , MX 312 , . . . and the MAC crossbar matrix MX 321 , MX 322 , . . . for several batches B 1 , B 2 , . . . , Bk. As shown in  FIG.  11   , several TCAM crossbar matrixes MX 311 , MX 312 , . . . and several MAC crossbar matrixes MX 321 , MX 322 , . . . are arranged in several memory banks. For the batch B 1 , the memory area A 3111  is used to store the edge list of the vertex VT 31 , and the memory area A 3211  is used to store the features of the vertex VT 31 . The memory area A 3121  is used to store the edge list of the vertex VT 32 , and the memory area A 3221  is used to store the features of the vertex VT 32 . 
     As shown in  FIG.  12   , for the batch B 2 , the memory area A 3112  is used to store the edge list of the vertex VT 33 , and the memory area A 3212  is used to store the features of the vertex VT 33 . The memory area A 3122  is used to store the edge list of the vertex VT 34 , and the memory area A 3222  is used to store the features of the vertex VT 34 . 
     As shown in  FIG.  13   , for the batch Bk, the memory area A 3111  is used to store the edge list of the vertex VT 35 , and the memory area A 3211  is used to store the features of the vertex VT 35 . The memory area A 3121  is used to store the edge list of the vertex VT 36 , and the memory area A 3221  is used to store the features of the vertex VT 36 . That is to say, the same memory area can be reused for different vertexes. The memory can be efficiently utilized. 
     In one case, the column bandwidth of the MAC crossbar matrix may not enough for store the feature of one node or one vertex. To avoid speed downgrade, a pipeline operation can be applied here. Please refer to  FIG.  14   , which illustrates the pipeline operation in the TCAM-based data processing strategy. As shown in FIG.  FIG.  14   , the feature U 11  is divided into two parts pt 21 , pt 22  and stored in two rows. The edge eg 111  is stored in two rows of the TCAM crossbar matrix MX 41 . The aggregations for the parts pt 21 , pt 22  are independent. At the time T 1 , the aggregation phase P 2  for the part pt 21  is executed; at the time T 2 , the update phase P 3  for the part pt 21  can be started to be executed. At the time T 2 , the aggregation phase P 2  for the part pt 22  is executed; at the time T 3 , the update phase P 3  for the part pt 22  can be started to be executed. 
     The dynamic fixed-point formatting approach is also applied in the aggregation phase P 2 . The weightings or the features stored in the crossbar matrix may have floating-point format. In the present technology, the weightings or the features can be stored in the crossbar matrix via a dynamic fixed-point format. Please refer to  FIG.  15   , which illustrates the dynamic fixed-point formatting approach. As shown in the following table I, the weightings can be represented as the floating-point format. 
     
       
         
           
               
               
               
               
               
             
               
                   
                 TABLE I 
               
               
                   
                   
               
               
                   
                 weightings 
                 floating-point format 
                 mantissa 
                 exponent 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 0.2165 
                 1.10111011 × 2{circumflex over ( )}-3 
                 10111011 
                 2{circumflex over ( )}-3 
               
               
                   
                 0.214 
                 1.10110110 × 2{circumflex over ( )}-3 
                 10110110 
                 2{circumflex over ( )}-3 
               
               
                   
                 0.202 
                 1.10011101 × 2{circumflex over ( )}-3 
                 10011101 
                 2{circumflex over ( )}-3 
               
               
                   
                 0.0096 
                 1.00111010 × 2{circumflex over ( )}-7 
                 00111010 
                 2{circumflex over ( )}-7 
               
               
                   
                 0.472 
                 1.11100011 × 2{circumflex over ( )}-2 
                 11100011 
                 2{circumflex over ( )}-2 
               
               
                   
                   
               
            
           
         
       
     
     The exponent range is from 2{circumflex over ( )}-0 to 2{circumflex over ( )}-7. In this embodiment, the exponent range can be classified into two groups G 0 , G 1 . The group G 0  is from 2{circumflex over ( )}-0 to 2{circumflex over ( )}-3, and the group G 1  is from 2{circumflex over ( )}-4 to 2{circumflex over ( )}-7. As shown in  FIG.  15   , if the exponent of the data is within the group G 0 , “0” is stored; if the exponent of the data is within the group G 1 , “1” is stored. For precisely representing “2-0”, the mantissa is shifted by 0 bit. For precisely representing “2{circumflex over ( )}-1”, the mantissa is shifted by 1 bit. For precisely representing “2{circumflex over ( )}-2”, the mantissa is shifted by 2 bits. For precisely representing “2{circumflex over ( )}-3”, the mantissa is shifted by 3 bits. For precisely representing “2{circumflex over ( )}-4”, the mantissa is shifted by 0 bit. For precisely representing “2{circumflex over ( )}-5”, the mantissa is shifted by 1 bit. For precisely representing “2{circumflex over ( )}-6”, the mantissa is shifted by 2 bits. For precisely representing “2{circumflex over ( )}-7”, the mantissa is shifted by 3 bits. For example, the weighting wt 1  is “0.2165”, the mantissa “0.2165” is “10111011”, the last bit is “0” to represent the group G 0 , and the mantissa “10111011” is shifted by 3 bits to precisely representing “2{circumflex over ( )}-3.” The weighting wt 2  is “0.472”, the mantissa “0.472” is “11100011”, the last bit is “0” to represent the group G 0 , and the mantissa “11100011” is shifted by 2 bits to precisely representing “2{circumflex over ( )}-2.” 
     According to the dynamic fixed-point formatting approach, the 7 exponents are classified into only two groups G 0  and G 1 , so the computing cycle can be reduced from 7 to 2, the computing speed can be greatly increased. 
     Furthermore, the adaptive data reusing policy applied for the step S 110  of sampling data from the dataset  900  is illustrated as below. The adaptive data reusing policy includes a bootstrapping approach, a graph partitioning approach and a non-uniform bootstrapping approach. 
     Please refer to  FIG.  16   , which illustrates the bootstrapping approach. Each of batches BC 1 , BC 2 , BC 3 , BC 4  is used to execute one iteration. The batch BC 1  includes the data of the nodes N 1 , N 2 , N 5 ; the batch BC 2  includes the data of the nodes N 1 , N 3 , N 6 ; the batch BC 3  includes the data of the nodes N 5 , N 3 , N 6 ; the batch BC 4  includes the data of the nodes N 4 , N 3 , N 2 . The data of the node N 1  is repeated within the batches BC 1  and the batch BC 2 . The data of the node N 3  is repeated within the batches BC 3  and the batch BC 4 . 
     According to the bootstrapping approach, some data is repeated within two batches, so the data movement can be greatly reduced. The training performance can be improved. 
     Please refer to  FIG.  17   , which illustrates the graph partitioning approach. In a graph, the graph size (number of all of the nodes) is n and the batch size (number of the nodes in one batch) is b. The reusing rate is b/n. If the reusing rate is too low, the bootstrapping approach may not cause a great improvement, the graph is needed to be partitioned for increasing the reusing rate. As shown in  FIG.  17   , the nodes in the graph are randomly segmented into 3 partitions. The reusing rate will be increased 3 times. The data of the nodes N 11  to N 14  are arranged in the batches BC 11  to BC 13 . The data of the nodes N 12 , N 14  are repeated within the batches BC 11  and the batch BC 12 . The data of the nodes N 13 , N 14  are repeated within the batches BC 12  and the batch BC 13 . 
     The data of the nodes N 21  to N 25  are arranged in the batches BC 21  to BC 23 . The data of the nodes N 23 , N 25  are repeated within the batches BC 21  and the batch BC 22 . The data of the node N 21  is repeated within the batches BC 22  and the batch BC 23 . 
     According to the graph partitioning approach, the reusing rate is increased and the bootstrapping approach still has a great improvement even if the graph is large. 
     Please refer to  FIG.  18   , which illustrates the non-uniform bootstrapping approach. In the bootstrapping approach, data of some of the nodes are repeatedly sampled, so some of the nodes may be sampled too much times and the accuracy may be affected. As shown in  FIG.  18   , sampling probabilities of the nodes are non-uniform. After some times of iteration, the sampling times of the node N 8  is above out of a boundary, so the sampling probability of the node N 8  is reduced to be 0.826% which is lower than the sampling probability of the other nodes. 
     According to the non-uniform bootstrapping approach, any node may not be sampled too much times and the accuracy can be kept. 
     The adaptive data reusing policy including the bootstrapping approach, the graph partitioning approach and the non-uniform bootstrapping approach can be executed via the following flowchart. Please refer to  FIG.  19   , which shows a flowchart of the adaptive data reusing policy according to one embodiment. In step S 111 , whether the reusing rate is lower than a predetermined value is determined. If the reusing rate is lower than the predetermined value, then the process proceeds to step S 112 ; if the reusing rate is not lower than the predetermined value, then the process proceeds to step S 113 . 
     In the step S 112 , the graph partitioning approach is executed. 
     In the step S 113 , whether the sampling time of any node is out of the boundary is determined. If the sampling time of any node is out of the boundary, the process proceeds to step S 114 ; if the sampling times of all of the nodes are not out of the boundary, the process proceeds to step S 115 . 
     In the step S 114 , the non-uniform bootstrapping approach is executed. 
     In the step S 115 , the (uniform) bootstrapping approach executed. 
     Moreover, please refer to  FIG.  20   , which shows a memory device  1000  adopted the training method described above. The memory device  1000  includes a controller  100  and a memory array  200 . The memory array  200  is connected to the controller  100 . The memory array  200  includes at least one TCAM crossbar matrix MXm 1  and at least one MAC crossbar matrix MXm 2 . The TCAM crossbar matrix MXm 1  stores the edges egij corresponding to one vertex. The TCAM crossbar matrix MXm 1  receives a search vector SVt, and then outputs a hit vector HVt for selecting some of the edges egij. The MAC crossbar matrix MXm 2  stores a plurality of features in the edges egij for performing the multiply accumulate operation according to the hit vector HVt. 
     According to the embodiments described above, in the TCAM-based training method for Graph Neural Network, the adaptive data reusing policy is applied in the sampling step (step S 110 ), and the TCAM-based data processing strategy and the dynamic fixed-point formatting approach are applied in the aggregation phase P 2 . The data movement can be greatly reduced and accuracy can be kept. The training efficiency of the in-memory computing, especially for the Graph Neural Network, is greatly improved. 
     It will be apparent to those skilled in the art that various modifications and variations can be made to the disclosed embodiments. It is intended that the specification and examples be considered as exemplary only, with a true scope of the disclosure being indicated by the following claims and their equivalents.