Expressing Parallelism II: explicit expressions


In the previous post, I explained the necessity for novel parallel programming languages. In this post, I will discuss the precision of parallel languages. By precision, I mean the degree to which an algorithm’s parallel implementation can be optimized for a particular computational architecture.

In 1982, the Poker programming environment introduced three semantic levels of parallel code. The lowest level of code focuses on the execution of a single processor within a larger multiprocessor system. At the middle level, code describes the communication protocol between two or more processors. Finally, the highest level of code orchestrates a global algorithm.

Poker’s three semantic levels provide a good framework to discuss the precision of parallel languages. Using conventional parlance, languages can be explicitly parallel or implicitly parallel. Explicit languages emphasize the lowest and middle levels of the Poker model. Explicit languages verbosely express inter-process communication and robustly articulate the mapping of data to processors. The explicit focus on lower semantic levels typically obfuscates any cogency of the overall parallel algorithm. On the other hand, implicit languages emphasize a higher semantic level and express parallelism in an abstract fashion. Although implicit languages provide semantic terseness, they traditionally incur an additional performance overhead because they cannot be fine-tuned for a particular architecture.

Explicit and implicit languages assume two different philosophies for achieving computational performance. Explicit languages rely on human developers to effect fine-grain architecture-specific adjustments to a code’s performance. Implicit languages rely on sophisticated compilers to “auto-magically” optimize data mappings and inter-process communication. Until recently, it was assumed that human optimizations outperformed compiler optimizations. In other words, the following relationship was historically true:

Explicit languages: verbose semantics => fine-tuned performance

Implicit languages: clean semantics => suboptimal performance

Today I listened to Qing Yi present a talk titled “Parameterizing optimizations for emprical tuning (POET)”. POET scripts provide language-independent annotations which can be inserted into existing code. The POET annotations can be written automatically by a compiler or manually by a human. POET’s philosophy is to allow developers to get at the results of the compiler (in a more explicit manner than compiler flags). Using this paradigm, it should be easy to envision a hybridization of explicit and implicit languages. In the ideal future, we could use highly abstract languages to implement parallel algorithms, and intermediary tools (such as POET) to fine-tune the compilation.

So what’s my point? Developers typically assume that compilers cannot generate efficient parallel code. Consequently, developers accept the burden of explicitly expressing parallelism. Emergent compiler tools, such as POET, point towards a hybridized future where we can enjoy the semantic ease of implicitly parallel languages with the fine-grained optimizations of explicit languages.


