Parallelization of multilevel fast multipole algorithm for scattering analysis of targets situated in a half-space environment is presented. Due to the introduction of image sources to deal with the effects of far interface interactions, the communication traffic is nearly doubled compared to that in the free-space case. An adaptive direction partitioning strategy with improved load balance is developed. The number of plane-wave direction partitions at a given tree level varies with tree node descendants to make the algorithm suitable for both uniform and nonuniform tree levels and efficient to utilize modern CPUs with 8, 10, 12, or other numbers of cores. Both weak and strong scalability of the algorithm is investigated, and numerical results show that the algorithm is very efficient using up to 2048 CPU cores. © 2002-2011 IEEE.