Methods and apparatuses for searching data stored in a memory array using a replicated data pattern
View Patent ↗A method includes replicating a data pattern to be searched for, storing the replicated data pattern into a first row of memory cells, and comparing the replicated data pattern to data stored into a second row of memory cells. In response to detecting the data pattern in the data stored into the second row of memory cells, storing into a third row a value indicative of at least one of an occurrence of the data pattern or a position of the searched for data pattern in the data stored into the row of memory cells.
1. A method, comprising:
replicating a data pattern to be searched for across a first row of memory cells;
comparing the first row of memory cells including the replicated data pattern to data stored into a second row of memory cells; and
responsive to detecting the data pattern in the data stored into the second row of memory cells, storing into a third row a value indicative of at least one of an occurrence of the data pattern or a position of the searched for data pattern in the data stored into the second row of memory cells.
2. The method of claim 1 , comprising storing a data pattern into the second row of memory cells as the data stored into the second row of memory cells.
3. The method of claim 1 , wherein detecting the data pattern in the data stored into the second row comprises comparing a number of digits of the searched for data pattern to a number of digits of the data stored into the second row of memory cells.
4. The method of claim 3 , wherein, when a number of digits of the data pattern is not equal to a length value of 1:
performing a for-loop according to a length value of the data pattern;
storing values of the data stored into the row of memory cells into a row of accumulators; and
performing a logical rotation of the values stored into the row of accumulators to compare the data pattern to the data stored into the row of memory cells.
5. The method of claim 4 , comprising performing a logical shift operation of the row of accumulators by a number of digits to align digits indicating a match between the data pattern and the data stored into the row of memory cells.
6. The method of claim 5 , comprising performing a logical operation based at least in part on a result of the logical shift operation, wherein performing the logical operation comprises storing the value indicative of a first occurrence of the data pattern in the data stored into the row of memory cells.
7. A processor-in-memory (PIM) device, comprising:
a plurality of memory cells; and
a processing structure communicatively coupled to the plurality of memory cells, wherein the PIM device is configured to:
replicate a data pattern to be searched for into a first row of the plurality of memory cells;
compare the first row of the plurality of memory cells that includes the replicated data pattern to data stored into a second row of the plurality of memory cells; and
responsive to detecting the data pattern in the data stored into the second row of the plurality of memory cells, store into a third row of the plurality of memory cells a value indicative of at least one of an occurrence of the data pattern or a position of the data pattern in the data stored into the second row of the plurality memory cells.
8. The PIM device of claim 7 , wherein the data stored into the row of the plurality of rows of memory cells comprise at least a portion of an email, a text message, a text document, a text file, a text string, a script file, a compressed file, a webpage, or any combination thereof.
9. The PIM device of claim 7 , wherein the PIM device being configured to compare the replicated data pattern to the data stored into the second row comprises the PIM device being configured to compare a number of digits of the replicated data pattern to a number of digits of the data stored into the second row of the plurality of memory cells.
10. The PIM device of claim 7 , wherein the PIM device is configured to compare a number of digits of the searched for data pattern to a length value of 1 before storing the value indicative of the at least one of the occurrence or the position of the searched for data pattern in the data stored into the second row of the plurality memory cells.
11. The PIM device of claim 10 , wherein the length of the data stored into the second row of the plurality of rows of memory cells comprises a length of approximately 2 kilobytes (kB) or less.
12. The PIM device of claim 10 , wherein the length of the data stored into the second row of the plurality of rows of memory cells comprises a length of approximately 2 kilobytes (kB) or more.
13. The PIM device of claim 7 , wherein the PIM device is configured to compare the replicated data pattern to data stored into the second row of the plurality of memory cells a number of times equal to a length of the data pattern.
14. A non-transitory computer-readable medium having computer executable code stored thereon, the code comprising instructions to:
store a data pattern into a first row of a plurality of memory cells of the PIM device;
replicate a data pattern to be searched for across the first row of the plurality of memory cells;
storing the replicated data pattern into a second row of the plurality of memory cells;
execute, via the PIM device, a comparison of replicated data pattern stored into the second row of memory cells and the data pattern stored into the first row of memory cells; and
responsive to detecting the data pattern in the data pattern stored into the first row of memory cells, store into a third row of memory cells a value indicative of at least one of an occurrence of the data pattern or a position of the data pattern in the data pattern stored into the first row of memory cells.
15. The non-transitory computer-readable medium of claim 14 , comprising instructions to:
execute a comparison of digits of the data pattern to digits of the data pattern stored into the first row of memory cells; and
store into the third row of memory cells the value indicative of the at least one of the occurrence or the position of the replicated data pattern when the digits of the replicated data pattern is detected in the digits of the data pattern stored into the first row of memory cells.
16. The non-transitory computer-readable medium of claim 14 , comprising:
executing a comparison of a number of digits of the replicated data pattern to a length value of 1; and
storing into the third row of memory cells the value indicative of the at least one of the occurrence or the position of the replicated data pattern when the number of digits of the replicated data pattern is equal a length value of 1.
17. The non-transitory computer-readable medium of claim 16 , wherein, when the number of digits of the replicated data pattern is not equal to the length value of 1, the code comprises instructions to:
perform a for-loop according to a length of the replicated data pattern;
store values of the data pattern into a row of accumulators; and
perform a bitwise logical rotation of the values stored into the row of accumulators to iteratively compare the replicated data pattern stored into the second row of memory cells and the data pattern stored into the first row of memory cells.
18. The non-transitory computer-readable medium of claim 17 , comprising instructions to perform a logical shift operation of the row of accumulators by a number of digits to align digits indicating a match between the replicated data pattern stored into the second row of memory cells and the data pattern stored into the first row of memory cells.
19. The non-transitory computer-readable medium of claim 18 , comprising instructions to perform a bitwise logical operation based at least in part on a result of the logical shift operation, wherein performing the bitwise logical operation comprises storing the value indicative of a first occurrence of the replicated data pattern in the first row of memory cells.
20. The non-transitory computer-readable medium of claim 14 , comprising instructions to store into the third row of memory cells a value indicative of the first occurrence of the data pattern and the position of the data pattern in response to detecting the data pattern in the data pattern stored into the first row of memory cells.