This can arise from architectural factors:
If the same memory bandwidth is available for both one or more processes, then you will see almost no speedup since SpMV and related linear algebra operations are memory bandwidth limited.
It might also be the case that communication overhead overwhelms you local computation. For example, in linear iterative methods we recommend having at least 10,000 unknowns per process.
or numerical factors:
Parallel preconditioners are often weaker than their serial counterparts. For example, block Jacobi gets weaker the more blocks you use. Thus, you need to account for extra time spent on extra linear iterations. Nonlinear conditions in general does not work this way, so Newton iterations are often constant.
Whenever trying to parallelise a program you have to balance out a number of costs, but primarily there is
- The cost of running each computation
- The cost of any communications between those computations
- The cost of managing those computations
If your computations are embarrassingly parallel then the communications cost will be very low (input and output only) and the management cost should be very low.
If you have interdependencies between computations, the communications cost can go up significantly. If you have a complex algorithm that takes different time to complete for any given computation, then the management complexity goes up, as you try to efficiently make use of the resources you have.
As with any form of optimisation, the key is to benchmark. Look at how it performs without MPI, how it performs with MPI and one process, then look at how it scales.
If you are playing with CUDA, try giving it much more data. One test here resulted in a negative speedup. We gave it 1000 times more data and the GP-GPU version finished in almost the same time, while the version running on the main CPU took 1000 times as long.
I would recommend you do the following:
Make a profile of the time execution of your code, with and without parallelization. If you have doubts about how to do this, we can help you if you describe your code better.
You can now focus on the parts that run slower in parallel. You should be aware that communication between processes may be slow. Like Mark and Sean pointed out, just because a problem can be divided into threads doesn't mean that doing so will be efficient. You have to look into it more deeply. But if you profile your code, it may help you to find any existing bugs. My two cents.
If you explain what you are doing in more detail, e.g. with a workflow, someone may be able to give you a better explanation.