Efficient backprojection-based synthetic aperture radar computation with many-core processors
Authors: 
Jongsoo Park, Ping Tak Peter Tang, Mikhail Smelyanskiy, Daehyun Kim, Thomas BensonAuthors Info & Claims
Abstract
Tackling computationally challenging problems with high efficiency often requires the combination of algorithmic innovation, advanced architecture, and thorough exploitation of parallelism. We demonstrate this synergy through synthetic aperture radar SAR via backprojection, an image reconstruction method that can require hundreds of TFLOPS. Computation cost is significantly reduced by our new algorithm of approximate strength reduction; data movement cost is economized by software locality optimizations facilitated by advanced architecture support; parallelism is fully harnessed in various patterns and granularities. We deliver over 35 billion backprojections per second throughput per compute node on an Intel® Xeon® processor E5-2670-based cluster, equipped with Intel® Xeon Phi™ coprocessors. This corresponds to processing a 3K×3K image within a second using a single node. Our study can be extended to other settings: backprojection is applicable elsewhere including medical imaging, approximate strength reduction is a general code transformation technique, and many-core processors are emerging as a solution to energy-efficient computing.
References
[1]
A.V. Aho, M.S. Lam, R. Sethi and J.D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 2007.
[2]
F.E. Allen, J. Cocke and K. Kennedy, Reduction of operator strength, in: Program Flow Analysis, 1981, pp. 79-101.
[3]
G.M. Amdahl, Validity of the single processor approach to achieving large scale computing capabilities, in: AFIPS Spring Joint Computer Conference, 1967, pp. 483-485.
[4]
T.M. Benson, D.P. Campbell and D.A. Cook, Gigapixel spotlight synthetic aperture radar backprojection using clusters of GPUs and CUDA, in: IEEE Radar Conference, 2012, pp. 853-858.
[5]
D.P. Campbell, D.A. Cook and B.P. Mulvaney, A streaming sensor challenge problem for ubiquitous high performance computing, 2011, available at: http://www.ll.mit.edu/HPEC/agendas/proc11/Day1/Session_1/1025_Campbell.pdf.
[6]
J. Cocke and K. Kennedy, An algorithm for reduction of operator strength, Communications of the ACM 20(11) (1977), 850-856.
[7]
B. Cordes and M. Leeser, Parallel backprojection: A case study in high-performance reconfigurable computing, EURASIP Journal on Embedded Systems 2009 (2009), 1.
[8]
M. Deisher, M. Smelyanskiy, B. Nickerson, V.W. Lee, M. Chuvelev and P. Dubey, Designing and dynamically load balancing hybrid LU for multi/many-core, Computer Science-Research and Development 26(3,4) (2011), 211-220.
[9]
M.D. Desai and W.K. Jenkins, Convolution backprojection image reconstruction for spotlight mode synthetic aperture radar, Image Processing, IEEE Transactions on Image Processing 1(4) (1992), 505-517.
[10]
A.R. Fasih and T.D.R. Hartley, GPU-accelerated synthetic aperture radar backprojection in CUDA, in: IEEE Radar Conference, 2010, pp. 1408-1413.
[11]
E. Hansis, J. Bredno, D. Sowards-Emmerd and L. Shao, Iterative reconstruction for circular cone-beam CT with an offset flat-panel detector, in: IEEE Nuclear Science Symposium Conference Record (NSS/MIC), 2010, pp. 2228-2231.
[12]
T.D.R. Hartley, A.R. Fasih, C.A. Berdanier, F. Özgüner and U.V. Catalyurek, Investigating the use of GPU-accelerated nodes for SAR image formation, in: IEEE International Conference on Cluster Computing (CLUSTER), 2009, pp. 1-8.
[13]
J.R. Humphrey, D.K. Price, K.E. Spagnoli, A.L. Paolini and E.J. Kelmelis, CULA: hybrid GPU accelerated linear algebra routines, in: SPIE Conference Series, Vol. 7705, April 2010.
[14]
A. Isola, A. Ziegler, T. Koehler, W.J. Niessen and M. Grass, Motion-compensated iterative cone-beam CT image reconstruction with adapted blobs as basis functions, Physics in Medicine and Biology 53 (2008), 6777.
[15]
C.V. Jakowatz, Jr., D.E. Wahl, D.C.G.P.H. Eichel and P.A. Thompson, Spotlight-Mode Synthetic Aperture Radar: A Signal Processing Approach, Kluwer Academic Publishers, 1996.
[16]
C.V. Jakowatz, Jr., D.E. Wahl and D.A. Yocky, Beamforming as a foundation for spotlight-mode SAR image formation by backprojection, in: SPIE 6970, 2008.
[17]
P. Kogge, K. Bergman, S. Borkar, D. Campbell, W. Carlson, W. Dally, M. Denneau, P. Franzon, W. Harrod, K. Hill, J. Hiller, S. Karp, S. Keckler, D. Klein, R. Lucas, M. Richards, A. Scarpelli, S. Scott, A. Snavely, T. Sterling, R.S. Williams and K. Yelick, ExaScale computing study: Technology challenges in achieving exascale systems, 2008, available at: www.cse.nd.edu/Reports/2008/TR-2008-13.pdf.
[18]
S. McIntosh-Smith and J. Irwin, The best of both worlds: Delivering aggregated performance for high-performance math libraries in accelerated system, in: ISC, 2007, pp. 331-340.
[19]
J.-M. Muller, Elementary Functions: Algorithms and Implementation, Birkhäuser, 2006.
[20]
D.C. Munson, Jr., J.D. O'Brien and W.K. Jenkins, A tomographic formulation of spotlight-mode synthetic aperture radar, Proceedings of the IEEE 71(8) (1983), 917-925.
[21]
A. Nguyen, N. Satish, J. Chhugani, C. Kim and P. Dubey, 3.5-D blocking optimization for stencil computations on modern CPUs and GPUs, in: International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2010, pp. 1-13.
[22]
F. Niu, B. Recht, C. Re and S.J. Wright, HOGWILD!: A lockfree approach to parallelizing stochastic gradient descent, in: Advances in Neural Information Processing Systems (NIPS), 2011.
[23]
NVIDIA, OpenCL programming guide for the CUDA architecture, 2009, available at: www.nvidia.com/content/cudazone/download/OpenCL/NVIDIA_OpenCL_ProgrammingGuide.pdf.
[24]
R. Portillo, S. Arunagiri, P.J. Teller, S.J. Park, L.H. Nguyen, J.C. Deroba and D. Shires, Power versus performance tradeoffs of GPU-accelerated backprojection-based synthetic aperture radar image formation, in: Proceedings of SPIE, Modeling and Simulation for Defense Systems and Applications VI, Vol. 8060, 2011.
[25]
M.A. Richards, Fundamentals of Radar Signal Processing, McGraw-Hill, 2005.
[26]
M. Soumekh, Synthetic Aperture Radar Signal Processing with MATLAB Algorithms, Wiley Interscience, 1999.
[27]
J.E. Volder, The CORDIC trigonometric computing technique, in: IRE Transactions on Electronic Computers, 1959, pp. 330-334.
[28]
D.E. Wahl, D.A. Yocky and C.V. Jakowatz, Jr., An implementation of a fast backprojection image formation algorithm for spotlight-mode SAR, Algorithms for Synthetic Aperture Radar Imagery XV 6970 (2008), 69700H.
[29]
M. Wolfe, High Performance Compilers for Parallel Computing, Addison-Wesley, 1996.
[30]
S. Xiao, D.C. Munson, Jr., S. Basu and Y. Bresler, An N2 log N back-projection algorithm for SAR image formation, in: Asilomar Conference on Signals, Systems and Computers, 2000, pp. 3-7.
- Efficient backprojection-based synthetic aperture radar computation with many-core processors
Recommendations
Efficient backprojection-based synthetic aperture radar computation with many-core processors
SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and AnalysisTackling computationally challenging problems with high efficiency often requires the combination of algorithmic innovation, advanced architecture, and thorough exploitation of parallelism. We demonstrate this synergy through synthetic aperture radar (...
Efficient backprojection-based synthetic aperture radar computation with many-core processors
SC '12: Proceedings of the 2012 International Conference for High Performance Computing, Networking, Storage and AnalysisTackling computationally challenging problems with high efficiency often requires the combination of algorithmic innovation, advanced architecture, and thorough exploitation of parallelism. We demonstrate this synergy through synthetic aperture radar (...
Efficient sparse matrix-vector multiplication on x86-based many-core processors
ICS '13: Proceedings of the 27th international ACM conference on International conference on supercomputingSparse matrix-vector multiplication (SpMV) is an important kernel in many scientific applications and is known to be memory bandwidth limited. On modern processors with wide SIMD and large numbers of cores, we identify and address several bottlenecks ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IOS Press
Netherlands
Publication History
Published: 01 July 2013
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in