Slashdot Mirror

← Back to Stories (view on slashdot.org)

The Double Life of Memory Exposed With Automata Processor

Posted by Unknown on from the perl-accelerator dept.

An anonymous reader writes "As Nicole Hemsoth over at HPCwire reports 'In a nutshell, the Automata processor is a programmable silicon device that lends itself to handing high speed search and analysis across massive, complex, unstructured data. As an alternate processing engine for targeted areas, it taps into the inner parallelism inherent to memory to provide a robust and absolutely remarkable, if early benchmarks are to be believed, option for certain types of processing.'" Basically, the chip is designed solely to process Nondeterministic Finite Automata and can explore all valid paths of an NFA in parallel, hiding the whole O(n^2) complexity thing. Micron has a stash of technical documents including a paper covering the design and development of the chip. Imagine how fast you can process regexes now.

32 comments

  1. post went up before i finished typing it by Anonymous Coward · · Score: 0

    that's fast

    1. Re: post went up before i finished typing it by Anonymous Coward · · Score: 0

      Oh joy. That means the NSA can use these to get our data before we finish it.

  2. Exploring NFAs in parallel by supersat · · Score: 4, Interesting

    Well, strictly speaking, you can already explore all paths of an NFA simultaneously. You simply convert it to a DFA, which each state representing a potential subset of states the NFA could be in. It requires exponentially more states, but the running time is equivalent.

    1. Re:Exploring NFAs in parallel by Anonymous Coward · · Score: 0

      The conversion costs the same as just solving the NFA in the first place.

    2. Re:Exploring NFAs in parallel by Anonymous Coward · · Score: 5, Interesting

      In the real world (as opposed to the Big O world), the running time is waaayyyyyy faster.

      We wrote a program to translate ~10,000 non-trivial Perl regular expressions to DFAs (specifically, into Ragel syntax). Actually, only about a quarter could be completely translated, because of various Perl extensions. The rest had to be programmatically analyzed for sub-expressions which could be turned into filters--only if the filters matched did the PCRE actually run.

      Achieved a 20x (yes, 20x!) improvement in throughput compared to Perl or PCRE, and very nearly that compared to RE2 (RE2 doesn't scale well wrt memory when you try to union more than a few complex expressions together). However, as you pointed out, the state machine was enormous--over 1GB compiled, and over 2GB in source code. It was so big that neither GCC nor clang could compile it within an afternoon because their array and structure handling code has some algorithmic deficiencies. So we had to come up with some tricks there, too.

      You would think the DFA approach would run afoul of memory bandwidth and cache trashing at that scale. And it probably does, although there appears to be a significant degree of locality involved for most inputs. But regardless it's clearly better than running NFAs.

      Tangent:
      I was once on a conference call with Intel engineers who were hawking some fancy substring matching code. I think they implemented Aho–Corasick, utilizing new Xeon vector operations. Their goal was obviously to sell more expensive hardware by selling optimized software at a nominal cost and tying you to their platform. Their numbers were nice, but Ragel was still performance competitive, could scale better (in terms of number of patterns), is FOSS, and has an ingenius design which makes it trivial to integrate into your application without having to deal with an API that breaks your threading or I/O model.

      I'm sure the Automata processor would do well if it can be productized properly. But there's plenty of room for improvement in the way people do regular expressions now.

    3. Re:Exploring NFAs in parallel by Wootery · · Score: 1

      Achieved a 20x (yes, 20x!) improvement in throughput compared to Perl or PCRE

      You were using Ragel with C/C++, right?

      However, as you pointed out, the state machine was enormous--over 1GB compiled, and over 2GB in source code

      Good lord, what were you processing?

    4. Re:Exploring NFAs in parallel by Anonymous Coward · · Score: 2, Interesting

      Hi, I'm a biochemist and I had a very nice conversation with these guys at SC13.

      If it actually does appear on the market as a normal memory module, it is likely to find many uses that cannot be imagined now!

      In the paper presentation the phrase "non-von neumann" architecture is a hint at the applications that may be useful.

      And while we are on the subject, the quantum d-wave talk was fascinating...!

    5. Re:Exploring NFAs in parallel by wkcole · · Score: 1

      However, as you pointed out, the state machine was enormous--over 1GB compiled, and over 2GB in source code

      Good lord, what were you processing?

      AC discussing massive complex unstructured data analysis? My bet is a PRISM LOVEINT project...

  3. I stopped reading TFA by Anonymous Coward · · Score: 1

    It's so full of scripts that keep phoning home the annoyance couldn't possibly justify the maximum possible value gainable from reading the content.

  4. O(n^2)? by Anonymous Coward · · Score: 3, Insightful

    I suppose that was meant to say O(2^n)? Emulating an NFA on a DFA requires exponentially more either memory or time.

    1. Re:O(n^2)? by deaf.seven · · Score: 1

      with n^2 we wouldn't have the NP = P problem^^

  5. "handing" - handling [EOM] by Anonymous Coward · · Score: 0

    See subject.

  6. Double life by Anonymous Coward · · Score: 0

    Every double-life must end in a double-death.

  7. no need to forget what we never know about by Anonymous Coward · · Score: 0

    motive always equals results http://www.youtube.com/watch?v=MLO3NmGJuHg

  8. When CPU meets RAM. by Anonymous Coward · · Score: 0

    Reminds me of Computational RAM.

    1. Re:When CPU meets RAM. by rpresser · · Score: 1

      Somewhat similar. Also resembling WISARD, which used RAM like a neural network.

      The essential point to think about is that a 1GB RAM can act as a cellular automaton with a billion cells. There's no algorithmic complexity to defeat because there's no algorithm. Of course the harder the problem gets, the more cells you need....

  9. wonder how it compares to GPGPU by Trepidity · · Score: 4, Interesting

    There is some existing work on the same basic idea of massively parallelizing regex matching by doing all the NFA branches in parallel, but using a GPU. Now a GPU is not necessarily perfectly suited to this problem, but it does have the advantage of being a mass-market consumer product, which produces economies of mass-market scale that let the average GPU have a ton more processing units and RAM than this Automata processor does. Would be interesting to see if an NFA-specialized processor gets enough of a speedup to overcome the manufacturing advantage of just throwing a beefy GPU at the problem.

    --
    10 PRINT CHR$(205.5+RND(1)); : GOTO 10
  10. Yes, but how many Hashes/s can it crack?!? by Anonymous Coward · · Score: 0

    Yes, but how many Hashes/s can it crack?!?

  11. The NSA finally gets some good news! by Anonymous Coward · · Score: 0

    The final obstacle to complete surveillance falls.

  12. Speeding up the wrong algorithm again? by Theovon · · Score: 4, Interesting

    I skimmed over the article, but I couldn’t tell: Is this another example of someone choosing an O(n^2) algorithm over an equivalent O(n log n) algorithm and then patting themselves on the back because they speed up the O(n^2) algorithm through parallelism, even though it’s still slower than the O(n log n) on a single processor?

    I can’t tell because they go on about NFA’s, which would be exponential in time compared to DFA’s. That’s a totally different thing.

    1. Re:Speeding up the wrong algorithm again? by Anonymous Coward · · Score: 0

      The n^2 comment is simply the incompetence of the Slashdot editors on display once again.

    2. Re:Speeding up the wrong algorithm again? by Anonymous Coward · · Score: 0

      Yes, it is.

    3. Re:Speeding up the wrong algorithm again? by Anonymous Coward · · Score: 0

      The O(n^2) thing is from the submitter, not the article. It's a complete facepalm because obviously the problem is NP-complete by definition.

  13. Space for Time Trade-off by Anonymous Coward · · Score: 1

    From a brief scan, this is an interesting Space-time tradeoff. Definitely has close physical limits to scaling, and we're not that strong algorithmically on what to do with this type of chip. Should be good Ph.D. material for a few years at least.

  14. No, it cannot hide O(n^2).... by gweihir · · Score: 1

    O(n^2) is the complexity of the problem, not that one of the implementation. That means it is impossible to hide it. This thing just gives some level of parallelism, hence the performance looks a bit better. It is still O(n^2) and when the NFA expands the search tree beyond that parallelism, the thing is back to plain quadratic behavior.

    --
    Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
  15. running NFA in even LINEAR time is trivial by Anonymous Coward · · Score: 0

    Well you can run any NFA in linear time (special hardware or no)... you don't have to determinize. Simply start in the initial state and carry along the set of all states reachable: if your word is "abbbab" then you check which states can be reached by 'a', then which states can be reached from those with a 'b'.. etc. None of those sets is larger than the number of states (constant) and the input length sets a hard limit on the length of the computation. In effect you produce a run of the powerset automaton without constructing that automaton explicitly.

    You can even check if the language is non-empty (simple depth-first search).

    What you cannot do with an NFA (efficiently) is to check whether there's an input that's rejected. THAT requires exponential time (it's PSPACE complete).

    My guess is that the hardware uses some sort of symbolic representation of the NFA to speed up use of that kind of thing. Or possibly to try speed up some of those PSPACE-hard stuff I mentioned... like non-universality (there exists an input that is not accepted), intersection and so forth.

  16. Now They Have Two Problems by Anonymous Coward · · Score: 0

    Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

    -- Zawinski