The simulation of EM (electromagnetic) wave propagation requires considerable computation time, as it analyzes a large number of propagation paths. To overcome this problem, we propose a GPU (graphics processing unit)-based parallel algorithm for VPL (vertical plane launch)-approximated EM wave propagation. The conventional algorithm computes the gain along propagation paths with irregular memory access, which results in low GPU performance. In our proposed algorithm, a CPU reorders irregular propagation paths to a GPU-suitable linear order on the CPU memory at each receiving point. We hid the reordering time behind CPU-GPU communication and GPU-based computation of gain on the reordered memory. We found that our proposed algorithm with a quad GPU is up to 30 times faster than the conventional algorithm with a 16-threaded dual CPU.