The New York Times had an article today about multicore chips, entitled "Faster Chips Are Leaving Programmers in Their Dust ":
In the future, Mr. Mundie said, parallel software will take on tasks that make the computer increasingly act as an intelligent personal assistant.
"My machine overnight could process my in-box, analyze which ones were probably the most important, but it could go a step further," he said. "It could interpret some of them, it could look at whether I’ve ever corresponded with these people, it could determine the semantic context, it could draft three possible replies. And when I came in in the morning, it would say, hey, I looked at these messages, these are the ones you probably care about, you probably want to do this for these guys, and just click yes and I’ll finish the appointment."
There are those who argue that there will be no easy advances in the field — including some inside Microsoft.
"I’m skeptical until I see something that gives me some hope," said Gordon Bell, one of the nation’s pioneering computer designers, who is now a fellow at Microsoft Research. Mr. Bell said that during the 1980s, he tried to persuade the computer industry to take on the problem of parallel computing while he was a program director at the National Science Foundation, but found little interest.
"They told me, 'You can’t tell us what to do,'" he said. "Now the machines are here and we haven’t got it right."
This controversy brought to mind a lengthy white paper from UC Berkeley that I have been pondering for some months now. The white paper is called The Landscape of Parallel Computing Research: A View from Berkeley. Although the paper is not new, the insights it provides are more than relevant to those of us not on the very bleeding edge of computer engineering, where solid-state physics and computer science meet materials science and computational linguistics.
From the Berkeley paper:
We believe that much can be learned by examining the success of parallelism at the extremes of the computing spectrum, namely embedded computing and high performance computing. This led us to frame the parallel landscape with seven questions, and to recommend the following:
- The overarching goal should be to make it easy to write programs that execute efficiently on highly parallel computing systems
- The target should be 1000s of cores per chip, as these chips are built from processing elements that are the most efficient in MIPS (Million Instructions per Second) per watt, MIPS per area of silicon, and MIPS per development dollar.
- Instead of traditional benchmarks, use 13 "Dwarfs" [sic] to design and evaluate parallel programming models and architectures. (A dwarf is an algorithmic method that captures a pattern of computation and communication.)
- "Autotuners" should play a larger role than conventional compilers in translating parallel programs.
- To maximize programmer productivity, future programming models must be more human-centric than the conventional focus on hardware or applications.
- To be successful, programming models should be independent of the number of processors.
- To maximize application efficiency, programming models should support a wide range of data types and successful models of parallelism: task-level parallelism, word-level parallelism, and bit-level parallelism.
- Architects should not include features that significantly affect performance or energy if programmers cannot accurately measure their impact via performance counters and energy counters.
- Traditional operating systems will be deconstructed and operating system functionality will be orchestrated using libraries and virtual machines.
- To explore the design space rapidly, use system emulators based on Field Programmable Gate Arrays (FPGAs) that are highly scalable and low cost.
Since real world applications are naturally parallel and hardware is naturally parallel, what we need is a programming model, system software, and a supporting architecture that are naturally parallel. Researchers have the rare opportunity to re-invent these cornerstones of computing, provided they simplify the efficient programming of highly parallel systems. [italics added]
Pondering this raised a question in my mind with which I have struggled for some length of time now; I haven't written about it because I don't feel qualified to provide an answer, in fact haven't even formed a useful opinion to share. The NY Times article makes me think it's time to raise the question to my readers, whether or not I have yet come up with an answer or even a useful contribution to the process of finding an answer.
The question concerns the relationship between natural language and programming languages. In the halcyon (or should I say Jurassic?) days of programming, when FORTRAN, COBOL, ALGOL, and BASIC ruled the world, the correspondence between natural and programming languages was very close. Describing an algorithm in narrative form was highly intuitive. We wrote pseudocode to describe problems. If we wanted to be fancy, or to justify the almost embarrassingly high salaries people were paying us, we drew flow charts, data flow diagrams, or hierarchically-structured decomposition diagrams. These, however, were easily described in a narrative.
My question is this: does the narrative paradigm hold, or are we about to face a transition to an entirely new way of looking at electronic computation as a problem-solving medium?
This feels very reminiscent of evolution of physics: the Newtonian laws of motion closely model our intuitive view of the universe. Newton's co-discovery of the calculus, though, shows that he understood the paradox of intuition. His physical laws may have been intuitive (for the most part), but for most of us, calculus isn't. There is a classic 'aha!' moment for most calculus students, after which it makes a lot of sense. That the 'aha!' moment does come for most bright students is a good thing - it is necessary to use calculus to fully describe the operation of Newton's laws in the real world. Many people never experience that 'aha!' moment, and never need to.
Complications set in
Then along comes Einstein, and we realize that our 'full description' of the natural world is actually partial, and breaks down rather rapidly as one approaches the macrocosmic and microcosmic extremes. The interrelationship of time and space? Gravity as (in effect) a bending of space rather than a force per se? Such concepts were only the start of a series of increasingly arcane fly-bys whizzing out of the world of physics over the heads of the hoi polloi - a polloi that included many in other realms of science. Following closely on Einstein's heels, Heisenberg managed to come up with new physical concepts that did a fly-by over even Einstein's head. Schrödinger's cat was out of the bag, so to speak, in spite of still being inside the box.
Algorithmic programming has faced a similar crisis already with the rise of object-oriented programming (OOP). OOP was to algorithmic programming what calculus was to the Laws of Motion: it required a sudden 'aha!' moment for most of us before we understood what was going on and how we could write programs in the new paradigm. But for many programmers, especially those from the Baby Boomer generation, that 'aha!' moment never happened. Even when programming in modern languages that support but do not require an object-oriented approach, these programmers write purely algorithmic code.
They may be writing utilities to be run from the Unix command line, for example, or operating in a framework that in effect handles the object orientation for them, such as the Common Gateway Interface, or CGI. CGI scripts are handlers for events generated by a Web browser, which is essentially an object-oriented user interface framework. A CGI programmer does not need to know much about how a browser operates. An understanding of HTML forms and the business logic of the back end system are all that s/he needs to get by. Each CGI script is a narrative about what to do when event X happens, where X is (generally) an end user pressing a button on a form.
In CGI, cookies are used to keep track of the necessary session state - cookies essentially being nothing more than global variables. For the object-oriented programmer, the objects themselves maintain their state, and program execution involves a bunch of objects interacting with each other. Instead of a monologue narrative, we end up with something more like a play. Actors speak (i.e. send messages) to each other, triggering action on the part of the listeners (i.e. message recipients) that cause them to take actions of their own, actions that often involve new messages, thus furthering the plot line.
A brave new world
In the realm of human-computer interaction, and in protocol-compliant computer-computer interaction over networks like the Internet where servers may have no prior knowledge of their clients, arbitrary inputs from the real world can drive unexpected state changes in our system objects, and we run into problems the algorithmic programmers never had - deadlocks, livelocks, race conditions, and so on. These problems have one thing in common - they are problems that arise out of parallelism.
Programmers of operating systems and database management systems have been dealing with these problems for years - for example, Concurrent Euclid, the Unix System and Tunis by R. C. Holt, first published back in 1982, gives lucid and often entertaining descriptions of the problems of parallelism and how to solve them. Programmers who wanted to work in these realms usually started out mystified and then had their 'aha!' moment; if it didn't happen, you weren't allowed into the inner sanctum (known as "Ring Zero" or "Kernel mode" in some of my favorite operating systems), and had to go back to algorithmic or object-oriented applications programming.
It has been conventional wisdom for some time now that compilers could be made smart enough to hide parallelism from programmers. In general that has proven true in the realm of supercomputers, but mostly in cases where there was a lot of natural parallelism in the problem domain. Multi-core chips, and their many-core descendants soon to come, will test that wisdom in the realm of applications programming. Microsoft and the chip manufacturers are betting the farm on this, as well they must if Moore's Law is to continue to apply.
Compilers translate a human-understandable narrative into machine-readable code. To parallelize a human narrative in a way that optimizes the resources of a multi-core system, compilers are going to need to be a lot smarter than we have been able to make them thus far.
I'll try to come back to this in the near future and look into some of the Berkeley folks' opinions about the breakdown of some axioms of conventional wisdom in the emerging world of highly parallel mainstream computing. For now there are more questions than answers, but the questions are crucial to the evolution of computing in the next decade or two.
Comments