<p>The strength reduction finite element method (SRFEM) has been successfully applied to two-dimensional (2D) and three-dimensional (3D) slope stability analysis. Numerical experiments demonstrate that the high computational cost, complexity, and numerical difficulties of SRFEM may markedly hinder its applications to 3D slope stability analysis. Alternatively, a semidefinite programming-optimized finite element method with strength reduction (SRFEM-SDP) is implemented and compared to SRFEM. It is underscored, however, that the existing search algorithms of factor of safety (<i>FOS</i>) have been executed on a single processor, seldom studies have attempted to leverage parallel processing to improve the search process of <i>FOS</i>. In this work, we propose two novel parallel search algorithms of <i>FOS</i>: first, a parallel multisection (PMS) algorithm is developed, which is applicable to both SRFEM and SRFEM-SDP; second, by setting a significantly small maximum number of nonlinear iterations (<i>maxIters_NL</i>) for the Level-1 (L1) search followed by a prescribed <i>maxIters_NL</i> for the Level-2 (L2) search, a two-levels (2Ls) parallel multisection (PMS^2Ls) algorithm is specifically developed to enhance efficiency of SRFEM. Based on one homogeneous slope and the James Bay Dyke, numerical results demonstrate that when SRFEM is applied, the acceleration ratio (<i>R</i>_acc) of the PMS^2Ls algorithm can be up to 9.67 by reference to the single processor search; SRFEM-SDP is very competitive to SRFEM for our investigated 3D slope stability analyses in terms of the computational efficiency, due to its cheap and balanced computational costs at the feasible and infeasible solution sides.</p>