Can any algorithm efficiently be implemented as a SIMT problem?

Question

Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions.

Excluding overhead due to hardware limitations (specifically, memory copy times when using a GPU) - are there algorithms whose efficiency can only be made worse in a SIMT model? By "efficiency," I mean here the total number of elementary operations / # parallel processing elements.

(Assume that each individual compute element in the SIMT model is (made to be) exactly as fast as the single compute element in the sequential model. Therefore, computing time is the same as the number of elementary operations.)

Asked another way, can any algorithm be made at least as efficient using SIMT instructions than it could using sequential instructions? Again, I'm purely talking about computing "time" here - not set up / memory copies (which are the typical reason why you wouldn't use a SIMT processor for a highly sequential problem AFAIK).

Answer 1

No, efficiency cannot be strictly worse, for trivial reasons. For instance, you can have all $n$ threads independently compute the same thing -- each doing the same thing that the sequential computation would have done.

This is not very interesting or useful in practice, for a number of reasons: (1) in practice, in SIMT architectures each individual compute element is typically less powerful than the compute element in a sequential system; (2) we care not just about compute time but about energy usage, and wasting energy on pointless computation would be, well, pointless.

At the same time, it is true that there are computational tasks that are inherently sequential: they cannot be sped up on a parallel processor (including a SIMT machine). See, e.g., Which algorithms can not be parallelized?, https://crypto.stackexchange.com/q/606/351.