5
$\begingroup$

Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, even if the machine has multiple processors.

Now, suppose we wanted theoretically to write a "parallel compiler", which would analyze such a program and figure out what operations are safe to execute concurrently, and output an executable which would run in parallel on multiple processors, so that, no matter the timing between these threads, the program in the end will come up with the same results as with "serial compiler".

I am guessing that such a compiler, if possible, would need a very long time to calculate - I am guessing that the problem "parallelize an arbitrary program" must be at least NP-complete (possibly exp). Is that known, and if so, is that true, and if so, can you point me to a published argument?

Let me try and formalize the problem better. Assuming each instruction emitted by the compiler executes in unit time, then for a given number of processors, and assuming the processors communicate and access memory instantly, given that some instructions will depend on others, there is theoretically the shortest possible time to complete the program.

Let's say we want our compiler, maybe not reach this theoretical limit, but come up with instructions that will take up to 2x the theoretical limit.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ It would probably depending on how you formulate the problem, but I suspect it's formally undecidable for most interesting models. In general, how "parallel" a program is may depend on its input data. Consider, for example, a program which needs to operate on the topological order of a graph. If the input graph is disconnected, it's perfectly parallel. If the input graph is a single clique, then it's inherently sequential. $\endgroup$
    – Pseudonym ♦
    Commented Jul 4, 2016 at 4:49
  • 1
    $\begingroup$ @MarkGaleck You seem to have created two accounts. See here for how to merge them. $\endgroup$
    – Raphael
    Commented Jul 4, 2016 at 9:03
  • 1
    $\begingroup$ Can this situation be reduced to halting problem ? If your compiler tries to run commands to see if they are dependent on any other command, it is undecidable if your compiler will even terminate or not. $\endgroup$
    – atakanyenel
    Commented Jul 4, 2016 at 18:06
  • $\begingroup$ @Atayenel no I am not trying to run commands to decide dependencies, I don't think this is needed - can't you just say, OK, instruction a reads variable x, instruction b writes it, a is after b in "serial" mode, so a depends on b. $\endgroup$
    – Mark Galeck
    Commented Jul 4, 2016 at 18:56
  • $\begingroup$ re "formulating the problem" this is connected to the P =? NC question ie open question in complexity theory $\endgroup$
    – vzn
    Commented Jul 5, 2016 at 15:26

2 Answers 2

Reset to default
5
$\begingroup$

It is not clear what exactly you want of that compiler, so let me explore several possibilities.

Optimize the parallelism

This is impossible. Optimizing even sequential runtime is not computable, and a similar proof shows the same for parallel runtime. The proof also extends to any notion of "almost optimal" like within a constant factor or something similar.

Thus, any notion of parallelization in this direction is not even in NP, and it's not even close.

Get some parallelism

Without defining exactly what "some" means we can not classify the problem in terms of complexity. There are certainly things that modern compilers can do, for instance vectorize suitable for-loops -- but all of these are certainly not NP-hard to detect (or they wouldn't do them).

I'm certain that you can carefully define some parallelization feature that is NP-complete to detect. I'd especially look towards coarse-grained parallelism, though exploiting that requires serious rewrites of code.

Do anything

That's trivial and hence boring. For instance, standard data-flow analyses will identify (sub)sequences of statements that are independent and can thus be reordered or, in principle, be executed in parallel. This will get you some very fine-grained parallelism that may not even gain you a speed-up, and will certainly not scale to many processors, but well.

Some language have features to tell the compiler that two things are independent, e.g. method calls, and that way lies potential gain. Then it's easy for the compiler again, though.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ OK thank you, I did upvote, but have you read the section in my question " Added after comment of D.W.", I think I explain exactly what is meant by "parallelize". $\endgroup$
    – Mark Galeck
    Commented Jul 5, 2016 at 10:41
  • $\begingroup$ @MarkGaleck Yes. That falls under "do anything"; create a dependency graph and execute the disconnected components in parallel. $\endgroup$
    – Raphael
    Commented Jul 5, 2016 at 10:43
  • $\begingroup$ no, under my definition, this would not work. Consider that we have 100 instructions that are all independent, and one instruction depends on all of them. If you have 100 processors, the shortest possible time is 2, so by my definition, 4 or under is OK. With your solution, there is one component and the time (serial) will be 101. $\endgroup$
    – Mark Galeck
    Commented Jul 5, 2016 at 20:07
  • $\begingroup$ Okay, so we use topological sort to get the sets of instructions that can be executed in parallel. That's a boring problem and is likely to not yield any gains in practice since the overhead will be way, way higher. $\endgroup$
    – Raphael
    Commented Jul 6, 2016 at 7:56
2
$\begingroup$

You'd need to define exactly what you mean by "parallelize". Besides, finding a parallelization (what a compiler is presumably asked to do) is a search problem, while NP is a set of decision problems. Search problems can't be "NP complete", they are a different kettle of fish. Sure, problems in NP often have corresponding search problems (see for example Bellare's "Decision vs search"), and if one is hard the other is too. Let's be loose with language and talk about "NP hard search problems" if the corresponding decision problem is NP hard.

Compilers "solve" NP hard search problems as a matter of course all over the place. But they usually only consider a subset of the full problem (lower-hanging fruit, if you will), use approximate solutions, or outright heuristics that "usually work in the programs seen in practice". A fascinating glimpse at the problems tackled and how they are addressed is given by one of LLVMs researchers, John Regher in his blog.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.