Export to
Monday, October 24, 2011 at 2:55pm and last updated
Monday, October 24, 2011 at 4:18pm.
Everything you know (about Parallel Programming) is wrong!: A wild screed about the future
Access Notes
Building is at 4th and College. Room 86-01 is in the basement, take the elevator or stairs down to basement and follow the signs.
Enter at 1900 SW Fourth Avenue. Take the stairs to the basement and turn right. Go to room 86-01.
Website
Description
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, Vrije, 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!