Patent Publication Number: US-2023145303-A1

Title: Memory device and operation method thereof

Description:
BACKGROUND OF THE INVENTION 
     Field of the Invention 
     The invention relates to a memory device and an operation method thereof. 
     Description of the Related Art 
     Finite state machine (FSM) is a calculation model that could be used to simulate sequential logic circuit and computer program. FSM could be implemented by software or hardware. 
     FSM could generate regular language. Regular expression matching is generally implemented with FSM, and could be applied to establish model in the fields such as mathematics, artificial intelligence, games, and linguistics. 
     When implementing regular expression matching and FSM with hardware, not only computing efficiency must be considered, but also space efficiency must be considered. In view of this, a hardware implementation with both computational efficiency and space efficiency is an important research topic. 
     SUMMARY OF THE INVENTION 
     An embodiment of the present invention discloses a memory device, comprising a first driver circuit, a second driver circuit, an in-memory-searching (IMS) array, a sensing circuitry, a working memory and a buffer. The IMS array comprises a plurality of memory cells. The memory cells are coupled to the first driver circuit via a plurality of first signal lines, and coupled to the second driver circuit via a plurality of third signal lines. The memory cells are configured to store a plurality of first strings of a plurality of string pairs generated according to a finite state machine (FSM). The sensing circuitry is coupled to the IMS array. The sensing circuitry comprises a plurality of sensing units coupled to the memory cells via a plurality of second signal lines. The working memory is coupled to the sensing circuitry. The working memory having a plurality of memory addresses one-to-one corresponding to the sensing units, and configured to store a plurality of second strings of the string pairs. The buffer is coupled to the working memory and the first driver circuit. The buffer configured to store a string representing a starting state of the FSM while the FSM is initialized. 
     Another embodiment of the present invention discloses an operation method of memory device, comprising: programming a plurality of first strings of a plurality of string pairs representing a finite state machine (FSM) to an in-memory-searching (IMS) array of a memory device; programming a plurality of second strings of the string pairs to a working memory of the memory device; and programming a string representing a starting state of the FSM to a buffer of the memory device. 
     The above and other aspects of the invention will become better understood with regard to the following detailed description of the preferred but non-limiting embodiment(s). The following description is made with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1 A  shows a block diagram of a memory device according to an embodiment of the present invention. 
         FIG.  1 B  shows a block diagram of a memory device according to another embodiment of the present invention. 
         FIG.  2    shows a finite state machine. 
         FIG.  3    shows a flowchart of an operation method of memory device according to an embodiment of the present invention. 
         FIG.  4    shows a flowchart of an operation method of memory device according to another embodiment of the present invention. 
         FIGS.  5 A- 5 C  show schematic diagrams of operation of memory-based FSM according to an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to  FIG.  1 A ,  FIG.  1 A  shows a block diagram of a memory device according to an embodiment of the present invention. A memory device  10   a  includes a first driver circuit  102 , a second driver circuit  103 , an in-memory-searching (IMS) array  104   a , a sensing circuitry  105 , a working memory  106 , a buffer  107  and a memory controller  108 . 
     The IMS array  104   a  includes a number of memory cells C 11 ˜Cmn, a number sets of first signal lines SRL 1 - 1 , SRL 1 - 2 ˜SRLm- 1 , SRLm- 2 , a number of second signal lines ML 1 ˜MLn and a number of third signal lines SL 1 ˜SLn. Each of the memory cells Cij is coupled to the first driver circuit  102  via a corresponding first signal line set SRLi- 1 , SRLi- 2 . and a corresponding bit line BLj, wherein i is an integer not smaller than 1 and not greater than m. A number of memory cells C 1   j ˜Cmj form a memory cell string. Each of the memory cell strings is coupled to the sensing circuit  105  via a corresponding second signal line MLj, and coupled to the second driver circuit  103  via a corresponding third signal line SLj, wherein j is an integer not smaller than 1 and not greater than n. in this embodiment, the IMS array  104   a  is a NOR type non-volatile memory. Each memory cell Cij could include two transistors, where the gates of the two transistors are respectively coupled to the first signal lines SRLi- 1 , SRLi- 2 . The transistors could be MOSFET, FeFET, or any type that is practicable. This architecture is called ternary content addressable memory (TCAM). By programming the combination of threshold voltages of the two transistors of the memory cell, the memory cells C 11 ˜Cmn could be programed to store 0 and 1, or further to store 0, 1 and don&#39;t care, wherein don&#39;t care would be matched whether 0 or 1 is searched. For brevity, “programming the memory cells on a specific second/third signal line” would be simplified to “programming a specific second/third signal line”, and “a data string stored in the memory cells on a specific second/third signal line” would be simplified to “a data string of a specific second/third signal line”. 
     The sensing circuitry  105  is coupled to the IMS array  104   a . The sensing circuitry  105  includes a number of sensing units SA 1 ˜SAn. In this embodiment, the sensing units SA 1 ˜SAn are one-to-one coupled to the second signal lines ML 1 ˜MLn. The sensing unit is configured to output a signal according to the magnitude of a current sensed from the coupled second signal line, wherein the signal output by the sensing unit represents whether the data string of the second signal line coupled to the sensing unit is matched with the data string to be searched. in an embodiment, when the current sensed from the second signal line coupled to the sensing unit is greater than the predetermined threshold, it could be determined that the data string of the second signal line coupled to the sensing unit is matched with the data string to be searched. 
     The working memory  106  is coupled to the sensing circuitry  105 . The working memory  106  could be volatile memory or non-volatile memory. The working memory  106  includes a number of memory addresses. In an embodiment, the memory addresses could one-to-one correspond to the sensing units of the sensing circuitry. The buffer  107  is coupled to the working memory  106  and the first driver circuit  102 . 
     The memory controller  108  could be coupled to the first driver circuit  102 , the second driver circuit  103 , the sensing circuitry  105 , the working memory  106  and the buffer  107 , and configured to control the first driver circuit  102 , the second driver circuit  103 , the sensing circuitry  105 , the working memory  106  and the buffer  107  by signals. 
     Referring to  FIG.  1 B ,  FIG.  1 B  shows a memory device according to another embodiment of the present invention. The memory device  10   b  is similar to the memory device  10   a  in architecture. The difference is the IMS array  104   b  is different from the IMS array  104   a . In this embodiment, the IMS array  104   b  is a NAND-type non-volatile memory. Each of the memory cells includes two transistors serial connected. A number of the memory cells are serial connected between a second signal line and a third signal line to form a memory cell string for storing a data string. 
     In order to illustrate how the memory device  10   a  and  10   b  could implement a finite state machine (FSM), an exemplary FSM would be taken for illustration. 
     Referring to  FIG.  2   ,  FIG.  2    shows a block diagram of a FSM. The FSM 2 includes four states q1˜q4, wherein q1 is the starting state, and q1 is also the accepting state, a, b are inputs. According to the regular expression of the FSM 2, a number of state transition cases of the FSM 2 are shown in Table 1. Table 1 shows eight state transition cases of the FSM 2, including: for the current state is q1, if the input is a, the next state is q2, and if the current input is b the next state is q3; for the current state is q2, if the current input is a, the next state is q4, and if the current input is b the next state is q1; for the current state is q3, if the current input is a, the next state is q1, and if the current input is b, the next state is q4; for the current state is q4, if the current input is a, the next state is q4, and if the current input is b, the next state is q4. Noted that since transferring the FSM to regular expression is well known by a person having ordinary skill in the art, it would not be described herein. 
     
       
         
           
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 current state 
                 current input 
                 next state 
               
               
                   
               
             
            
               
                 q1 
                 a 
                 q2 
               
               
                 q1 
                 b 
                 q3 
               
               
                 q2 
                 a 
                 q4 
               
               
                 q2 
                 b 
                 q1 
               
               
                 q3 
                 a 
                 q1 
               
               
                 q3 
                 b 
                 q4 
               
               
                 q4 
                 a 
                 q4 
               
               
                 q4 
                 b 
                 q4 
               
               
                   
               
            
           
         
       
     
     Next, the states q1˜q4 and the allowable input a, b of the FSM 2 would be encoded. In an embodiment, q1 is encoded as 00, q2 is encoded as 01, q3 is encoded as 10, q4 is encoded as 11, a is encoded as 0001, and b is encoded as 0010. After encoding, Table 1 could be transferred to  FIG.  2   . 
     
       
         
           
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 current state 
                 current input 
                 next state 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                 00 
                 0001 
                 01 
               
               
                 00 
                 0010 
                 10 
               
               
                 01 
                 0001 
                 11 
               
               
                 01 
                 0010 
                 00 
               
               
                 10 
                 0001 
                 00 
               
               
                 10 
                 0010 
                 11 
               
               
                 11 
                 0001 
                 11 
               
               
                 11 
                 0010 
                 11 
               
               
                   
               
            
           
         
       
     
     According to the encoded states, the encoded allowable inputs, and the state transition cases, a number of string pairs would be generated, wherein the string pairs one-to-one correspond to the state transition cases, and each of the string pairs includes a first string and a second string. The first string includes the encoded current state and the encoded current input. The second string includes the encoded next state. For example, the state transition case “if the current state is q1 (00) and the current input is a (0001), the next state is q2 (01)” corresponds to a string pair [000001,01], the state transition case “if the current state is q1 (00) and the current input is b (0010), the next state is q3 (10)” corresponds to a string pair [000010,10], and so on. That is, for each of the string pairs, in the first string, a first portion codewords represents the current state, and a second portion codeswords represents the current input, and the second string represents the next state corresponding to the current state and the current input. Table 3 shows an example of the string pairs of the FSM 2. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 3 
               
               
                   
                   
               
               
                   
                 first string 
                 second string 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 000001 
                 01 
               
               
                   
                 000010 
                 10 
               
               
                   
                 010010 
                 00 
               
               
                   
                 100001 
                 00 
               
               
                   
                 100010 
                 11 
               
               
                   
                 110001 
                 11 
               
               
                   
                 X10010 
                 11 
               
               
                   
                   
               
            
           
         
       
     
     Referring to  FIG.  3   ,  FIG.  3    shows a flowchart of an operation method of memory device according to an embodiment of the present invention. After the encoding and obtaining of the string pairs, FSM could be establish on the memory device  10   a  (or  10   b ) by using the operation method shown in  FIG.  3   . 
     At S 301 , the IMS array  104   a / 104   b  would be programmed according to the first strings of the string pairs. The architecture of the memory device  10   a  is taken as the example. It is assumed that m is 6, and n is 8. The memory controller  108  commands the first driver circuit  102  and the second driver circuit  103  to apply suitable programming voltages (depends on the actual hardware specification) to one-to-one program the first strings to different third signal lines. For example, the first string 000001 of the string pair corresponding to “if the current state is q1 and the current input is a, the next state is q2” could be programmed to the memory cells C 11 ˜C 61  on the third signal line SL 1 , the first string 000010 of the string pair corresponding to “if the current state is q1 and the current input is b, the next state is q3” could be programmed to the memory cells C 12 ˜C 62  on the third signal line SL 2 , and so on. 
     At S 303 , the working memory  106  would be programmed according to the second strings of the string pairs. Taking the memory device  10   a  as the example, the second string 01 of the string pair corresponding to “if the current state is q1 and the current input is a, the next state is q2” could be programmed to a memory address corresponding to the third signal line ML 1  (the sensing unit SA 1 ), the second string 10 of the string pair corresponding to “if the current state is q1 and the current input is b, the next state is q3” could be programmed to a memory address corresponding to the third signal line ML 2  (the sensing unit SA 2 ), and so on. 
     At S 305 , a string corresponding to the starting state of the FSM would be stored to the buffer. Step S 305  is performed for initialize the FSM established by steps S 301  and S 305 . 
     Referring to  FIG.  4   ,  FIG.  4    shows a flowchart of an operation method of memory device according to another embodiment of the present invention. The process in  FIG.  4    could be continued after the process in  FIG.  3   . With the process in  FIG.  4   , the operation of the FSM could be realized. 
     At S 401 , the memory controller receives an input string. The input string is obtained by encoding an input to be input to the FSM. As in the previous example, when the input is a, the input string is 0001, and when the input is b, the input string is 0010. 
     At S 403 , the memory controller, based on a clock signal, commands the first driver circuit  102  to apply a number of first searching voltage to the IMS array  104   a / 104   b  according to the input string. For example, it is assumed that the input is a. During a first clock cycle of the clock signal, the memory controller  108  commands, according to the input string 0001 which represents a, the first driver circuit  102  to apply the first searching voltage corresponding to 0 to the first signal line set SRL 3 - 1 , SRL 3 - 2 , apply the first searching voltage corresponding to 0 to the first signal line set SRL 4 - 1 , SRL 4 - 2 , apply the first searching voltage corresponding to 0 to the first signal line set SRL 5 - 1 , SRL 5 - 2 , and apply the first searching voltage corresponding to 1 to the first signal line set SRL 6 - 1 , SRL 6 - 2 . 
     At S 405 , the first driver circuit  102 , based on the clock signal, applies a number of second searching voltage to the IMS array  104   a / 104   b  according to the string stored in the buffer  107 . Continuing the previous example, during the first clock cycle, the string 00 representing the starting state q1 is stored in the buffer  107 . Therefore, the word line driver  102  applies the second searching voltage corresponding to 0 to the first signal line set SRL 1 - 1 , SRL 1 - 2 , and applies the second searching voltage corresponding to 0 to the first signal line set SRL 2 - 1 , SRL 2 - 2 . 
     At S 407 , the sensing circuitry  105  obtains a sensing result by sensing a number of currents from the IMS array  104   a / 104   b , and triggers the working memory  106  to output the second string stored in a memory address corresponding to the sensing result to the buffer  107 . In an embodiment, the sensing result indicates which of the sensing units in the sensing circuitry  105  has detected a current greater than the predetermined threshold. Based on the sensing result, it could be determined that which of data string on the third signal lines is matched. Continuing the previous example, the searching voltages applied to the first signal line SRL 1 ˜SRL 6  representing the data string to be searched is 000001. The data string of the third signal line SL 1  matches 000001. Therefore, a current greater than the predetermined threshold could pass through the memory cells C 11 ˜C 16 , and sensed by the sensing unit SA 1 . The data strings of the third signal lines SL 2 ˜SL 8  do not match 000001. Therefore, no current greater than the predetermined threshold could be sensed by the sensing units SA 2 ˜SA 8 . Based on the sensing result, the sensing circuitry  105  would output a signal to cause the working memory  106  to output the second string 01 stored in the memory address corresponding to the sensing unit SA 1  to buffer  107 . The original string 00 stored in the buffer would be overwritten by the string 01 which is output by the working memory  106 . This step is equivalent to transfer the current state from q1 to q2. 
     In practical applications, the input to FSM may be a sequence of inputs. That is, a number of inputs with a specific order would be input to FSM. For such an input sequence, steps S 401 ˜S 407  would be performed repeatedly. I it would be illustrated with an example and  FIGS.  5 A ˜ 5 C hereafter. In  FIGS.  5 A ˜ 5 C, the field “first string” represents the first string stored on multiple different second signal lines (such as ML 1 ˜ML 8 ), the field “second string” represents the second strings stored in the memory addresses of the working memory  106  corresponding to the multiple second signal lines, the current state represents the data string currently stored in the buffer  107 , and the current input represents the input of the current input sequence to be currently executed. It is assuming that an input sequence is a, a, b, a, b. The corresponding input string sequence would be 0001, 0001, 0010, 0001, 0010. Referring to the left part of  FIG.  5 A , during a first clock cycle of the clock signal, the buffer  107  stores the starting state 00 (q1), the first driver circuit  102  applies the searching voltages corresponding to 000001 (the combination of 00 representing the current state and 0001 representing the current input, the following could be deduced by analogy) to the first signal line sets SRL 1 - 1 , SRL 1 - 2 ˜SRL 6 - 1 , SRL 6 - 2 , the sensing circuitry  105  detects the current greater that the predetermined threshold from the second signal line ML 1  (000001 matched) and cause the working memory  106  to output the second string 01 (q2) stored in the memory address corresponding to the third signal line SL 1  to the buffer  107  for overwriting 00 (q1). Referring to the right part of  FIG.  5 A , during a second clock cycle of the clock signal, the buffer  107  stores the current state 01 (q2), the first driver circuit  102  applies the searching voltages corresponding to 010001 (the combination of 01 and 0001) to the first signal line sets SRL 1 - 1 , SRL 1 - 2 ˜SRL 6 - 1 , SRL 6 - 2 , the sensing circuitry  105  detects the current greater that the predetermined threshold from the second signal line ML 3  (010001 matched) and cause the working memory  106  to output the second string 11 (q4) stored in the memory address corresponding to the third signal line SL 3  to the buffer  107  for overwriting 01 (q2). Referring to the left part of  FIG.  5 B , during a third clock cycle of the clock signal, the buffer  107  stores the current state 11 (q4), the first driver circuit  102  applies the searching voltages corresponding to 110010 (the combination of 11 and 0010) to the first signal line sets SRL 1 - 1 , SRL 1 - 2 ˜SRL 6 - 1 , SRL 6 - 2 , the sensing circuitry  105  detects the current greater that the predetermined threshold from the second signal line ML 8  (110010 matched) and cause the working memory  106  to output the second string 11 (q4) stored in the memory address corresponding to the third signal line SL 8  to the buffer  107  for overwriting 11 (q4). Referring to the right part of  FIG.  5 B , during a fourth clock cycle of the clock signal, the buffer  107  stores the current state 11 (q4), the first driver circuit  102  applies the searching voltages corresponding to 110001 (the combination of 11 and 0001) to the first signal line sets SRL 1 - 1 , SRL 1 - 2 ˜SRL 6 - 1 , SRL 6 - 2 , the sensing circuitry  105  detects the current greater that the predetermined threshold from the second signal line ML 7  (110001 matched) and cause the working memory  106  to output the second string 11 (q4) stored in the memory address corresponding to the third signal line SL 7  to the buffer  107  for overwriting 11 (q4). Referring to  FIG.  5 C , during a fifth clock cycle of the clock signal, the buffer  107  stores the current state 11 (q4), the first driver circuit  102  applies the searching voltages corresponding to 110010 (the combination of 11 and 0010) to the first signal line sets SRL 1 - 1 , SRL 1 - 2 ˜SRL 6 - 1 , SRL 6 - 2 , the sensing circuitry  105  detects the current greater that the predetermined threshold from the second signal line ML 8  (110010 matched) and cause the working memory  106  to output the second string 11 (q4) stored in the memory address corresponding to the third signal line SL 8  to the buffer  107  for overwriting 11 (q4). 
     After performing steps S 401 ˜S 407  for each input of the input sequence, it could be determined that whether the input sequence is accepted by the FSM according to the string stored in the buffer  107 . While the state represented by the string finally stored in the buffer  107  is same as the accepting state, it could be determined that the input sequence is accepted by the FSM. For example, the string finally stored in the buffer  107  is not 00 which represents the accepting state q1, but 11 which represents q4. Therefore, it could be determined that the input sequence a, a, b, a, b would not be accepted by the FSM 2, as shown in the lower right corner of  FIG.  5 C . The determination could be made by the memory controller  108 , or a specific purpose circuitry (not shown). 
     Noted that in the processes described above, the second driver circuit  103  would be controlled by the memory controller  108  to apply suitable bias voltage at correct timing to allow the operation of in-memory-searching to be performed. “Correct timing” and “suitable bias voltage” depend on the actual specification of the memory device. 
     In order to improve the space efficiency of the IMS array, the string pairs could be integrated. When integrating, the different bit(s) of the first string of at least two of string pairs with the same second string would be replaced by don&#39;t care. For example, Table 4 could be generated after integration is performed for Table 3. 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 4 
               
               
                   
                   
               
               
                   
                 first string 
                 second string 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 000001 
                 01 
               
               
                   
                 000010 
                 10 
               
               
                   
                 010001 
                 11 
               
               
                   
                 010010 
                 00 
               
               
                   
                 100001 
                 00 
               
               
                   
                 1X0010 
                 11 
               
               
                   
                 110001 
                 11 
               
               
                   
                   
               
            
           
         
       
     
     In Table 4, X represents don&#39;t care. In order to program the first strings of the string pairs in Table 4, the IMS array is required to have the memory cells that support the programming of don&#39;t care. 
     While the invention has been described by way of example and in terms of the preferred embodiment (s), it is to be understood that the invention is not limited thereto. On the contrary, it is intended to cover various modifications and similar arrangements and procedures, and the scope of the appended claims therefore should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements and procedures.