Guy Steele on Parallel Programing

Perm url with updates: http://xahlee.org/comp/Guy_Steele_parallel_computing.html

Guy Steele on Parallel Programing

Xah Lee, 2011-02-05, 2011-02-06

A fascinating talk by the computer scientist Guy Steele. (popularly known as one of the author of Scheme Lisp)

How to Think about Parallel Programming: Not! (2011-01-14) By Guy Steele. @ Source www.infoq.com

The talk is a bit long, at 70 minutes. The first 26 minutes he goes thru 2 computer programs written for 1970s machines. It's quite interesting to see how software on punch card works. For most of us, we've never seen a punch card. He goes thru it “line by line”, actually “hole by hole”. Watching it, it gives you a sense of how computers are like in the 1970s.

At 00:27, he starts talking about “automating resource management”, and quickly to the main point of his talk, as in the title, about what sort of programing paradigms are good for parallel programing. Here, parallel programing means solving a problem by utilizing multiple CPU or nodes (as in clusters or grid). This is important today, because CPU don't get much faster anymore; instead, each computer is getting more CPU (multi-core).

In the rest 40 min of the talk, he steps thru 2 programs that solve a simple problem of splitting a sentence into words. First program is typical procedural style, using do-loop (accumulator). The second program is written in his language Fortress, using functional style. He then summarizes a few key problems with traditional programing patterns, and itemize a few functional programing patterns that he thinks is critical for programing languages to automate parallel computing.

In summary, as a premise, he believes that programers should not worry about parallelism at all, but the programing language should automatically do it. Then, he illustrates that there are few programing patterns that we must stop using, because if you do write your code in such paradigm, then it would be very hard to parallelize the code, either manually or by machine AI.

If you are a functional programer and read FP news in the last couple of years, his talk doesn't seem much new. However, i find it very interesting, because:

  • ① This is the first time i see Guy Steele talk. He talks slightly fast. Very bright guy.
  • ② The detailed discussion of punch card code on 1970s machine is quite a eye-opener for those of us who haven't been there.
  • ③ You get to see Fortress code, and its use of fancy unicode chars.
  • ④ Thru the latter half of talk, you get a concrete sense of some critical “do's & don'ts” in coding paradigms about what makes automated parallel programing possible or impossible.

In much of 2000s, i did not understand why compilers couldn't just automatically do parallelism. My thought have always been that a piece of code is just a concrete specification of algorithm and machine hardware is irrelevant. But i realized, that any concrete specification of algorithm is specific to a particular hardware, by nature. (See: Why Must Software Be Rewritten For Multi-Core Processors?.)

Parallel Computing vs Concurrency Problems

Note that parallel programing and concurrency problem are not the same thing.

Parallel programing is about writing code that can use multiple CPU. Concurrency problems is about problems of concurrent computations using the same resource or time (e.g. race condition, file locking). See: Parallel computingConcurrency (computer science)

Elegant Functional Style ≠ Automatic Parallelism

I've been doing functional programing for about 17 years (since 1993), pretty much ever since i started programing with my first language Mathematica. One paradigm i use frequently, is sequencing functions, aka chaining functions, piping, fold, nest. In some sense, most of my programs is one single sequence of function chain. The input is feed to a function, then its output to another, then another, until the last function spits out the desired output. It is extremely elegant, no state whatsoever, and often i even take the extra mile to avoid using any local temp variables or constants in my functions. But after watching this video, i learned, that function chaining is NOT good for parallelism, despite it is considered a very elegant functional paradigm.

As a functional programer, typically we are familiar with all the FP style constructs, and we strive for such elegance. The important thing i learned from this video is that, elegance in functional style does not mean it will be good for parallelism. Similarly, software written with purely functional language such as Haskell, does not imply it'll be good for parallelism. (but will be a lot better than procedural langs, of course.) FP and Automatic Parallelism certainly share some aspects, such as declarative code and not maintaing states, but is not the same issue.

Here's a few properties of functions he think it's important for automatic parallelism . (if you haven't watched the whole video carefully, you probably won't understand it because it's out of context. I'm listing them here for myself too)

  • Associativity . (grouping doesn't matter) e.g. ((a ⊕ b) ⊕ c) == (a ⊕ (b ⊕ c))
  • Commutativity . (order doesn't matter.) e.g. (a ⊕ b) == (b ⊕ a)
  • Idempotent
  • Identity
  • Zero

Here's things you should avoid, from his slide:

  • DO loops.
  • linear linked list
  • Java style iterator.
  • even arrays are suspect.
  • as soon as you say “fist, SUM = 0” you are hosed.
  • accumulators are BAD. They encourage sequential dependence and tempt you to use non-associative updates.
  • If you say, “process sub-problems in order,” you lose.
  • The great tricks of the sequential past WON'T WORK.
  • The programing idioms that have become second nature to us as everyday tools for the last 50 years WON'T WORK.

Conclusion:

  • A program organized according to linear problem decomposition principles can be really hard to parallelize. (e.g. accumulator, do loop)
  • A program organized according to independence and divide-and-conquer principles is easy to run in parallel or sequentially, according to available resources.
  • The new strategy has costs and overheads. They will be reduced over time but will not disappear.
  • in a world of parallel computers of wildly varying sizes, this is our only hope for program portability in the future.
  • Better language design can encourage “independent thinking” that allows parallel computers to run programs effectively.

Here's a paper written by Guy Steele in 2009, which kinda summarize the points in this talk. (requires lisp knowledge to understand)

Organizing Functional Code for Parallel Execution “or, foldl and foldr Considered Slightly Harmful”. (2009-08) Guy Steele. @ Source labs.oracle.com

Fortress & Unicode

It's interesting that Fortress language freely uses unicode chars. For example, list delimiters are not the typical curly bracket {1,2,3} or square bracket [1,2,3], but the unicode angle bracket ⟨1,2,3⟩. (See: Matching Brackets in Unicode.) It also uses the circle plus ⊕ as operator. (See: Math Symbols in Unicode.)

I really appreciate such use of unicode. The tradition of sticking to the 95 chars in ASCII of 1960s is extremely limiting. It creates complex problems manifested in:

All these problems occur because we are jamming so many meanings into about 20 symbols in ASCII.

See also:

Also, most of today's languages do not support unicode in function or variable names, so you can forget about using unicode in variable names (e.g. α=3) or function names (e.g. “lambda” as “λ” or “function” as “ƒ”), or defining your own operators (e.g. “⊕”). (Exceptions i know that works well in practice are: Mathematica, Javascript, Java, Emacs Lisp. See: Unicode Support in Ruby, Perl, Python, Emacs Lisp.)

Popular posts from this blog

11 Years of Writing About Emacs

does md5 creates more randomness?

Google Code shutting down, future of ErgoEmacs