This thesis reports on the parallelization of an object-oriented stochastic agent-based simulator, openPASS, which is widely used in automated driving research. Based on software and hardware analysis, a suitable multithreading strategy is implemented that is deterministic at all times. A strategy for distributing agents on hardware threads is developed and optimized considering data distribution, synchronization and load balancing. Stochastic quality in the multithreaded program is investigated through analytical and empirical studies of parallel random number generation. As a result, a suitable design for parallel random number generation based on distributed Mersenne Twister generators is established. In addition, a theoretical framework is developed to quantify the error between the original and multithreaded program. The multithreaded program was found to speed up the average runtime of the simulation by a factor of 3.02, from a theoretical maximum speedup of 5.33. Underlying convergence properties of the stochastic simulation were preserved by the multithreading implementation. Further speedup was limited because the CPU frontend did not pass enough operations to the CPU backend due to expensive cross-object function calls.