Via David Eppstein, I find out about the Workshop on Theory and Multicores. A memorable citation from the call:
[...] 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.Which theory community? The one that thinks our machine models are not robust enough to tell the difference between O(n lg n) and O(n5)? The one that thinks nO(1/ε^2) is polynomial and even efficient? The one that thinks Amazon should be happy with an O(lg3n) approximation for its profit? The one that thinks the coolest conclusions we ever came to are the philosophical implications of interactive proofs and zero knowledge?
The theory community will do just fine, thank you very much.
As for "the low level of current activity" being incompatible "with past involvement of theorists in parallel computing" --- it is exactly the past involvement that led to the current attitude towards parallel computing! Parallel computing is the fabled field where we got burned badly, and the first example people use to argue that theory is still very young. (It usually goes like this: "Imagine an equivalent of Perelman disappearing for 20 years and coming back with an answer to the most burning question about PRAMs from 1985. Who would care now?").
It's going to be hard to regain enthusiasm about parallel computing, as timely as the moment may be.
But at least we learned our lessons. Never again will a hyped-up mob of theorists rush head-on to study a machine model too early. Never will we study a machine model before such computers are even built, and while the practicality of such computers is still debated. We understand that producing a theoretical model too early will have us chasing the wrong rabbits, and that our results might be as relevant as the 5-state 17-symbol universal Turing Machine was in the design of the Pentium.
Alright, enough of this. I should go back to reading about 3-round quantum interactive proofs with entanglement.
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
23 comments:
You left out the part about parallel algorithms also being useful as a way of slowing down geometric optimization algorithms by replacing fast and easy to implement binary searches with slow and complicated parametric searches.
This post made me laugh out loud. Way to go, Mihai!
to know love is to know mihai
I was under the impression that all this multi-core stuff can be reduced to questions about compressed sensing. Since there is enough theoreticians invovled with CS, there is really no point wasting our time on current technology which is clearly bound to be replaced by some other technology in the next 60-1000 years, before we will really have a chance to understand what the real problems are.
there is really no point wasting our time on current technology which is clearly bound to be replaced by some other technology in the next 60-1000 years, before we will really have a chance to understand what the real problems are.Since the point went right past you, let me rephrase it in plain language. Yes, we should really be studying parallel algorithms now. No, we shouldn't have studied them so intensely 20 years ago; we wasted a lot of time for little gain. No, it's not going to be easy to start again given that so many people developed an allergy to the words "parallel computing."
Yes, quantum computing is heading down the same path. I don't expect (industry-relevant) quantum computers in the next 20 years, so I expect the TCS trend to kill itself before it becomes useful.
Also, if a quantum computer is ever built, it seems likely that the real complexity measures will not be what we expect them to be today. Then, a lot of our effort will have been wasted. And many people will have developed an allergy for the field --- ensuring that we always study things at the wrong time.
"ensuring that we always study things at the wrong time."
Mihai, I'd love to be enlightened: when's the right time to study things?
Mihai, I'd love to be enlightened: when's the right time to study things?You know what they say about general rules: as a rule, they always fail. This doesn't mean you cannot tell that some particular time is bad.
Mihai, I really don't think the theory community's involvement with PRAM was such a disaster. For one thing, it led to measures of decision-tree complexity (certificate complexity, block sensitivity, etc.) that play a crucial role in quantum query complexity. :)
More importantly, we understand exactly what it is about the PRAM model that made it unrealistic: latency (or to put it differently, the fact that the speed of light is finite). Furthermore, anyone who was thinking about it from a physics perspective would have seen that right away (and I'm guessing some did).
In the case of quantum computing, we are thinking about it from a physics perspective, yet neither the computer scientists nor the physicists have figured out how to break current physics so as to make QC not work. At the least, the discovery that QC is impossible (or even that we had the wrong model for it) would cause a revolution in physics -- it won't just be a matter of reminding people about the speed of light or something. Do you not see that as a significant difference between the two cases?
If you think from the perspective of an engineer, then surely Mihai is right. Every research (and in every discipline, e.g., literature) should be attached and inspired by technological demands of the civilization in which the researcher works.
But this is really begging the question. Most research is not done under this dogmatic view, or else we would have only engineering, business management, medicine and law schools.
In fact, most scientific research begins with the dogma that science is meant to explain the phenomena it investigates. In this sense, the theory of computer science is meant to explain different aspects of computing, regardless of the fact that someone has some financial interests in advancing certain technologies.
PRAMs clearly overhyped, and Mihai's fictional Perelman example best illustrates this. The field will be better of if researchers are mature enough to admit when we went astray, rather than try to deny the obvious.
This troubles me about Uzi's proposal. From a distance it seems that he sees multicores as a complete validation of PRAM research in the 80s. If so we have learnt nothing from that experience.
The proper thing to do is to cherry pick results and lessons from that era, e.g. ignore latency and programming difficulty at your own peril and use the good results such as those listed by Scott to propose a new theory that is relevant to multicore computers.
"Since the point went right past you..."? Did it? Or did you miss my point? (60-1000 years should have been a hint.) The debate continues...
And PRAM research lead to some very elegant and beautiful algorithms. Some of this research must have been useful for distributed computing...
It appears that only one negative comment above was not answered in the computation complexity blog http://weblog.fortnow.com/
The comment is:
This troubles me about Uzi's proposal. From a distance it seems that he sees multicores as a complete validation of PRAM research in the 80s. If so we have learnt nothing from that experience. The answer to this comment is that its premise is wrong. Uzi never claimed that complete validation of PRAM research exists. Only a very signficant validation of key components of it.
Scott,
I really don't think the theory community's involvement with PRAM was such a disaster.Of course not. Take some intelligent people and force them to work on converting iron to gold, and they might just discover some interesting things in the process (like gunpowder). That doesn't make it a good style of doing research.
we understand exactly what it is about the PRAM model that made it unrealistic: latency (or to put it differently, the fact that the speed of light is finite).Here is where we diverge. If you think of PRAM as modeling the hardware on the Pentium chip, one reason PRAM is unrealistic is indeed latency (in other words, long wires are different from short wires). But the main issue is that the hardware industry decided long ago to build universal hardware -- so they simply don't care about our PRAM algorithms for maximum flow in a planar graph.
If you think of PRAM as an abstraction for parallel programming, this is a different world. The focus of PRAM is entirely wrong here. We cannot afford to synchronize processors at gate-level granularity, so the optimal depth on a PRAM is not too meaningful. On the other hand, PRAM totally ignores communication cost, which are a game changer.
neither the computer scientists nor the physicists have figured out how to break current physics so as to make QC not work.I am not Oded Goldreich, by the way. Quantum phenomena are certainly true, and they might scale (from a scientific, engineering, and economic perspective) to be usable in computing. It's just that we don't have much clue how that computer model will look like, and what the bottlenecks will be.
Who knows, quantum computing may fail economically because preparing some n-qubit state requires O(n^6) cubic meters of vacuum around. That bottleneck will clearly become an intellectually interesting issue.
Why not wait and see what the real issues are? If we're too trendy now, we'll make it hard to go back and study the real issues when time is ripe.
Anon 6:08am,
If you think from the perspective of an engineer,Much of my work is in lower bounds. I challenge you to find the true engineering value of these :)
In fact, most scientific research begins with the dogma that science is meant to explain the phenomena it investigates.Correct. But there is an infinity of models and problems to ask. Which ones should we strive hardest to explain? There is much benefit in focusing on something connected to reality.
By contrast, mathematicians are often a self-centered species, where a new direction can be argued for by pointing to connections to previous things they studied themselves. I do not have much respect for their achievements in areas that do not mean anything to me.
Anon 60-1000:
Thank you very much for your hint. In the same spirit, may I also give you a hint? Sarcasm, which I suspect you may be trying to engage in, is most effective when understandable. What is that model that may change in the next 60-1000 years?
The Word RAM? I would certainly agree.
The PRAM? It proved itself inappropriate 20 years ago. (Though of course, some interesting algorithms were invented, and some ideas will be rescued.)
Quantum computing? Which computer?
technically this is a very disappointing discussion.
Even following the 2pm Anon comments that you need to read the posting on the Computational Complexity blog to find answers for all the negative comments posted here, Mihai went ahead with 2 flawed comments. One implying that PRAM implementation requires tight synchrony. The second is that it is completely hopeless to provide the needed bandwidth for PRAM-like implementation.
The UMD XMT hardware platform addresses both issues using a hardware platform that one can build today. It was demonstrated in a 64-processor hardware prototype. The bandwidth issue was addressed in publications on the interconnection network at DAC and Hot Interconnects.
Thank you anon, you just made my point. Parallel computing will be hard to pick up today because the past trend has produced so many blind people on both sides of the issue (PRAM fanatics and PRAM haters).
Whether or not your wonderful UMD machine can implement a PRAM is somewhat orthogonal to the discussion. The deep question here is: how should the new parallel computers look like? "Like a PRAM" may be a valid answer, but let's explore our options first (while keeping an eye on the market).
I fully agree with the last comment that Mihai posted.
--Same Anon.
Uzi never claimed that complete validation of PRAM research exists. Only a very signficant validation of key components of it.He doesn't come across this way when he makes comments like the UMD being a successful implementation of the PRAM and his take on the LOGP paper.
Sarcasm, which I suspect you may be trying to engage in, is most effective when understandable.I disagree. Sarcasm is a tool to make people think about their basic assumptions. It does not have to be understandable, or even make a coherent point. It does have to point out contradictions between held beliefs and reality.
BTW, 64 processors architecture is not PRAM. For PRAM to work you would need thousands or millions of processors in the same machine (think about GPUs). Similarly, 10 qbits do not make an interesting quantom computer. And three sarcastic comments on a discussion do not form a useful contribution to a discussion...
I tend to view the PRAM episode of the TCS community in the 1980s as a success not a failure: it gave a convenient model on which to design massively parallel algorithms and enabled the community to reach a pretty clear picture of the basics of ultimately parallel computation: NC vs. P; very efficient parallel problems (on lists, trees, and related to undirected connectivity) vs. somewhat efficient ones (related to directed connectivity and worse), and a highly powerful model that may be simulated by more reasonable ones (like the butterfly network). The model is realistic in the basic sense as it is very close in complexity to circuit models, etc.
Those who are disappointed by the model seem to have expected it to be a realistic model of actual programming (like a programming language) which, while desired by some (like Uzi), is certainly not the main reason for studying it. Any decent graduate class on PRAMs started with the caveat listing the basic issues that the model ignores on purpose. At a certain point, the basic insights that could be drawn from the model were exhausted, more of the work on PRAMs became un-illuminating, and so the model was quietly abandoned in search of models that can provide new insights.
I tend to view the PRAM episode of the TCS community in the 1980s as a success not a failure: I see PRAM research as I do AI research in the 70s-80s: important foundational work which was overshadowed by overly optimistic projections of its applicability.
I have a view of the PRAM episode similar to Noam's - it was a public relations failure but a research success. Many new ideas, algorithmic and otherwise, were developed in the name of PRAM research that are useful today - many more than Scott credits.
I dispute Mihai's assertion that theory should not have jumped into parallel computation at the time it did. Starting in the late 1970's, real parallel machines were being built and designed. The long term need for parallel solutions was clear. Routing algorithms that could make some of the abstraction possible had been developed. Between the late 1970's and early 1990's, parallel computation was viewed as one of the key waves of the future in both theory and computer architecture communities. Theory was working towards an understanding of parallel computation and the PRAM was merely a convenient vehicle - and a highly appropriate one given the freedom of thought that it enabled. By 1990, though, it was clear that the innovation driven by commodity processors was so great that it would outstrip any advantage of parallel CPUs in the short term, given the latter's greater complexity and difficulty for programming. All work on the theory of parallel computing suffered, not just PRAM research.
Despite all this, as Noam says, the collapse of theoretical parallel computing research came mostly because the rate of real progress in the area slowed dramatically despite increasing numbers of researchers into the early 1990's. Instead, other vistas opened up by the PCP theorem and new approaches to approximation algorithms became vastly more attractive for theoreticians.
Jumping ahead to the multi-core machines of today, the hard issues seem ones of good programming models rather than algorithm design (which was the focus of PRAM research). We do have more refined models than the PRAM, such as the Scan model, that might be decent starting points. On the algorithmic side, the interesting unexplored vistas for multi-core systems seem less clear. As someone who worked on parallel algorithms and models in the 1980's, I see more algorithmic interest in the distributed parallelism inherent in MapReduce than I do in multi-core.
Post a Comment