We present an optimistic synchronous relaxation algorithm for parallel kinetic Monte Carlo (KMC) simulations of thin film growth. This algorithm is based on spatial decomposition of the KMC lattice and it employs two measures aimed at improving the parallel efficiency: dynamic global updating and domain boundary shifting. We utilize this algorithm to simulate two different growth models, which represent the growth of Ag on Ag(111) and the heteroepitaxial growth of Ag on Pt(111). We show that these simulations can achieve good efficiency-especially for large domain sizes with a moderate number of processors. We find that domain boundary shifting can improve efficiency-especially for simulations of growth in the AgPt(111) system, where the potential-energy surface topology creates areas of rapid, localized motion. We analyze the origins of parallel efficiency in these simulations.