Fran Allen delivers Organick Lecture (click to enlarge)

Fran Allen was the Turing Award winner for 2006. This afternoon she's giving the University of Utah's Organick Memorial Lecture. I've reported on some of these in the past few years:

• Jim Gray on Distributed Computing Economics
• Vint Cerf on Internet Challenges
• Alan Kay: Is Computer Science an Oxymoron?
• Alan Kay: The 100 Dollar Laptop and Powerful Ideas
• Jeannette Wing on Computational Thinking

I try to come every year. I find it's something I'm inspired by each time.

The grand goal of high performance computers right now is a 1 petaflop machine. This requires 1,000,000 gigaflop processors. Wow. She shows a semilog plot of peak speed vs year introduced that is a linear line (Moore's law at work).

Much of Allen's work in the 80's and early 90's was around the PTRAN system of analysis for parallelism. The techniques are used, for example in the optimization stage of IBM's XL family of compilers.

Because more and more transistors are being placed on chips, they're using more and more energy--getting hotter. Part of the solution--which we're seeing play out--is multi-core chips. This requires parallelism to achieve the performance users expect. But making use of multi-codes requires that tasks be organized by either users or software to run in parallel.

By 2021, there will be chips with 1024 cores on them. Is parallelism the tool that will make al these ores useful? John Hennessey has called it the biggest challenge Computer Science has every faced. He has credentials that might make you believe him. Allen says that it's also the best opportunity that Computer Science has to improve user productivity, application performance and system integrity.

For parallel (superscalar, etc.) architectures, compilers--software--have been used to automatically manage scheduling tasks so that they can operate in parallel. What about those techniques will be useful in this new world of multi-cores?

Allen says we need to get rid of C--soon. C, as a language, doesn't provide enough information to the compiler for it to figure out interdependencies--making it hard to parallelize. Another way to look at it is that pointers allow programmers to build programs that can't be easily analyzed to find out which parts of the program can be executed at the same time.

Another factor that makes parallelization hard is data movement. Allen offers no silver bullet. The latency of data movement inhibits high performance.

The key is the right high level language that can effectively take advantage of the many good scheduling and pipelining algorithms that exist. If we don't start with the right high level language, those techniques will have limited impact.

She presents some research from Vivek Sarkar on compiling for parallelism. Only a small fraction of application developers are experts in parallelism. Expecting them to become such is unreasonable. The software is too complex and the primary bottleneck in the usage of parallel systems. X10 is an example of a language (object oriented) that tries to maximize the amount of automatic parallel optimization that can be done.

Major themes include cross-procedure parallelization, data dependency analysis, control dependency analysis, and then using those analyses to satisfy the dependencies while maximizing parallelism.

Useful parallelism depends on the run time behavior of the program (i.e. loop frequency, branch prediction, and node run times) and the parameters of the target multiprocessor. Finding the maximal parallelism isn't enough because it probably can't be efficiently mapped on the multiple cores or processors. There is a trade off between the partition cost and the run time. Finding the intersection gives the right level of parallelism--the level that is the most efficient use of available resources. Interprocedural analysis is the key to whole program parallelism.

One of the PTRAN analysis techniques was the transform the program into a functional equivalent that used static single assignment. This, of course, is what functional programming enthusiasts have been saying for years: one of functional programming's biggest advantages is that functional programs--those without mutation--are much more easily parallelized than imperative programs (including imperative-based object oriented languages).

There's a long list of transformations that can be done--everything from array padding to get easily handled dimensions to loop unrolling and interleaving. Doing most of these transformations well requires detailed knowledge of the machine--making it a better job for compilers than humans. Even then, the speedup is less than the number of additional processors applied o the job. That is, applying 4 processors doesn't get you a speedup of 4--more like 2.2. The speed up--at present--is asymptotic.