A fast high-order Finite Element-Boundary Integral-Multilevel Fast Multipole Algorithm (FE-BI-MLFMA) recently has been presented for scattering by large and deep cavities [1]. The bottleneck of this algorithm is pointed out in this paper. A parallelization approach of this FE-BI-MLFMA is presented and implemented to eliminate this bottleneck. Numerical experiments demonstrate the parallel efficiency of this parallelization approach. The capability of this parallel FE-BI-MLFMA is demonstrated by computing scattering by a big and deep brick cavity with 15λ×15λ×100λ. Numerical examples of cavities loaded with obstacles, including a circular cavity loaded by an array of straight blades model are performed to verify the high efficiency and accuracy of the parallel FE-BI-MLFMA.