Leibson's Law

Tim Mattson, a principal engineer at Intel’s Applications Research Laboratory, describes himself as an old-school parallel programmer. He’s been slinging code for impressively parallel machines since 1985. That makes him an authority in my book. He sounds like one too. Mattson was the keynote speaker at last week’s IEEE DATC Electronic Design Processes Workshop held in Monterey, California. He had a lot to say about programming parallel machines (increasingly common in the multicore SOC age) and he said it with passion and authority—a potent combination. But first, his disclaimer (which I loved): Mattson was speaking his mind and his opinions do not necessarily reflect those of Intel or its lawyers.

Mattson first overviewed the driving reason behind the trend towards using more processors in SOC and system design. I’ve discussed these drivers many times in this blog, but it doesn’t hurt to briefly repeat. Moore’s Law continues unabated. We get more transistors onto a chip every year. Mattson laid out the timeline for future lithographic advances in IC fabrication:

    Year            Lithography

2007                45nm
2009                32nm
2011                22nm
2013                16nm
2015                11nm
2017                  8nm

In 10 years, we’ll be capable of putting 32 billion transistors on a chip. By then, we’d better not be designing chips and systems the same way we do today.

Denard Scaling died at 90nm so we’re not seeing the power reductions we formerly got with every process shrink. As a result, power considerations are curbing the formerly rapid climb in clock rates, which had served as our principal tool for boosting processor performance. Now we’re turning to multiple processors to replace GHz clock rates as the tool of choice for boosting performance. All of this is cold, hard reality. Anyone who argues that we will continue to see clock-rate improvement ramps like those that have come before is delusional. (Those are my words, not Mattson’s.)

Consequently, parallel programming is about to become a way of life in our business and Mattson wants us to be ready. “Write your software for 100 processor cores,” says Mattson, “and then run it on fewer cores. Your code will work.” Mattson points out that Intel has been in the parallel computing business since 1985, when it started building parallel supercomputers based on (gulp) 80286/80287 microprocessors and floating-point coprocessors. Since then, Intel has underwritten the creation of a variety of parallel architectures, which has gotten Intel membership in the Dead Architecture Society according to Mattson. That guy can sure turn a phrase.

During a quarter century of parallel computing development, Mattson has seen many parallel programming fads come and go. He’d like for us to avoid going down roads that we have already established as dead ends. For one thing, says Mattson, we are not going to find a way to automatically distribute an arbitrary chunk of software across multiple processors. At least not in the foreseeable future. This is the famous “parallel programming problem” and Mattson says that our only hope is to get programmers to write parallel software “by hand. After 25+ years of research, we are no closer to solving the parallel programming problem.” Yet only a tiny fraction of programmers write parallel code.

“History repeats itself while historians repeat each other” (Philip Guedalla 1889-1944)

Computer scientists are dismal at remembering the past, says Mattson. They can’t even spell the word literature. So Mattson raises the banner of computer history to try to remind people of the noble, failed experiments in massively parallel programming with the hope that we can avoid remaking these same mistakes. Here are his five key points:

1. Parallel systems are useless without parallel software.
2. “If you build it, they will come,” is not true here.
3. We can’t generate parallel software automatically, even though people still try.
4. Our only hope is to get programmers to write parallel software by hand.
5. After 25 years of research, we’re no closer to solving the “parallel programming problem.”

Next, Mattson demolished another favorite idol of computer science: the parallel programming language. It’s a well-known trait of computer scientists that they will try to solve every problem with a new programming language. The parallel programming problem is no exception. Mattson displayed an eye chart listing the names of nearly 250 parallel programming languages developed just during the 1990s. “This is silly,” said Mattson, “If creating a new language was the solution, the problem would already be solved. This is not the path to a solution.”

Then Mattson cited the Draeger Grocery Store experiment to prove his point. In this experiment, two jelly and jam displays were set up in one of the San Francisco Bay area’s Draeger’s grocery stores. One display had six types of jellies and jams. The other displayed 24 types. Although consumers examined more product in the display with more choices, they bought more product from the display with fewer choices. The conclusion: fewer choices lead to more sales. For parallel programming, the lesson is that having 250 programming language choices leads to paralysis. Yet there is a parallel programming paradigm that works: MPI, a message-passing API that works with existing, non-parallel programming languages that programmers already know how to use with existing languages.

So here’s Mattson’s bottom line: Let’s do it right this time. “Let’s stop taking potshots at each other’s APIs and adopt a more disciplined, scientific approach. Science is a community process. If we want to make progress on programmability, we need to:

• Develop a systematic, human-centered model of how programmers solve parallel programs
• Define a human-language of programmability—so we can objectively discuss the pros and cons of different programming technologies.
• Define metrics so we can track progress and make systematic comparisons between APIs.

To that end, Mattson points to his book, Patterns for Parallel Programming, as a starting point. He then invited the workshop to join in peer review and experiments to validate his theories.