The same type of problem occurs in many different guises in computational physics. In many applications, there are standard algorithms that are regular, simple, often local, and thus parallelize very efficiently. However, it is this very regularity and locality that makes them poor algorithms.
Complex physical problems and physical systems are usually irregular, often non-local, and change rapidly with time, so simple regular and local algorithms tend to have problems, such as critical slowing down.
More complex algorithms, such as non-local, irregular cluster algorithms; multiscale and multigrid methods for PDEs and spin models; adaptive, irregular grids for finite element calculations; hierarchical, adaptive N-body solvers; etc., all work much better, but are much more difficult to parallelize!