Fast CPU/GPU Pattern Evaluation of Irregular Arrays
Keywords:
Fast CPU/GPU Pattern Evaluation of Irregular ArraysAbstract
An approach for the fast analysis of “irregular”, i.e., of conformal, periodic or aperiodic, 2D arrays, based on the use of the pseries approach and Non-Uniform FFT (NUFFT) routines is proposed. The approach allows for modulating the computational burden depending on the array curvature and, thanks to the use of the NUFFT, the asymptotic growth of the computing time reduces to that of a few, standard FFTs. A sub-array partition strategy is also sketched and shown to further unburden the procedure and control the accuracy. The approach has been implemented in both sequential and parallel codes enabling its execution on CPUs and on costeffective, massively parallel computing platforms like Graphic Processing Units (GPUs). Its performance in terms of computational efficiency and accuracy has been assessed by an extensive numerical analysis and also against benchmarks provided by algorithms based on fast Matrix- Vector Multiplication routines.
Downloads
References
O.M. Bucci, G. D’Elia, G. Mazzarella, and G.
Panariello, “Antenna pattern synthesis: a new
general approach”, Proc. of the IEEE, vol. 82,
no. 3, pp. 358-371, Mar. 1994.
A. Capozzoli and G. D’Elia, “ Global
optimization and antennas synthesis and
diagnostics, part one: concepts, tools,
strategies and performances”, Progr.
Electromagn. Res. PIER, vol. 56, pp. 195-232,
A. Capozzoli and G. D’Elia, “Global
optimization and antennas synthesis and
diagnosis, part two: applications to advanced
reflector antennas synthesis and diagnosis
techniques”, Progr. Electromagn. Res. PIER,
vol. 56, pp. 233-261, 2006.
L. Josefsson and P. Persson, Conformal array
antenna theory and design, J. Wiley & Sons.,
New York, 2006.
G. Caille, I. Lager, L.P. Ligthart, C. Mangenot,
A.G. Roederer, G. Toso, and M.C. Viganò,
“Aperiodic arrays for multiple beam satellite
applications,” Proc. of the 11th Int. Symp. on
Microw. Opt. Tech., pp. 419-422, Dec. 2007.
A. Capozzoli, C. Curcio, G. D’Elia, A. Liseno,
and P. Vinetti, “FFT & aperiodic arrays with
phase-only control and constraints due to
super-directivity, mutual coupling and overall
size”, Proc. of the 30th ESA Antenna
Workshop on Antennas for Earth Observ.,
Science, Telecomm. and Navig. Space
Missions, May 2008.
A. Capozzoli, C. Curcio, G. D’Elia, and A.
Liseno, “Fast power pattern synthesis of
conformal reflectarrays”, Proc. of the IEEE
Antennas Prop. Symp., pp. 1-4, July 2008.
A. Capozzoli, C. Curcio, G. D’Elia, A. Liseno,
and P. Vinetti, “FFT & equivalently tapered
arrays”, Proc. of the XXIX URSI General
Assembly, Aug. 2008.
J.H. Doles III and F.D. Benedict, “Broad-band
array design using the asymptotic theory of
unequally spaced arrays,” IEEE Trans.
Antennas Prop., vol. 36, no. 1, pp. 27-33, Jan.
A. Akdagli and K. Guney, “Shaped-beam
pattern synthesis of equally and unequally
spaced linear antenna arrays using a modified
tabu search algorithm,” Microw. Optical Tech.
Lett., vol. 36, no. 1, pp. 16-20, Jan. 2003.
J. Huang, M. Lou, A. Feria, and Y. Kim, “An
inflatable L-band microstrip SAR array”,
Proc. of the IEEE Antennas Prop. Int. Symp.,
pp. 2100-2103, Jun. 1998.
R.E. Collin, Antennas and radiowave
propagation, McGraw-Hill, New York, 1985.
A.W. Rudge, K. Milne, A.D. Olver, and P.
Knight, The Handbook of Antenna Design Vol.
, London, Peter Peregrinus, 1983.
J.W. Cooley and J.W. Tukey, “An algorithm
for the machine calculation of complex
Fourier series”, Math. Comput., vol. 19, no.
, pp. 297-301, Apr. 1965.
V. Galindo-Israel and R. Mittra, “A new
series representation of the radiation integral
with application to reflector antennas”, IEEE
Trans. Antennas Prop., vol. AP-25, no. 5, pp.
-641, Sept. 1977.
O.M. Bucci, G. Franceschetti, and G. D’Elia,
“Fast analysis of large antennas – a new
computational philosophy”, IEEE Trans.
Antennas Prop., vol. AP-28, no. 3, pp. 306-
, May 1980.
K. Fourmont, “Non-equispaced fast Fourier
transforms with applications to tomography,”
CAPOZZOLI, CURCIO, D'ELIA, LISENO, VINETTI: FAST CPU/GPU PATTERN EVALUATION OF IRREGULAR ARRAYS
J. Fourier Anal. Appl., vol. 9, no. 5, pp. 431-
, Sept. 2003.
J. Y. Lee and L. Greengard, “The type 3
nonuniform FFT and its applications”, J.
Comput. Phys., vol. 206, n. 1, pp. 1-5, Jun.
J.D. Owens, M. Houston, D. Luebke, S.
Green, J. E. Stone, and J. C. Phillips, “GPU
computing”, Proc. of the IEEE, vol. 96, no. 5,
pp. 879-899, May 2008.
www.top500.org .
T. R. Halfhill, “Parallel processing with
CUDA”, Microproc. Rep.,
http://www.nvidia.com/docs/IO/55972/220401
_Reprint.pdf, Jan. 28, 2008.
S. S. Stone, J. P. Haldar, S. C. Tsao, W. M.
Hwu, B.P. Sutton, and Z.P. Liang,
“Accelerating advanced MRI reconstructions
on GPUs”, J. Parallel Distr. Comp., vol. 68,
no. 10, pp. 1307-1318, Oct. 2008.
M. J. Inman and A. Z. Elsherbeni,
“Programming video cards for computational
electromagnetics applications”, IEEE
Antennas Prop. Mag., vol. 47, no. 6, pp. 71-
, Dec. 2005.
D. Kirk and H. M. Hwu, CUDA Textbook, in
press.
M. Bläser, “Lower bounds for the
multiplicative complexity of matrix
multiplication”, Comput. Complex., vol. 8, no.
, pp. 203-226, Dec. 1999.
K. Atkinson and D. D. K. Chien, “A fast
matrix-vector multiplication method for
solving the radiosity equation”, Adv. in
Comput. Math., vol. 12, no. 2-3, Feb. 2000,
pp. 151-174.
http://matrixprogramming.com/MatrixMultipl
y/
D. Sundararajan, The Discrete Fourier
Transform: Theory, Algorithms and
Applications, Singapore, Word Scientific,
F. Smithies, Integral equations, Cambridge,
Cambridge University Press, 1958.
J. P. Boyd, “A fast algorithm for Chebyshev,
Fourier and sinc interpolation onto an irregular
grid”, J. Comput. Phys., vol. 103, no. 2, pp.
-257, Dec. 1992.
A. Dutt and V. Rokhlin, “Fast Fourier
transforms for nonequispaced data”, SIAM J.
Sci. Comput., vol. 14, no. 6, pp. 1368-1393,
Nov. 1993.
Q. H. Liu and N. Nguyen, “An accurate
algorithm for nonuniform fast Fourier
transforms (NUFFT’s)”, IEEE Microw.
Guided Wave Lett., vol. 8, no. 1, pp. 18-20,
Jan. 1998.
J. A. Fessler, B. P. Sutton, “Nonuniform fast
Fourier transforms using min-max
interpolation”, IEEE Trans. Signal Proc., vol.
, no. 2, pp. 560-574, Feb. 2003.
W. P. M. N. Keizer, “Large planar array
thinning using iterative FFT techniques”,
IEEE Trans. Antennas Prop., vol. 57, no. 10,
pp. 3359-3362, Oct. 2009.
H. Legay, B. Salome, E. Labiole, M. A.
Milon, D. Cadoret, R. Gillard, R.
Chaharmir,and J. Shaker, “Reflectarrays for
satellite telecommunication antennas”, Proc.
of the 2 nd Europ. Conf. on Antennas Prop.,
Nov. 11-16, 2007.
A. G. Roederer, “Reflectarray antennas”,
Proc. of the 3 rd Europ. Conf. on Antennas
Prof., pp. 18-22, Mar. 2009.
A. Capozzoli, C. Curcio, G. D’Elia, A.
Liseno, D. Bresciani, and H. Legay, “Fast
phase-only synthesis of faceted reflectarrays”,
Proc. of the 3 rd Europ. Conf. on Antennas
Prop., pp. 1329-1333, Mar. 23-27, 2009,
N. Yuan, T. S. Yeo, X. C. Nie, and L. W. Li,
“A fast analysis of scattering and radiation of
large microstrip antenna arrays”, IEEE Trans.
Antennas Prop., vol. 51, no .9, pp. 2218-2226,
Sept. 2003.
M. Frigo and S.G. Johnson, “The design and
implementation of FFTW3”, Proc. of the
IEEE, vol. 93, no. 2, pp. 216-231, Feb. 2005.
The Numerical Algorithms Group, Intel Math
Kernel Library Reference Manual, Intel
Corporation, 2001.
J. L. Hennessy and D. A. Patterson, Computer
Architecture: a quantitative approach, San
Francisco, USA, Morgan Kauffman Publisher,
NVIDIA CUDA Reference Manual, v. 2.0,
Jun. 2008.
CUDA cuFFT Library, Oct. 2007.
CUDA cuBLAS Library, Sept. 2007.
D. Göddeke, R. Strzodka, J. Mohd-Yusof, P.
McCormick, S.H.M. Buijssen, M. Grajewski,
and S. Turek, “Exploring weak scalability for
ACES JOURNAL, VOL. 25, NO. 4, APRIL 2010
FEM calculations on a GPU-enhanced
cluster”, Parallel Comp., vol. 33, no. 10-11,
pp. 685-699, Nov. 2007.
A. Capozzoli, C. Curcio, G. D’Elia, and A.
Liseno, “Power pattern synthesis of multifeed
reconfigurable reflectarrays”, Proc. of the 29th
ESA Antenna Workshop on Multiple Beams
Reconfig. Antennas, Apr. 2007
