From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.2 required=5.0 tests=AWL autolearn=disabled version=3.1.3 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id B7EA3BBAF for ; Tue, 21 Apr 2009 02:52:58 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlMCAEO27EmAcIhIkWdsb2JhbACCHYsFiRwBAQEBCQsKBxEFqxABCYYeiE2CSoEzBg X-IronPort-AV: E=Sophos;i="4.38,431,1233529200"; d="scan'208";a="27999971" Received: from redflag.cs.princeton.edu ([128.112.136.72]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 21 Apr 2009 02:52:48 +0200 Received: from [192.168.0.100] (H-135-207-240-34.research.att.com [135.207.240.34]) (authenticated bits=0) by redflag.CS.Princeton.EDU (8.13.8/8.13.8) with ESMTP id n3L0qgMP008246 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Mon, 20 Apr 2009 20:52:45 -0400 (EDT) Cc: caml-list@inria.fr Message-Id: <87C7CCB2-26AB-4F87-BF38-5924FA68077C@cs.princeton.edu> From: Yitzhak Mandelbaum To: Mike Lin In-Reply-To: <2a1a1a0c0904201435y12e36603t60fb40fd1a7d8260@mail.gmail.com> Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v930.3) Subject: Re: [Caml-list] Parallelized parsing Date: Mon, 20 Apr 2009 20:52:40 -0400 References: <200904202215.27735.jon@ffconsultancy.com> <2a1a1a0c0904201435y12e36603t60fb40fd1a7d8260@mail.gmail.com> X-Mailer: Apple Mail (2.930.3) X-Proofpoint-Virus-Version: vendor=nai engine=5.3.00 definitions=5590 signatures=521263 X-Proofpoint-Spam-Reason: safe X-Spam: no; 0.00; yitzhak:01 mandelbaum:01 context-free:01 context-free:01 yonezawa:01 twente:01 parser:01 citeseer:01 citeseer:01 impl:01 grammars:01 bottom-up:01 grammars:01 algebra:01 pubs:01 Unfortunately, most forms of parsing are not terribly amenable to efficient parallelization because of the irregular nature of the subcomponents of the parsing problem. That is, you can't easily break up the problem into subcomponents that can be farmed out to different CPUs. That said, if you've just got CPU's lying around, unused anyhow and wasting resources isn't that important, then there is plenty of work on this topic which might be applicable. Some good places to start are here: A. Nijholt. Parallel approaches to context-free language parsing. Chapter 2 in: Parallel Natural Language Processing, U. Hahn and G. Adriaens (eds.), Ablex Publishing Corporation, Norwood, New Jersey, 1994, 135-167 (ISBN 0.89391.869.5). and here: Survey of Parallel Context-Free Parsing Techniques, M. P. van Lohuizen, 1997. In case you're really interested in the topic, here's a more complete list of references with assorted notes (my own). References below are taken from the above survey. * **Parallel Natural Language Processing**. A book on parallel parsing algorithms. By Geert Adriaens, Udo Hahn. [Available in Google Books](http://books.google.com/books?id=G9-67_mQPnkC). Some relevant chapters follow * YO94: nonterminal-per-processor. Akinori Yonezawa and Ichiro Ohsawa. Object-oriented parallel parsing for context-free grammers. In Adriaens and Hahn. * Fan94: "Connectionist" parsing. Good for massively parallel machines. Survey authors comment that not promising for CF parsing. Mark Fanty. Context-free parsing in connectionist networks. In Adriaens and Hahn. * Sik93b: A Cross-breeding of Tomita and Earley. Klaas Sikkel. **Parsing Schemata**. PhD thesis. Dept of Computer Science University of Twente Enschede The Netherlands * There's a book-chapter preprint on parsing schemata which is related to the above. There's also a book of the same name, which is a revised version of the thesis. * GC88: MIMD shared-memory Earley. Ralph Grishman, Mahesh Chitrao. Evaluation of a parallel chart parser ([citeseer](http://citeseer.comp.nus.edu.sg/579833.html) * dV93b: measurements on par. impl. of CYK, Earley and DD. J.P.M. de Vreught. A practical comparison between parallel tabular recognizers. * CF84, Sij86, Tan83: VLSI Earley. * More VLSI Earley: **A Parallel Parsing VLSI Architecture for Arbitrary Context Free Grammars** Andreas Koulouris, Nectarios Koziris, Theodore Andronikos, George Papakonstantinou, Panayotis Tsanakas. 1998. * HdV91, IPS91: load balancing approaches to chart parsing. J. Hoogerbrugge and J.P.M. de Vreught. **Parallel recognizing in practice**. Ibarra, Pong, and Sohn, **Parallel recognition and parsing on the hyper-cube**. IEEE Transactions on Computers, 40(6):764-770, 1991. * The proposal for Berkeley's new parallel computing center (sponsored by Intel & MS) mentions the need for parallel parsing of web pages. I don't know what, if any, progress they've made in that direction. * More parallel earley. Includes description of algorithm (basically, bottom-up earley) together with proofs relating to running time and communication time. Also reports results on running an implemenation on a parallel-machine simulator. **A parallel parsing algorithm for arbitrary context-free grammars**. Dong-Yul Ra and Jong- Hyun Kim. * A Static Load-Balancing Scheme for Parallel XML Parsing on Multicore CPUs. Yinfei Pan, Wei Lu, Ying Zhang , Kenneth Chiu. A paper on parallel XML parsing. I've seen a few of these. This one is representative. * A paper on linear algebra on GPUs (http://www.cs.utexas.edu/users/flame/pubs/sc08.pdf ). Possibly relevant because chart parsing can be implemented as a form of matrix multiply. Yitzhak On Apr 20, 2009, at 5:35 PM, Mike Lin wrote: > There is certainly a reasonable body of basic CS research on > parallelizing CFG algorithms such as CYK, the Earley parser, and to a > lesser extent the more practical LALR strategy used by yacc etc. (In > the latter case it seems to get easier if you're willing to trade off > determinism when parsing ambiguous grammars.) > > I know some people who use some of this stuff in very specific > contexts (RNA folding), but I haven't seen any practical > general-purpose tools like a parallel yacc... > > Overall, I don't actually know much more than you could figure out > from Google Scholar in an hour but hopefully these were some useful > search terms. > > On Mon, Apr 20, 2009 at 5:15 PM, Jon Harrop > wrote: >> >> I'm desperately trying to prepare for the imminent drop of a rock- >> solid >> multicore-friendly OCaml implementation and was wondering what work >> has been >> done on parallelized parsers and/or parallel-friendly grammars? >> >> For example, Mathematica syntax for nested lists of integers looks >> like: >> >> {{{1, 2}}, {{3, 4}, {4, 5}}, ..} >> >> and there are obvious divide-and-conquer approaches to lexing and >> parsing that >> grammar. You can recursively subdivide the string (e.g. memory >> mapped from a >> file) to build a tree of where the tokens { , and } appear by index >> and then >> recursively convert the tree into an AST. >> >> What other grammars can be lexed and/or parsed efficiently in >> parallel? >> >> -- >> Dr Jon Harrop, Flying Frog Consultancy Ltd. >> http://www.ffconsultancy.com/?e >> >> _______________________________________________ >> Caml-list mailing list. Subscription management: >> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list >> Archives: http://caml.inria.fr >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs >> > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs ----------------------------- Yitzhak Mandelbaum