Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have little knowledge about the subjects of compiler construction and parallel programming, so please bear with me. This is a course about compiler construction, and we are asked to learn CUDA while taking the course because the professor would like us to write a compiler for a simplified language. That compiler is supposed to be doing the work in parallel at some specific stages. My understanding was that the scanner, parser, semantic analyzer, code generator and the optimizer are inherently sequential. I have written some parsers for very simple tasks before, so my understanding is based on little bit of theory and little bit of experience. I would understand how to incorporate shared state at some point in the construction of the compiler to do multiprocessing, but not SPMD.

What components of a compiler can be parallelized(e.g. using CUDA as in my case, SPMD model in general)?

SPMD: Single Program Multiple Data

share|improve this question
    
Is this a beginning compiler construction course, or an advanced one? I think the instructor's decision to mix compiler construction with CUDA programming is ill advised; compiler construction is difficult enough to wrap your mind around as it is. –  Robert Harvey Sep 19 '11 at 20:22
    
In any case, the techniques for parallelizing any program (including compilers) are the same as any other generalized parallelization effort: you break the work up into pieces that can be processed independently and simultaneously, so that the pieces don't interfere with each other. The difference being that CUDA uses a microprocessor that's specifically designed to process imagery, so there's going to be some impedance mismatch there while you try to pound the round peg into that square hole. –  Robert Harvey Sep 19 '11 at 20:25
    
@Robert Harvey No sir, this is not an introductory course. It is about Compiler Construction Techniques. –  AraK Sep 19 '11 at 20:29
    
This is always referred to as SIMD, not SPMD, Single Instruction Multiple Data. –  DeadMG Sep 20 '11 at 11:24
    
@DeadMG, you're wrong. en.wikipedia.org/wiki/SPMD –  SK-logic Sep 20 '11 at 12:19

5 Answers 5

There are all sorts of opportunities for handling the work in parallel. Individual lines in a source-code files can be scanned and tokenized independently of each other, for example. Blocks of code can typically be parsed independently of each other and can be target for parallelism there.

Some optimization techniques lend themselves to being parallelized. Intermediate structures containing information about register allocation, can, for example, be generated independently from different blocks of code, and then stitched together in one long pass at the end. Much intermediate work and some code generation work can be done in parallel - it's possible to have a complete intermediate representation where code generation can occur in parallel, starting at multiple starting points at the same time.

Of course, this all sounds rather strange. It's unusual to try to write a compiler which uses CUDA (compilers nowadays are mostly more than fast enough for most purposes they're used for, without parallelization). It's much more common to try and write a compiler which compiles CUDA code, and which attempts to introduce parallel processing power into code originally written to run linearly.

share|improve this answer
1  
You'd have to contruct your language for this. In common languages like C, there's no formal relation between statements and lines. –  MSalters Sep 20 '11 at 11:09

...compiler is supposed to be doing the work in parallel at some specific stages.

Your professor seems to have it the other way around I am afraid. Or maybe you misunderstood him.

I would rather expect a compiler that would produce SPMD (CUDA) optimized target code generated from your simplified language. So that, say, simple addition of vectors, no matter how it is expressed in source language, gets translated into correct and high-performant set of CUDA API calls.

In that sense I would say compiler is supposed to be producing target code doing the work in parallel at some specific stages. It doesn't matter if it does that sequentially - as long as its output code exploits SPMD.

share|improve this answer
    
I would say this is how I understood it at first, but when I asked the prof he corrected me and said that The parallel work is done by the compiler it self. –  AraK Sep 20 '11 at 12:45

A possible use for SPMD acceleration can be something like more aggressive register allocation and instruction scheduling. See this article for inspiration.

share|improve this answer

The interesting part would be the linker phase. Regular compilation is embarrasingly parallel anyway; just use one thread per Translation Unit. Merging the results isn't. This is essentially graph theory; you're resolving external references (arcs), and eliminating unused functions (disjoint subgraphs).

share|improve this answer

My understanding was that the scanner, parser, semantic analyzer, code generator and the optimizer are inherently sequential

That's not entirely true. I've had some ideas about running parsers concurrently. Whether or not a parser is concurrent or not depends on whether the language's structure is atomic.

For a really simple example:

namespace_scope_definition := x | y | z | a | b | c;
namespace := `namespace` `{` namespace_scope_definition+ '}';
program := namespace+;

Each namespace in this case, and each definition inside it, has it's own independent parse tree. If you were to separate them out into "atoms", you could parse each "atom" independently.

Arguably, a semantic analyzer could have the same basic idea, and possibly even an optimizer- different sections of source can be analyzed/optimized concurrently. In addition, you can lex each file of source code independently.

share|improve this answer
    
Probably (but quite unlikely) this approach can be utilised to some extend with a classic shared memory thread-level parallelism. But there is nothing you can do in SPMD way. –  SK-logic Sep 20 '11 at 12:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.