Spatial Partitioning Strategy for Parallelization of MLFMA with Reduced Communication

Authors

  • Xunwang Zhao Shaanxi Key Laboratory of Large Scale Electromagnetic Computing School of Electronic Engineering, Xidian University, Xi’an, 710071, China
  • Chang Zhai Shaanxi Key Laboratory of Large Scale Electromagnetic Computing School of Electronic Engineering, Xidian University, Xi’an, 710071, China
  • Zhongchao Lin Shaanxi Key Laboratory of Large Scale Electromagnetic Computing School of Electronic Engineering, Xidian University, Xi’an, 710071, China
  • Yu Zhang Shaanxi Key Laboratory of Large Scale Electromagnetic Computing School of Electronic Engineering, Xidian University, Xi’an, 710071, China
  • Qifeng Liu Science and Technology on Electromagnetic Compatibility Laboratory China Ship Development and Design Center, Wuhan 430064, China

Keywords:

Multilevel fast multipole algorithm (MLFMA), parallelization, reduced communication, spatial partitioning, subtrees

Abstract

The bottleneck of the spatial partitioning for parallelizing the multilevel fast multipole algorithm (MLFMA) lies in higher levels of the tree, at which boxes are usually fewer than parallel processors, yielding a serious load imbalance. To solve the bottleneck, the higher levels of the tree are truncated to generate plenty of subtrees, which are distributed among processors to facilitate balancing the work load. At the coarsest level, the communication volume during translation between far-away processors is drastically reduced by adopting the far-field approximation. Therefore, the communication mainly occurs between nearby processors, which is favorable for modern computing clusters. In comparison with the parallel strategies that hybridize the spatial partitioning with the k-space partitioning, the proposed approach is more straightforward and shows good scalability.

Downloads

Download data is not yet available.

References

X. Zhao, Y. Chen, H. Zhang, Y. Zhang, and T. K. Sarkar, “A new decomposition solver for complex electromagnetic problems [EM Programmer's Notebook],” IEEE Antennas and Propag. Mag., vol. 59, no. 3, pp. 131-140, June 2017.

W. Yu, X. Yang, Y. Liu, L.-C. Ma, T. Su, N.-T. Huang, R. Mittra, R. Maaskane, Y. Lu, Q. Che, R. Lu, and Z. Su, “A new direction in computational electromagnetics: solving large problems using the parallel FDTD on the BlueGene/L supercomputer providing Teraflop-level performance,” IEEE Antennas and Propag. Mag., vol. 50, no. 2, pp. 26- 44, Apr. 2008.

S. Jiang, Y. Zhang, Z. Lin, and X. Zhao, “An optimized parallel FDTD topology for challenging electromagnetic simulations on supercomputers,” International Journal of Antennas and Propagation, vol. 2015, Article ID 690510, 10 pages, 2015.

S. Velamparambil and W.C. Chew, “Analysis and performance of a distributed memory multilevel fast multipole algorithm,” IEEE Trans. Antennas Propag., vol. 53, no. 8, pp. 2719-2727, Aug. 2005.

X.-M. Pan, W.-C. Pi, M.-L. Yang, Z. Peng, and X.- Q. Sheng, “Solving problems with over one billion unknowns by the MLFMA,” IEEE Trans. Antennas Propag., vol. 60, no. 5, pp. 2571-2574, May 2012.

Ö. Ergül and L. Gürel, “A hierarchical partitioning strategy for an efficient parallelization of the multilevel fast multipole algorithm,” IEEE Trans. Antennas Propag., vol. 57, no. 6, pp. 1740-1750, June 2009.

B. Michiels, J. Fostier, I. Bogaert, and D. D. Zutter, “Weak scalability analysis of the distributedmemory parallel MLFMA,” IEEE Trans. Antennas Propag., vol. 61, no. 11, pp. 5567-5574, Nov. 2013.

X. Zhao, S.-W. Ting, and Y. Zhang. “Parallelization of half-space MLFMA using adaptive direction partitioning strategy,” IEEE Antennas and Wireless Propag. Lett., vol. 13, pp. 1203-1206, 2014.

J. M. Taboada, M. G. Araujo, F. O. Basteiro, J. L. Rodriguez, and L. Landesa, “MLFMA-FFT parallel algorithm for the solution of extremely large problems in electromagnetics,” Proceedings of the IEEE, vol. 101, no. 2, pp. 350-363, Feb. 2013.

B. MacKie-Mason, A. Greenwood, and Z. Peng, “Adaptive and parallel surface integral equation solvers for very large-scale electromagnetic modeling and simulation (invited paper),” Progress In Electromagnetics Research, vol. 154, pp. 143- 162, 2015.

T. Agarwal, A. Sharma, A. Laxmikant, and L. V. Kale, “Topology-aware task mapping for reducing communication contention on large parallel machines,” in Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium, Rhodes Island, Greece, 25-29 April 2006.

Hop (networking), accessed on June 25, 2017. [Online]. https://en.wikipedia.org/wiki/Hop_(networking).

W. C. Chew, T. J. Cui, and J. M. Song, “A FAFFAMLFMA algorithm for electromagnetic scattering,” IEEE Trans. Antennas Propag., vol. 50, no. 11, pp. 1641-1649, Nov. 2002.

S. Velamparambil, W. C. Chew, and J. Song. “10 million unknowns: is it that big?,” IEEE Antennas and Propag. Mag., vol. 45, no. 2, pp. 43-58, Apr. 2003.

J. Song and W. C. Chew, “Interpolation of translation matrix in MLFMA,” Microw. Opt. Techn. Lett., vol. 30, no. 2, pp. 109-114, July 2001.

C. Delgado and M. F. Cátedra, “Combination of ray-tracing and the method of moments for electromagnetic radiation analysis using reduced meshes,” Journal of Computational Physics, vol. 361, pp. 412-423, Jan. 2018.

Y. Zhang, Y. J. Xie, and C. Liang, “A highly effective preconditioner for MoM analysis of large slot arrays,” IEEE Trans. Antennas Propag., vol. 52, no. 5, pp. 1379-1381, May 2004.

S. M. Rao, D. R. Wilton, and A. W. Glisson, “Electromagnetic scattering by surfaces of arbitrary shape,” IEEE Trans. Antennas Propag., vol. 30, pp. 409-418, May 1982.

Downloads

Published

2021-07-16

How to Cite

[1]
Xunwang Zhao, Chang Zhai, Zhongchao Lin, Yu Zhang, and Qifeng Liu, “Spatial Partitioning Strategy for Parallelization of MLFMA with Reduced Communication”, ACES Journal, vol. 34, no. 01, pp. 11–16, Jul. 2021.

Issue

2019: Vol 34 Iss 1

Section

General Submission