Theory Matters Wiki

Summary | Rationale | Powerpoint | JPG Slide | JPG Image | Credits | Comments | All Nuggets

Modeling and Exploiting the Power and Parallelism of Tomorrow's Computers

Major changes in the way computers are being built require major revisions in the way computational tasks are abstractly described and reasoned about.

Summary

For the past four decades, the growth in computational power has been achieved by putting more and more transistors on chips: however, this trend (known as Moore's law) seems to be reaching its limits. Today, increased efficiency is being achieved through parallelism, and this trend is likely to continue in the future, with all computing devices likely to have many processors. Given this trend, the single-processor computational models given by Turing and Von Newmann are fast losing their predictive power. What is the right framework in which to design algorithms and programs for these multiple-processor machines?

Rationale

Historically, mathematical models of computing machines have often predated their actual existence. The successful computational models of Turing and of Von Neumann paved the way for the art of computing as we know it today, and still serve as the primary frameworks used to describe and to reason about computing tasks. Indeed, their ongoing success and impact inspires abstraction as a tool to access the future.

The era of the single-processor computer, however, seems to be ended and these fundamental models are less relevant to future computer architectures. Moore's law has turned from delivering more speed to delivering more processors, and parallelism is our way forward. In the future, all computing is best viewed as using many processes. Concurrently with this, massive data sets imply that communication bottlenecks (even within a single computer) and memory speeds are increasingly dominating the cost of computing. Efficient programming for many processors asks that more work be done on them locally, between their expensive communications.

Given these changes, the single-processor computing models of Turing/von Neumann are fast losing their relevance and predictive power; multiprocessor models derived from them are unlikely to scale as multicore processors grow. Good models/frameworks for parallel computing are desperately needed by the industry. For example, application-software vendors may avoid investing in large projects, rather than risk the wrong programming approach.

As an example of past successes, The MapReduce model for parallel systems allows the expressive power from functional programming to mask details of parallelism and communication, leaving the programmer free to specify the essence of massively distributed algorithms. The model is also influenced by work done in the theory community on the parallel prefix operation. . This demonstrates how abstract algorithmic thinking allows efficient programming for the computer architectures and systems of the future.

Contributors and Credits

Anupam Gupta, Rajmohan Rajaraman, Udi Wieder, David S. Wise, Lisa Zhang.

Also incorporated material from Uzi Vishkin's proposed nugget.

Image Ideas

List ideas for possible images. You can also upload images you've find using a command like this Δ.

My wires/calculators picture would fit this version/dswise.

Could be pictures of Turing, Turing machine, and parallel machine.

Comments

• to give feedback on this nugget, just add another bullet to this list.
• Similarly to my comment on the Computing as a Commodity nugget, I feel that the word "abstract" is over-used in this nugget, taking for granted the fact that abstraction is good without really making the case for it (whereas I think the common perception is that it is bad - removed from reality). The summary ends asking for "what is the right abstract framework". We should argue why we'd want an abstract framework at all; what benefits will it bring? The reasons are only mentioned in the last par of the rationale; it'd be good to make them more prominent. - Salil
• It would also be nice to mention TCS somewhere explicitly, eg how we are well-positioned for this effort (perhaps due to past successes like in Uzi Vishkin's nugget idea. - Salil
• Minor comments: "less and less" -> "less", "are increasingly dominant" -> "increasingly dominate the costs of computation". - Salil
• I think that the word "abstract" is indeed somewhat overused. E.g., instead of "abstract framework", one could just say "framework" - Piotr
• I would put more emphasis on "design" rather than "reasoning". E.g., instead of "in which to reason about..", what about "in which to design algorithms and programs for..." ? I think this would be more pragmatic. - Piotr
• Perhaps it would be good to emphasize that good models and frameworks for parallel computing are *desperately* needed by the industry. This is due to the chicken-and-egg problem: software people are reluctant to invest in parallelism because they are afraid to invest in a "wrong" model, while hardware people are reluctant to produce equipment if there is no software designed for it. See Uzi's nugget for more. - Piotr
• In their MapReduce? paper, Dean and Ghemawat credit a paper by Ladner, Fischer, JACM'80, for some of the ideas. Perhaps we can incorporate this as an example of basic research impact.
• Nugget modified. -- Lisa
• I added a reference to the influence of parallel prefix on mapreduce. -- Rajmohan
• Moved MapReduce? link to word "MapReduce?" itself. - Salil
• Note from designer Elaine Park on first design: The practical applications of this idea seem huge and the intention of this design is to capitalize on that appeal. Though the research itself is abstract, the implication of "tomorrow's computers," is a great handle for a pragmatic audience.
• Can the tagline be changed into a question to indicate there are problems to solve. -- Richard
• Tagline was "Major changes in the way computers are being built require major revisions in the way computational tasks are abstractly described and reasoned about." I offer a change as Richard suggests. --dswise
• Uploaded completely revised design. - Salil
• Note from designer Elaine Park on second design: Wanting to focus on the idea of communication between parallel processors while maintaining the futuristic look and feel led me to this. Using simple metallic spheres as stand-ins for processors puts the emphasis on their repetition, as well as the links between them.
• Actually, personally I prefer the old tagline - it sounds more catchy and convincing, with the repetition of "major" and its natural rhythm. - Salil
• The old tagline is back. (The new tagline was "How should we be describing computational tasks and algorithms to perform them, in order to take best advantage of major changes in computer architectures?") -- Lisa