[Beowulf] Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed about the Future

[Eugen Leitl]

http://splashcon.org/2011/program/dls/245-invited-talk-2

Mon 2:00-3:00 pm - Pavilion East

Everything You Know (about Parallel Programming) Is Wrong!: A Wild Screed
about the Future

invited speakerDavid Ungar, IBM Research, USA

In the 1970’s, researchers at Xerox PARC gave themselves a glimpse of the
future by building computers that, although wildly impractical at the time,
let them experience plentiful fast cycles and big memories. PARC researchers
invented Smalltalk, and the freedom afforded by such a dynamic, yet safe,
language, led them to create a new experience of computing, which has become
quite mainstream today.

In the end of the first decade of the new century, chips such as Tilera’s can
give us a glimpse of a future in which manycore microprocessors will become
commonplace: every (non-hand-held) computer’s CPU chip will contain 1,000
fairly homogeneous cores. Such a system will not be programmed like the
cloud, or even a cluster because communication will be much faster relative
to computation. Nor will it be programmed like today’s multicore processors
because the illusion of instant memory coherency will have been dispelled by
both the physical limitations imposed by the 1,000-way fan-in to the memory
system, and the comparatively long physical lengths of the inter- vs.
intra-core connections. In the 1980’s we changed our model of computation
from static to dynamic, and when this future arrives we will have to change
our model of computation yet again.

If we cannot skirt Amdahl’s Law, the last 900 cores will do us no good
whatsoever. What does this mean? We cannot afford even tiny amounts of
serialization. Locks?! Even lock-free algorithms will not be parallel enough.
They rely on instructions that require communication and synchronization
between cores’ caches. Just as we learned to embrace languages without static
type checking, and with the ability to shoot ourselves in the foot, we will
need to embrace a style of programming without any synchronization
whatsoever.

In our Renaissance project at IBM, Brussels, and Portland State,
(http://soft.vub.ac.be/~smarr/renaissance/) we are investigating what we call
“anti-lock,” “race-and-repair,” or “end-to-end nondeterministic” computing.
As part of this effort, we have build a Smalltalk system that runs on the
64-core Tilera chip, and have experimented with dynamic languages atop this
system. When we give up synchronization, we of necessity give up determinism.
There seems to be a fundamental tradeoff between determinism and performance,
just as there once seemed to be a tradeoff between static checking and
performance.

The obstacle we shall have to overcome, if we are to successfully program
manycore systems, is our cherished assumption that we write programs that
always get the exactly right answers. This assumption is deeply embedded in
how we think about programming. The folks who build web search engines
already understand, but for the rest of us, to quote Firesign Theatre:
Everything You Know Is Wrong!

David Ungar is an out-of-the-box thinker who enjoys the challenge of building
computer software systems that work like magic and fit a user's mind like a
glove. He received the 2009 Dahl-Nygaard award for outstanding career
contributions in the field of object-orientation, and was honored as an ACM
Fellow in 2010. Three of his papers have been honored by the Association for
Computing Machinery for lasting impact over ten to twenty-four years: for the
design of the prototype-based Self language, dynamic optimization techniques,
and the application of cartoon animation ideas to user interfaces. He enjoys
a position at IBM Research, where he is taking on a new challenge:
investigating how application programmers can exploit manycore systems, and
testing those ideas to see if they can help scale up analytics.

[NOTE] this session is organized as a joint event with the AGERE! workshop