Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2576

Parsing using a Graphics Processing Unit (GPU)?

Show all headers | View raw

Our esteemed moderator wrote:
[Parsing is not usually an important factor in compiler performance.
The slow parts are the lexer, because it has to look at every
character of the input, and some optimizations that have to analyze
the entire intermediate form of the program. The first step in lexing
is to identify what class each character is, e.g., identifier, white
space, or operator. Perhaps a GPU could do vector lookups to speed
that up. For optimizations, I can sort of imagine how some analyses
like reachability might be expressible as matrices. -John]

As to parallelizing lexers, we did some experiments on speeding up
regular expressions (mostly for Snort) while I was at Intel.   Charlie
Lasswell did experiments on starting parallel scans on different parts
of a stream or file that showed some promise.  The hyperscan team (aka
Sensory Networks, Geoff Langdale &co) had some interesting results on
when you could skip ahead and guess the correct state when using
NFAs--I believe they called it "and then a miracle happens" (following
the famous cartoon about a mathematical proof with some missing steps
on a whiteboard).  Michela Becchi worked on when you could predict
states involved in xFA loops would terminate.  Geoff had me do a mode
they called Maclellan (the HS folks had some interesting naming
conventions, one of them was the use of US Civil War generals for
major variations/modes) which was turning NFAs into parallelized DFAs
for Hyperscan.  The regular expression engine we put into the Cave
Creek chip, did a different form of parallel DFAs, spawning them when
certain conditions were met, and for things like the Aho-Corasick
algorithm you can show that there tends to be a "bushy" part near the
head of the automata, with "skinny" parts being forked off after a
small number of bytes--that was the key insight that led to our chip.

So, there are definite possibilities for doing SIMD regular expression
matching that would be suitable for GPU implementation.  Geoff and I
discussed how to approach it on numerous occasions.  It just never
quite got past the to-consider list.

Some of this "could" also be applied to parsing, particularly in a GLR
style parser, where you have forests.  But our moderator is correct in
saying the big boost would be in speeding up lexing.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Parsing using a Graphics Processing Unit (GPU)? Roger L Costello <costello@mitre.org> - 2020-08-31 10:35 +0000
  Re: Parsing using a Graphics Processing Unit (GPU)? Christian Gollwitzer <auriocus@gmx.de> - 2020-09-01 09:22 +0200
    Re: Parsing using a Graphics Processing Unit (GPU)? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-01 19:02 +0200
    Parsing using a Graphics Processing Unit (GPU)? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2020-09-02 01:14 +0300
    Re: Parsing using a Graphics Processing Unit (GPU)? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2020-09-02 02:13 -0700
      Re: Parsing using a Graphics Processing Unit (GPU)? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-02 22:34 +0200
  Re: Parsing using a Graphics Processing Unit (GPU)? "A. K." <minforth@arcor.de> - 2020-09-01 01:25 -0700
    Re: Parsing using a Graphics Processing Unit (GPU)? arnold@skeeve.com (Aharon Robbins) - 2020-09-02 05:43 +0000
  Re: Parsing using a Graphics Processing Unit (GPU)? Elijah Stone <elronnd@elronnd.net> - 2020-09-01 20:13 -0700
    Re: Parsing using a Graphics Processing Unit (GPU)? Roger L Costello <costello@mitre.org> - 2020-09-02 11:45 +0000
  Re: Parsing using a Graphics Processing Unit (GPU)? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2020-09-02 17:57 +0300
  Re: Parsing using a Graphics Processing Unit (GPU)? gah4 <gah4@u.washington.edu> - 2020-09-09 14:09 -0700

csiph-web