3 ms·
I'm missing something here, how do you know your start state when you do it in parallel?
by foota 8y ago
I'm missing something here, how do you know your start state when you do it in parallel?
- pjscott 8y agoThe part you do in parallel is computing the function "If the DFA is in state x, and it sees the whole input string, where will it end up?" You can represent that function as a table, one entry for each state. Once you've got that table, just look in the entry for the start state.
- Dylan16807 8y agoSo each thread might have to do up to m times the work, where m is the number of states? That sounds like it might be a pretty bad hit on the number of processors you need just to break even.
- Tarean 8y agoYou don't compute an end state, you compute a transition table. For each character you parse you look up the corresponding table and then you compose them. Here is a paper on how to do this efficiently with simd instructions https://www.microsoft.com/en-us/research/publication/data-parallel-finite-state-machines/ https://www.microsoft.com/en-us/research/publication/data-pa...