7 Responses to “Expressing Parallelism II: explicit expressions”

  1. Eddie Says:


    Remember me, from Susanville? Back then, “Victor” connoted “dangerous criminal”. Now, with these fancy essays you have been cranking out, it’s more like you’re Victor-freaking-Hugo. I am not sure what’s going on. Anyway, I got a good job coming up if you’re interested.


    P.S. Floyd’s back in the joint but he sends his regards.

  2. Kynthia Says:

    actually, when i read these posts again, they do make a lot of sense. what is missing, for me, is a reason to Care about the evolution of parallel programming, apart from a general desire to support the march of progress and my faith in your ability to choose important work.

    not that those reasons should be dismissed lightly. 🙂

    but a personal interest and belief in the importance of the work is almost certainly implied for your target audience, so i would only worry about that if you are planning on writing a version for wider distribution. or, i suppose, if you’re trying to convince some computer sciencists to jump ship and widen their skillsets so that they can join you. in those cases, i would take the time to explain why, in concrete terms, the advancement of parallelism is a noble goal.

    as it is, however, this is what i get:
    a) parallel programming lets you do neat things but it takes a lot of time and energy to tell the processors exactly what to do.
    b) when you express the parallelism more abstractly it is way more fun because you can spend your time and energy coming up with awesome algorithms and exploring their implications instead of barking step-by-step orders at stupid machines.
    c) right now the potential of this more abstract approach is difficult to realize because Someone still has to bark orders, and the compilers aren’t very good at it, so if we want to do it right we still have to do it ourselves.
    d) this is a lame excuse for not doing things the right way, and the obvious next steps are to keep using the abstract languages so that they get better and keep working on making the compilers smarter.
    e) this proto paper is about the options victor sees for advancing those goals.

    did i get it?

    my only more basic criticism is that sometimes you seem to write sentences just to prove that you can. case in point: “The explicit focus on lower semantic levels typically obfuscates any cogency of the overall parallel algorithm.”

    that is a wonderful sentence, and quite possibly the most elegant way to express the concept behind it. nevertheless, i believe that sometimes a more explicit approach can be beneficial when it comes to calling upon the reader’s vocabulary, if only to preserve processing power for the actual task of absorbing the main message of the paper. 😉

    they might not agree with you yet about the inherent superiority of the higher levels, you see. and if they don’t, they aren’t going to be reading those sorts of sentences with an eye to appreciating them in the manner you intend. they will either just feel happy that they are smart enough to parse them (in which case they will be distracted from your paper), or they will think you are pretentious (in which case you are not likely to be able to convince them of anything).

    but maybe you think i’m underestimating them, or that it’s a battle worth fighting. this just happens to be one of my personal beefs with academic writing, so i can be too picky about it, and i’ve argued about it with erik already, so bring it on. 🙂

    and eddie, victor hugo is an interesting choice for the straight (ahem!) academic persona of a so-called dangerous criminal, seeing as he is all about the depths to which an unjust criminal system can drive us, and the paths we can carve for ourselves by refusing to accept a worldview that sees us as guilty and instead fighting the good fight in whatever ways we can.

    so worry not, methinks victor is just figuring out how to take Everything to the next level. 😉

  3. Victor Says:

    Kynthia, thanks for clear-headed and honest critique!

  4. Jeff Says:

    I think Victor was not arguing for Parallelism, per se, but that those who are in that domain should consider alternatives to the traditional approach. I think he made very compelling arguments.

    When I read these last few blog entries I was excited about how well written they were. I should point out that in the example you gave, Kynthia, the only word that might not occur regularly in Computer Science discussions is “cogency.” I think anyone not familiar with that word should be able to figure it out by context. In general, however, I agree that we live in a world where anything but dumbed-down writing risks alienating readers.

  5. Eddie Says:


    You make some good points. I thought I could make a reference to an obscure literary figure and I would fit in with all Victor’s highbrow friends. All I was really trying to say is: “Victor, give us less ‘good ideas’ and more of them ‘bad stories'”. I like bad stories. He he.


  6. Kynthia Says:

    i like to think that i don’t believe in dumbing down; i just also don’t believe in smarting up. i was kind of being funny, but the bit about reserving processing power for other things really gets to the heart of my point. i love language. it is powerful stuff. i think that, barring a few wonderful exceptions where the object is play, it should be like a samurai sword — wielded only when needed, and never for show.

    jeff, thanks for reading my lengthy reply. i know i have lessons of my own to learn before i get my samurai of brevity merit badge, but it’s fun to have discussions like this with many people. i think you’re right that “cogency” is more of the sticker, but “obfuscate” is a funny word – i think people understand it, but it also sets off a little bell that says “i understand big words!!” and the resonance of that bell within the mind is distracting.

    but maybe that’s just me because whenever i hear it i get two strong hits of memory:

    the moment when i first learned the word, which was when i looked it up after its use on the x-files;
    that bumper sticker that says “eschew obfuscation!!” which i think i first understood soon thereafter, and chuckled about a lot.

    on with the show!

    oh, but victor? unless you are in luff with them, can you turn off graphical emoticons? i can’t help but smile when i’m talking to you, but seeing them in my comments makes me want to stab small woodland creatures with sticks.

  7. Kynthia Says:


    ha! we posted at the same time!!

    i likes the stories, too, but i’m happy that the blog is being used for both. the more people write crap that mostly only makes sense to them but that they are clearly passionate about, the better i sleep at night for confidence that the world is in good hands.

    and you probably would have been safe with victor hugo, except i happened to be a bit too obsessed with les mis in highschool, so i made myself read the actual book, and some other stuff besides, and there was plenty of good badness in that crowd, so it’s a hat i’d be proud to wear.

    particularly if it came with croissants.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: