Acceleration of the Multi Level Fast Multipole Algorithm on a Graphics Processing Unit

Abstract

It is of great importance that enemy aircraft can be detected by a radar. Good knowledge about one’s own detectability is also needed to make one’s own visibility as low as possible. Obtaining the aircraft radar signature involves solving a scattering problem with a large, low-observable aircraft. Briefly explained; the incident radar wave induces a current distribution on the surface of the scatterer. Using theMethod ofMoments (MoM), this current distribution can be found as the solution of an integral equation. The current distribution is expanded in a set of basis functions. Because every pair of basis functions interacts through the Green’s function, the continuous equation turns into a matrix equation after discretization. The matrix in this equation is a dense matrix. It is not desirable for practical problems to save the large system matrix, because this limits the problem size considerably. The Fast Multipole Method (FMM) became popular because it makes it possible to reduce the memory storage and the work needed to solve the discretized integral equation greatly. The work scales proportional to O(N 3 2 ), where N is the number of unknowns. The Multi Level Fast Multipole Algorithm (MLFMA) reduces the required memory and computational complexity even more to O(N logN) by having different levels of clustering. Radar signature computations are, with the use of theMulti Level FastMultipole Algorithm, still computationally intensive. Graphics Processing Units (GPU’s) have the potential of high computational power at relatively low cost. Given the hardware and software restrictions of Graphics Processing Units, some parts of the Multi Level FastMultipole Algorithmare better suited for calculations onGraphics ProcessingUnits than others. Only by perfectly understanding the properties of Graphics Processing Units, the applicability of theMulti Level Fast Multipole Algorithmcan be fully exploited. Matrix vector multiplications are the most time consuming parts in the Multi Level Fast Multipole Algorithm and are suitable for parallel computations. Therefore, this part of the algorithmis implemented on theGraphics Processing Units. A discretized Poisson equation will serve as a model problem for the Multi Level Fast Multipole Algorithm computation. The Poisson equation is discretized with finite differences on a structured grid in two dimensions. The discretized Poisson equation is iteratively solved on a Graphics Processing Unit. When the calculations are performed on a Graphics Processing Unit, they take up to 11 times less time in comparison with the same system performed on a single core of a Central Processing Unit (CPU). Three small test problems for theMulti Level FastMultipole Algorithm are used to compare the performance of different implementation methods. The test problems have a realistic structure, but have a smaller number of unknowns compared to real problems. Like inmany other applications, the bottleneck of Graphics Processing Units is the fact that information has to be sent back and forth. When a large amount of data has to be sent back and forth, the Graphics Processing Unit is not faster than a Central Processing Unit. Three test problems are accelera