|NP-complete problem in automatic compiler parallelization? email@example.com (1995-06-14)|
|Re: NP-complete problem in automatic compiler parallelization? Martin.Jourdan@inria.fr (1995-06-26)|
|From:||firstname.lastname@example.org (Timothy Williams)|
|Summary:||NP-complete problem in automatic compiler parallelization?|
|Keywords:||theory, parallel, question|
|Organization:||National Energy Research Supercomputer Center|
|Date:||Wed, 14 Jun 1995 07:06:25 GMT|
I have heard of a proof having to do with compilers trying to
automatically parallelize code with general dependencies. The gist was
that there is an NP-complete problem somewhere in there, making
prospects for automatic parallelization look bad.
I recently saw a statement of what was proved somewhere in an online
book or paper on the WWW, but I can't remember where! I don't really
need, and probably couldn't understand the proof, but I would like to
find a correct statement of what was proved.
Please post/email a statement of this if you know it, or pointers to a
book/paper *likely* to have it (I've already spent a bit of time
stabbing in the dark at the library myself).
| Tim Williams (email@example.com 510-423-6278) |
Return to the
Search the comp.compilers archives again.