GPUs have a smaller instruction set than a CPU does, but that means that from an architecture POV all the instructions in a GPU have a combination of slower CPU equivalent instructions?
I agree with @pmw1234, there is no theory. The intrsuction sets on CPU and GPU are both Turing complete, therefore CPU/GPU can do, in theory, whatever the other can. I found a dicussion for this on Quora, maybe you will be interested.
Note that, for one single thread, GPU processes slower than CPU (on average, device dependent) and it is much less flexible. GPU achieve its acceleration via a large number of concurrent threads (organized in warps -> blocks -> grids) processing the same or similar tasks, which resembles to SIMD in the CPU context. There are a few things that could make GPU much faster than CPU for some of the tasks:
- Large scale GPU-thread-based parallelism (therefore, SIMD-like processing)
- Latency hiding, I believe this would be a good reference: latency hiding
- Memory management (shared / texture memory) / asynchronous load & store
- Stream-based multiprocessing
Actually to the best of my knowledge, GPU threads can be very limitted for some tasks. For example, it does not perform as efficient as CPU threads when the program focuses more on branching logics than data-driven computation and large-scale similar simple tasks. There is a concept called "warp divergence" describing that when different threads in a GPU warp diverge during if-else branching, these threads could be serialized. Therefore, if your code (task) relies heavily on branching, you should be very careful when coding on GPU. A simple example is "select-like" function.
CPU however, is well-designed for handling context changing, the switch between multiple processes, branch prediction and out-of-order execution (therefore well pipelined) therefore each core can process very sophisticated tasks independently. As a simple analogy, a CPU is like a handful of extremely efficient workers who can work independently while a GPU is like a large number of normal workers who work well in groups. Both of them are similarly capable while they focus differently.