# Can any algorithm efficiently be implemented as a SIMT problem?

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).

• Thanks for the helpful questions. Please see edits above. – user2398029 Feb 5 '16 at 1:33

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.