A long-standing open challenge for automated program repair (APR) is search space explosion, which makes the size of the patch space too large to be handled with limited resources of time and memory. This problem is further exacerbated by the accuracy challenges of fault localization techniques, which regularly rank the actual faulty statement low on the list of suspicious statements, resulting in wasted repair effort. This paper proposes an approach to increase the overall performance of APR for large-scale programs by utilizing parallelism for exploring the patch space, as a promising strategy to parallelize template-based APR and effectively ameliorate the accuracy challenges of fault localization. Our empirical study reveals that a substantial five-fold improvement in performance can be obtained without any degradation in repair quality. We also observe that parallelized APR produces a larger number of plausible patches than sequential APR. These encouraging results show that the proposed approach is both feasible and efficient. Future steps include investigating other promising search space splitting strategies, such as splitting based on the fix templates in template-based APR, and hybrid combinations of such strategies.