Cache prefetch for deterministic finite automaton instructions
View Patent ↗In a DFA scanning engine used to match regular expressions or similar rules, instructions to execute DFA state transitions are accessed through an instruction cache. Each DFA instruction may indicate varying numbers of transitions or branches from a current state. The cache pre-fetches a requested number of additional instructions consecutively following an accessed instruction. The DFA engine accesses an instruction from the cache corresponding to a state within a small number of transitions from the root state. When a low-branching instruction is executed to access a next instruction from the root state, or when a low-branching instruction is executed to access a next instruction from the cache, a fixed or configurable pre-fetch length is requested. Some instructions such as low-branching instructions may contain a pre-fetch hint.
1. A method of pre-fetching instructions to an instruction cache for a Deterministic Finite Automaton (DFA) engine during a DFA descent, said DFA descent comprising a transition depth and a branching value, said method comprising:
accessing an instruction from an instruction cache; and
pre-fetching a number of instructions immediately following the accessed instruction to the instruction cache, wherein the number of instructions is selected based on at least one of the transition depth or the branching value.
2. The method of claim 1 , wherein the number of instructions is selected based on the transition depth.
3. The method of claim 2 , wherein said selection is by comparing the transition depth with a threshold value and selecting the number of instructions to be zero only if the transition depth is less than the threshold.
4. The method of claim 1 , wherein the number of instructions is based on the branching value.
5. The method of claim 4 , wherein the number of instructions is determined by comparing the branching value to a threshold and pre-fetching zero instructions only if the branching value is greater than the threshold.
6. The method of claim 1 , wherein the number of instructions is based on the transition depth and the branching value.
7. The method of claim 1 , wherein at least one instruction contains a pre-fetch hint, and if an executed previous instruction contains a pre-fetch hint, the number of instructions selected is based on the contained hint.
8. The method of claim 7 , wherein if the previous instruction does not contain a hint, the number of instructions is zero.
9. The method of claim 7 , wherein if the previous instruction does not contain a hint, the number of instructions is a predetermined value.
10. The method of claim 7 , wherein if the previous instruction does not contain a hint, the number of instructions is based on the transition depth.
11. The method of claim 10 , wherein the number of instructions is selectable by comparing the transition depth with a threshold value and a selected number of instructions is zero only if the transition depth is less than the threshold.
12. The method of claim 7 , wherein if the previous instruction does not contain a hint, the number of instructions is based on the branching value.
13. The method of claim 12 , wherein the number of instructions is determined by comparing the branching value to a threshold and pre-fetching zero instruction only if the branching value is greater than the threshold.
14. A system of pre-fetching instructions into an instruction cache for use in a Deterministic Finite Automaton (DFA) engine, said system comprising:
an instruction cache enabled to fetch instructions from an external memory; and
a DFA engine enabled to access instructions from the instruction cache, and to execute said instructions and to request pre-fetch of instructions to the instruction cache based on an algorithm, wherein the algorithm is based on at least one of a transition depth of a DFA descent or a branching value of the DFA descent.
15. The system of claim 14 , wherein the algorithm is based on the transition depth.
16. The system of claim 14 , wherein the algorithm is based on the branching value.
17. The system of claim 14 , wherein the algorithm is based on the transition depth and the branching value.
18. The system of claim 14 , wherein the algorithm is based on a pre-fetch hint contained in at least one instruction.
19. The system of claim 14 , wherein the algorithm is based on a pre-fetch hint contained in at least one instruction and the transition depth.
20. The system of claim 14 , wherein the algorithm is based on a pre-fetch hint contained in at least one instruction and the branching value.
21. The system of claim 14 , wherein the algorithm is based on a pre-fetch hint contained in at least one instruction and the transition depth and the branching value.
22. One or more non-transitory computer-readable media comprising a plurality of instructions stored thereon that in response to being executed result in a DFA engine:
accessing an instruction from an instruction cache;
determining at least one of a branching value associated with the instruction and a transition depth associated with the instruction;
determining a number of instructions based on at least one of the branching value or the transition depth; and
pre-fetching the number of instructions.