It's typically very hard if not impossible to implement a parallel version of an iterative algorithm that paralellizes across iterations. The completion of one iteration is a natural sequence point. If one algorithm requires fewer iterations but more work per iteration, then it's more likely that this algorithm can be effectively implemented in parallel.

An example of this is linear programming, where the primal-dual barrier (interior point) method typically uses only a few dozen iterations even for very large problems, but the work per iteration is quite extensive. In comparison various versions of the simplex method typically require far more iterations, but the work per iteration is less. In practice, parallel implementations of interior point methods have show far better parallel efficiency than parallel implementations of the simplex method.

It's typically very hard if not impossible to implement a parallel version of an iterative algorithm that paralellizes across iterations. The completion of one iteration is a natural sequence point. If one algorithm requires fewer iterations but more work per iteration, then it's more likely that this algorithm can be effectively implemented in parallel.

An example of this is linear programming, where the primal-dual barrier (interior point) method typically uses only a few dozen iterations even for very large problems, but the work per iteration is quite extensive. In comparison various versions of the simplex method typically require far more iterations, but the work per iteration is less. In practice, parallel implementations of interior point methods have shown far better parallel efficiency than parallel implementations of the simplex method.