The parallel computing method is introduced for the mission reliability computation of large phased-mission system (PMS). According to analysis of the traditional uniformization method (UM), a UM parallel algorithm based on graphics processing unit (GPU) is given, which is denoted as GPU-UM. The GPU-UM algorithm is implemented under the compute unified device architecture (CUDA) put forward by Nvidia. The coherence visiting and shared memory techniques have been used to improve the data load utilization ratio on GPU. In addition, the component types and quantities involved in mission may be changed under different phases. The complex phase changes lead to difficulty about handling components dependency. A system states mapping mechanism is proposed by analyzing three basic situations: adding new components, some working components quitting transiently or completely. In practice, changes between two consecutive phases can be processed by coordinating the three situations above as it becomes more complicated. The computation time and reliability under the GPU-UM, the CUDA-UM, the traditional UM and the Krylov subspace algorithms are compared. Results show that the GPU-UM algorithm is the best among them both in computation time and accuracy. Furthermore, the computation errors between the two algorithms (UM and Krylov) and simulation method are analyzed. It shows that the proposed states mapping mechanism can handle the phases dependency in PMS efficiently.