The current reality is that non-theory communities (architecture, compiler, applications) nearly ignore the role of the theory and algorithm communities when it come to ongoing reinvention of CS for parallelism. As you know, this reinvention is mandated by the transition to many-core computer driven by technology and market forces and will affect how CS is taught at all level, including freshmen programming, courses on algorithms and data structures, etc. It will be a pity for all if theory remains out of the discussion. For example, it can adversely affect the future of the theory and algorithms communities, as claims of relevance of theory to CS will become harder to support.
Here is one step to bridging the gap: Workshop on Theory and Many-Cores: What Does Theory Have to Say About Many-Core Computing?
WHEN: Friday, May 29, 2009
WHERE: Kim Engineering Building, Room 1110, University of Maryland, College Park, Maryland
The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse. For example, 19 out of 38 participants in a December 1988 NSF-IBM Workshop on Opportunities and Constraints of Parallel Computing in IBM Almaden had theory roots. The lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.
The main objective of the workshop will be to explore opportunities for theoretical computer science research and education in the emerging era of many-core computing, and develop understanding of the role that theory should play in it.
The workshop will feature five invited talks and several contributed presentations.=20
Deadline for submitting an abstract: April 27, 2009.
List of speakers:
- Guy Blelloch, CMU
- Phil Gibbons, Intel
- Arch Robison, Intel (Architect of Intel's Threading Building Blocks (TBB))
- Leslie Valiant, Harvard
- Uzi Vishkin, University of Maryland
Sponsors: The University of Maryland Institute for Advanced Computer Studies (UMIACS)its Electrical and Computer Engineering Department, and the Center for Computational Thinking, Carnegie-Mellon University
This advert is a rather gloomy, harsh pronouncement: "change your ways, theorists, or become irrelevant."
ReplyDeleteIt's not clear to me whether it's wise to heed this call (I share some of Mihai's reservations in his recent post), but beyond that, shouldn't multicore proponents also try to make a case that their gizmos actually pose truly novel and interesting questions for theorists?
We want to avoid rehashing issues that were essentially studied before with PRAM models.
Tempt us with some simple (if idealized) new models, and compelling open problems in these models; then we'll talk.
For example, it can adversely affect the future of the theory and algorithms communities, as claims of relevance of theory to CS will become harder to support. This sentence seems to imply that "theory" is external to "CS" and its relevance to CS is already questionable, and will be even more so in the future. Probably this is not so bad.
ReplyDeleteThe position of "theory" wrt CS is analogous to that of mathematics with respect to physics. Much as the physicists love to castigate the useless pursuits of mathematicians (trying to "prove" facts that every physicists "know") they can't also do without it. The mathematicians on the other hand appreciate and love the connections with physics, but in no way do they tie their existence to the tender mercies of the physicists. So be the relations between "theory" and "CS".
I think that comment #1 misses the statement that critiques vendors as well:
ReplyDeleteThe lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.
Namely, the workshop announcement does not "put the blame" on one side. It rather reflects the current reality where communication between theory/theorists and vendors is lacking. It then seeks to start a dialogue for correcting it. What is wrong with that?
The analogy to Physics versus Mathematics misses the fact that CS is "man made". In fact, the main reason for the workshop is that we are currently in the midst of the formative stage of this man-made reinvention of CS. It is not clear at all which approaches vendors will pursue. More importantly, it is not clear whether they will succeed. What is wrong with trying to articulate to vendors why they should care about theory/theorists by presenting to them the benefits of taking the role theory and theorists into account?
My own belief is that if vendors fail to incorporate an agreeable interface for the teaching of parallel algorithms that also connects with the huge PRAM knowledge based that the theory/algorithms community already built, their new many-core systems will fail to reach wide use due to programming difficulties.
Namely, with a more positive/constructive attitude from theorists, the field of algorithms/theory can position itself as the enabler of the new era. Isn't this a nicer place to be than be considered irrelevant for CS? If you agree, come to the workshop.
if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. "allowed"? do we have much say in the matter? Isn't it more of a case that we need to follow whatever the hardware people can and cannot create, with our input restricted more to places where there is truly a choice about what to do?
ReplyDeleteComment #2 raises an interesting question.
ReplyDeleteShould the relationship between theoretical CS (TCS) and CS be similar to the relation between Theoretical Physics and Physics, or should it be more like the relation between Mathematics and Physics as comment #2 suggests?
Perhaps it is not such a good idea for TCS to find itself on eternal vacation from CS.
Comment #4 asks a good question: do we have much say in the matter? Isn't it more of a case that we need to follow whatever the hardware people can and cannot create, with our input restricted more to places where there is truly a choice about what to do? What hardware people can and cannot create indeed defines the realm of possibilities of what can be built. However, this realm is much bigger than many theorists realize.
ReplyDeleteAs a case in point take the well-cited 1993 LOGP paper from UC-Berkeley. That paper stated that the PRAM model is completely irrelevant to anything that can ever be built. Since the paper was co-authored by senior hardware people (Culler and Patterson), many theorists believed this statement, and PRAM-related research nearly stopped.
Interestingly, most theorists missed the fact that the (very nice) 1999 book Parallel Computer Architecture by Culler and Singh
already backed away from this statement. That book ends with a section on Potential Breakthroughs. Page 961 states:
Another breakthrough may come from architecture if we can somehow design machines in a cost-effective way that makes it much less important for a programmer to worry about data locality and communication; that is, to truly design a machine that can look to the programmer like a PRAMThe fact is that we succeeded building a prototype of such a machine at UMD: http://www.umiacs.umd.edu/users/vishkin/XMT/CompFrontiers08.pdf
as part of a project entitled Explicit Multi-Threading (XMT): A PRAM-On-Chip Vision. see http://www.umiacs.umd.edu/~vishkin/XMT/index.shtml
This means that as a theorist you can vote with your feet. You can choose which among the hardware options out there you prefer and collaborate when it comes to your research and teaching choices. For example, if most theorists will chose to teach in their algorithms courses one hardware platform over the others, I can assure you that this will be heard loud and clear by vendors and architects. In fact, they may have no choice.
I hope that this answers your question.
Theorists need to understand that while they do not hold all the cards in this debate they can make a real difference. Theorists do not need to wait for architects to tell them that theory is important in the same way that architects do not need to wait for theorists.
I've put a longer post on this on my blog; but to summarize:
ReplyDeleteI think it's great to have a workshop in this area -- thanks to Uzi -- and I don't understand the negative reaction to their advertisement. Given that computing seems to be moving (rapidly) to multi-core, as a community theory should be getting involved. I'm not saying EVERYONE needs to get involved, but surely some theoretically-minded people should see this as an opportunity to both find new problems and have an impact on computing as practiced in the real world.
I'm perhaps a little less optimistic than Uzi about the potential of theorists to shape this direction, rather than simply to react to it. But who knows? Maybe some theorist will have a breakthrough idea that has a powerful impact. Or we'll have several smaller ideas that have a cumulative impact. And even if not, if multi-cores do become the standard, we will have to react to it, or we will lose some relevance as a community -- I don't see how that can be argued. The risk-reward analysis suggests to me theory should be finding ways to get involved.
Comment #2 raises an interesting question.
ReplyDeleteShould the relationship between theoretical CS (TCS) and CS be similar to the relation between Theoretical Physics and Physics, or should it be more like the relation between Mathematics and Physics as comment #2 suggests?
The most successful and fundamental aspects of theoretical CS are those which are mostly independent of the actual machine models. Examples are the whole theory of computational complexity (P vs. NP), recursive function theory, lambda-calculus etc.
Parts of so-called theory that has been intimately connected with machine-models have been engineering oriented and ephemeral in nature (not to say that these topics were not important during their times). However, the long term contributions of theoretical CS would be those that are independent of computational models.
I suppose that depends on your measure of what constitutes "success" in theoretical CS...
ReplyDeleteAnon #1 here again--I want to say to Uzi and others involved that I am not hostile to the initiative they are putting forward.
ReplyDeleteBut I was trying to point out that the statement struck a mainly negative tone about the state of affairs (aside from questions of blame). Although this may be justified, I think more positive outreach should nevertheless be attempted, in the form of inherently compelling theory questions.
Take the case of quantum computing theory/QIT. The field took off not because everyone believed quantum computing was just around the corner and classical computing would shrivel up soon, but (at least in part) because it became clear with Shor's and other work that quantum computing was really a place where deeply novel and exciting things could happen.
We don't necessarily expect the same degree of novelty from multicore, but I would still hope multicore proponents can make a direct appeal to theorists' intellectual curiosity.
As a case in point take the well-cited 1993 LOGP paper from UC-Berkeley. That paper stated that the PRAM model is completely irrelevant to anything that can ever be built. Since the paper was co-authored by senior hardware people (Culler and Patterson), many theorists believed this statement, and PRAM-related research nearly stopped.This is just not so. PRAM research was on its last legs by the time the LogP paper came out and anyone but the most heavily invested PRAM researchers could tell so from near and afar. If anything the Karp et al. LogP paper was an effort to save what was then turning to be a failed line of research.
ReplyDeleteAttempting to revive the PRAM model wholesale would be a grave mistake. It would evidence of a lack of introspection from the leaders of the field and set the ground for a second, even deeper failure. I hope reason prevails and whatever comes forward from the multicore workshop is inspired by scientific arguments rather than a desire for personal vindication.
First, I think that the workshop has nothing to do with one approach or another. This should be perfectly clear. It is truly intended as an open debate as the announcement indicates.
ReplyDeleteI will be glad to debate the future of the PRAM separately, but since Anon#11 is dragging me again to discussing that. Let me respectfully suggest to him/her the following:
I will be glad to give you an account on the UMD 64-processor PRAM-like machine so that you can try it and decide yourself.
One last comment.
ReplyDeleteI believe that the lively discussion here and in other sites suggests strong interest in the workshop, which is great.
I would like to welcome ANY relevant submission to the workshop by the deadline of April 27, and assure you that the program committee has no party line.
I will be glad to give you an account on the UMD 64-processor PRAM-like machine so that you can try it and decide yourself.I can only echo Mihai's comments here: a 64-processor machine is not a PRAM. People were talking about millions of processors back then and since communication costs grow quadratically, realizing a 64 processor machine says little about the practicality of a 64,000 or 1,000,000 processor machine.
ReplyDeleteThanks for the question. I will briefly review the current status and needs and then address the question.
ReplyDelete1. The 64-processor XMT prototype at UMD scales to 1024 processors and perhaps more. Its main form of programming is PRAM-like, which is much easier than any other current approach. The speed-ups over the best serial implementation exceed 100X (for 1024 processors).
For perspective, note that CS practitioners are "willing to kill" for an improvement of 5%.
A course on PRAM algorithms has been an effective introduction to XMT programming.
The claims above have been validated through real (prototype) hardware, prototype compiler, and the teaching of over 200 people (graduate, undergraduate and high schools students) and, of course, research.
2. This range for the number of processors is also what the high-performance "desktop" industry seeks to provide in the 2010s. Parallelism became the only game in town for performance improvement. Namely, the XMT/PRAM solution addresses a truly burning practical question based on a solution which is rooted in theory, and therefore potentially a great triumph for theory.
3. What about say 100K processors or more?
Indeed no claim is made for 100K processors at this point.
However, through publications and patents (mostly related to Opto-electronics) I believe that I have demonstrated potential for scaling PRAM parallelism to 100K processors and beyond. To make this a reality significant visionary investment from government, of the type that is expected from agencies such as DARPA, is needed.
I presented my initial thoughts on this matter at
http://www.csm.ornl.gov/workshops/IAA-IC-Workshop-08/documents/wiki/presentation-vishkin.pdf
I would like to summarize this discussion as follows. In Physics it is quite common to have 50 years or more between a theory contribution and its practical impact.
By this standard, the fact that PRAM algorithms stand to make an impact in 30 years is truly remarkable.
I believe that if CS theorists can become a bit more appreciative of their own contributions, theory and theorists will be the first to gain. Please forgive me for saying that, but for this to happen more theorists need to improve their understanding of CS practice and its enabling technologies. The minimum should be: (i) be tolerant: do not put down those among theorists who care to do it, since their success needs to be measured differently, and (ii) be patient: understand that the time scale for a real revolution in science is in decades; and if it is not too much to ask (iii) be supportive: this will be wise since you will be able to use such success stories when seeking support for your own future work; IMHO the intellectual challenge of making a theory contribution and transferring it to practice can also be quite non-trivial.
I really hope that nobody will be offended by anything written above statement. My intention is truly constructive.