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.