We discuss methods that allow us to increase the step size in a parallel tempering simulation of statistical models and test them at the example of the three-dimensional Heisenberg spin glass. We find an overall speedup of about 2 for contemporary lattices.