Friday, April 17, 2009

Theory and Many Cores Reflection

Since I'm at a lull point at the PC meeting, I'll write another post.

There's a call for a Workshop on Theory and Many-Cores at the University of Maryland the Friday before STOC. (Remember the Saturday before is Valiant's birthday celebration.) There's been some discussion in various blogs (as I note below) about it, so before discussing it, I'll repeat part of the call:

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.
I view this call as an attempt at strong advertising -- this area is important, lots of other areas are working on it, it could be core for the future -- but it seems to have brought some strong negative reactions.

Both Mihai Patrascu and Bill Gasarch have blogged about this. Mihai's post is very sarcastic and (although he clarifies his point in the comment) is not very clear, but his point seems to be that this is something theorists should but won't get involved with, having worked too much in this area in the past (PRAM algorithms) with little success. And there are what I take as negative comments on Bill's post, which seem to say "shouldn't the systems people be explaining to us why this is interesting" and even that theory should be independent of what's actually going on in CS.

I don't think the advertising is over the top at all. There is an unfortuantely-too-small collection of theory-oriented people who like working on problems and algorithms that real people might use. Mulit-core seems to be a rapidly growing area, with potential for interesting challenges. The fact that years ago people got over-excited about what in retrospect (or even at the time) turned out not to be a suitable-for-practice set of models doesn't mean there's not interesting work to be done now. It won't appeal to all theorists, and perhaps this sort of work doesn't meet some (Mihai's?) definition of "fundamental work theorists should be doing". But when there's a burst of activity in area in CS, as a community theory should be there if they can contribute. Exploring the possibilities here is just a good idea. I don't get the negativity, but I do see it as another example of a subset of theorists pushing a separation of CS theory from the rest of CS that's ultimately unhealthy, in terms of our relevance (and related things like funding).

And let's face it -- what's going to happen in multi-core architectures and languages is likely going to happen without the input of theory (and could happen without theory input as all). Does that mean we can't make meaningful contributions or find interesting new problems? Of course not. But if we believe this is the direction computing is going to move (and I hear that an awful lot these days), it does mean that for the theory community to sit around waiting for systems people to come asking for input is not a good idea -- unless the community wants to highlight a lack of relevance and interest in actual computer science as being practiced.


Anonymous said...

I thought Mihai's point was more that the FOCS/STOC community is being hypocritical by, on the one hand, staying away from parallel algorithms because of the past failures of theory to connect to practice and, on the other hand, enthusiastically embracing quantum computing despite the high likelihood of a failure of the theory there to connect to practice.

Unknown said...

Computer Science Community Ignores Industrial Needs, Lets Priorities be set by D.O.D. Funding: Film At 11.

Mihai said...

I agree with what David Eppstein says I am saying :)

It won't appeal to all theorists, and perhaps this sort of work doesn't meet some (Mihai's?) definition of "fundamental work theorists should be doing".There is something fundamental about parallel computing that we have not been able to capture or understand yet. It has something to do with communication, but so far I have failed to come up with a clear explanation of what I have in mind.

But when there's a burst of activity in area in CS, as a community theory should be there if they can contribute.We are trendy enough as it is. We should contribute when we have something interesting to say. And no, we should not engage in the turf wars that are often found in academic "practical areas."

Anonymous said...

I think part of the negative reaction to the call for theorists to get involved in the "many cores revolution" is that TCS (and, for that matter, a lot of CS) is already too influenced by short-term fads that don't quite pan out (and were never thought through to begin with). How about all the work on peer-to-peer networks? Or sensor networks? Or algorithmic game theory? Parallel computing and quantum computing may fall close to this category also.

Mind you, I'm not saying that all work in these areas is useless or that everyone should stay away from working on these topics. What I am saying is that it is dangerous to encourage a mass shift in TCS research in the vague hopes of getting more funding, or of making ourselves "relevant" in the short term (at the expense of relevance in the long term). It seems to me that some of the biggest successes of TCS have been from not following the crowd, and in developing techniques that others have been able to apply.

Unknown said...

About 15 years ago Bilardi and Preparata argued that because of speed of light issues, a computer with a 2D or 3D mesh (grid) of nodes with a logarithmic amount of memory, a little processing power and connections to its neighbors is the best you can do.

This model seems like a good choice for an abstract model of parallel computation, but there's a glaring weakness: they ignore the problem of transferring power into the computer and heat out. In their 2D model the third dimension can be used for heat and power, but it would be more principled to deal with heat and power explicitly in a 3D model. Perhaps one could assume that power must be routed in from infinity, the power density is bounded, and computation takes power? I wonder if these assumptions imply 2D is the best you can do (to within a constant).

Michael Mitzenmacher said...

Mihai -- thanks for the clarification.

Anon 4: I don't think anyone's asking (yet) for a mass shift in TCS research to this topic. What the ad seemed to be pointing out was the near-total dearth of TCS research in the area currently, hence a workshop to get people interested. In particular, for theorists who publish outside FOCS/STOC, perhaps this would be an interesting area to look for new problems...

outside STOC/FOCS said...

In other, non-core theory conferences, mostly SPAA and PODC, there is significant activity related to multi-core algorithms.
Much of it is rather nice theory.

The call-for-participation (and in a sense, also the list of speakers) somewhat ignores this activity.

Uzi Vishkin said...

One last comment.

I 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.

Anonymous said...

You said: "unfortunately-too-small collection of theory-oriented people who like working on problems and algorithms that real people might use".

How does one get involved in working on such problems?