Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Christopher F Clark Newsgroups: comp.compilers Subject: Re: Parsing using a Graphics Processing Unit (GPU)? Date: Wed, 2 Sep 2020 17:57:37 +0300 Organization: Compilers Central Lines: 17 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <20-09-010@comp.compilers> References: <20-09-001@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="34224"; mail-complaints-to="abuse@iecc.com" Keywords: parallel Posted-Date: 02 Sep 2020 11:49:45 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2581 To follow up on the part of the question about using GPUs to do arithmetic to implement DFA transitions. It can "easily" be done. The base ideas can be found in the Wu Mamber string search algorithm. You treat states like (usually one-hot) bits in a fixed length (usually one word) bit vector. Your transition function then simply maps bit vectors to bit vectors. You can do that as a SIMD instruction, thus it is suitable for a GPU to execute. -- ****************************************************************************** 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 ------------------------------------------------------------------------------