[antlr-interest] multi-core usage and pipeline processing

[Loring Craymer]

It should be pointed out that the reason for processing multiple files in parallel is the overhead of opening and closing files.  Without this overhead, the various threads would saturate both disk and memory bandwidth (optimizing disk access leads to large buffers, and competition for memory access results).  When dealing with large files (single file system), though, sequential processing is preferred because disk I/O is the limiting resource and competing file file accesses degrade performance due to frequent long-distance disk seeks.

--Loring


----- Original Message ----
From: Ian Kaplan <iank at bearcave.com>
To: antlr-interest at antlr.org
Sent: Friday, June 13, 2008 11:05:45 AM
Subject: [antlr-interest] multi-core usage and pipeline processing


  As has already been noted, the common use of multicores or multiple systems is parallel make (or ant or maven or what ever).  Multiple files can be compiled in multiple threads of control.  This makes compilation parallelizable to the number of files.

  It should also be possible to make use of pipeline parallelism.  As far as I know, no one has done this because compiling is not generally something that people are willing to put a lot of effort into speeding up beyond parallel make.  But it should be possible to create a pipeline that processes multiple files on a shared memory multi-core.  One state could do parse and AST construction.  Another state could do control flow/data flow construction and optimizatoin and another state could do code generation and target dependent optimization.

  The obvious argument against this is that compilers are already complex enough without making them into multi-process applications.  This would probably only be justified for something like logic synthesis compilers that are generating large net lists (and then you can't store things in memory).

  In summary, at least pipeline parallelism is possible, but it would probably be a bad idea.

  Ian



On Fri, Jun 13, 2008 at 8:41 AM, Edwards, Waverly <Waverly.Edwards at genesys.com> wrote:


Thanks all for your insights.  It was very interesting.


W.

-----Original Message-----
From: Sam Harwell [mailto:sharwell at pixelminegames.com]
Sent: Thursday, June 12, 2008 6:06 PM
To: Andy Tripp; Edwards, Waverly
Cc: antlr-interest at antlr.org
Subject: RE: [antlr-interest] multi-core usage

I'm using a combined grammar with AST output paired with a tree walker
grammar on the CSharp2 target. I spawn 5 threads on a quad-core box and
the parse uses about 65% of the overall processor power while it parses
~2500 files in ~5 seconds.

Breaking the parse into multiple threads provided about a 3:1 speed
increase. Multi-threaded parsing isn't the difficult part; it's
combining the results from the individual threads into one place that
can cause problems if you aren't careful.

Sam

-----Original Message-----
From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Andy Tripp
Sent: Thursday, June 12, 2008 4:50 PM
To: Edwards, Waverly
Cc: antlr-interest at antlr.org
Subject: Re: [antlr-interest] multi-core usage

I have a mechanism where I spawn multiple threads to parse multiple
files.
It speeds things up quite a bit, mostly because doing it single-threaded
is I/O bound. With the multiple threads, file reading and parsing can
happen in parallel.

As for multiple cores, I don't know how much multithreading will help.
>From what I've read, it's not easy to get Java to utilize multiple
CPUs.
I would think you'd have to have incredibly huge input for ANTLR to use
a lot of CPU to parse it. Anyway, it's pretty easy to try out
multithreading in Java, so just try it and see what happens.



Edwards, Waverly wrote:
>
> I have curiosity question.  Can ANTLR take advantage of multi-core
> processors.
> The only place where I can think it would be possible would be in the
> lexer where you might be able to apply one file per core to be
> tokenized.  Has anyone tried?
> Again, just curious.
>
>
> W.
>


      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080613/00b35125/attachment.html