This paper investigates two parallel simulation methodologies, multiple replication and parallel regenerative simulation. Problems of applying these methodologies to massively parallel simulations are identified. Two approaches (MR-PI and PR) are proposed to overcome some of these problems. The MR-PI approach, based on multiple replication simulation, uses a pilot simulation to reduce the initial transient bias by starting the simulation from a state that is representative of the steady-state conditions. The PR approach allows approximate regeneration by using substate matching for models that do no regenerate frequently. Empirical results suggest that the proposed approaches can produce very accurate results.