A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction

Mert Hidayetoglu, Carl Pearson, Izzat El Hajj, Levent Gurel, Weng Cho Chew, Wen-Mei W Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a massively-parallel solver for large Helmholtz-Type inverse scattering problems. The solver employs the distorted Born iterative method for capturing the multiples-cattering phenomena in image reconstructions. This method requires many full-wave forward-scattering solutions in each iteration, constituting the main performance bottleneck with its high computational complexity. As a remedy, we use the multilevel fast multipole algorithm (MLFMA). The solver scales among computing nodes using a two-dimensional parallelization strategy that distributes illuminations in one dimension, and MLFMA sub-Trees in the other dimension. Multi-core CPUs and GPUs are used to provide per-node speedup. We demonstrate a 76% efficiency when scaling from 64 GPUs to 4,096 GPUs. The paper provides reconstruction of a 204.8?×204.8? image (4M unknowns) executed on 4,096 GPUs in near-real time (almost 2 minutes). To the best of our knowledge, this is the largest full-wave inverse scattering solution to date, in terms of both image size and computational resources.

Original languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages64-74
Number of pages11
ISBN (Print)9781538643686
DOIs
StatePublished - Aug 3 2018
Event32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 - Vancouver, Canada
Duration: May 21 2018May 25 2018

Publication series

NameProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

Other

Other32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018
CountryCanada
CityVancouver
Period5/21/185/25/18

Fingerprint

Multiple scattering
Image reconstruction
Scattering
Forward scattering
Iterative methods
Program processors
Computational complexity
Lighting
Graphics processing unit
Node

Keywords

  • GPU
  • Imaging
  • Inverse Scattering
  • Massive Parallelization
  • Multilevel Fast Multipole Algorithm

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems and Management

Cite this

Hidayetoglu, M., Pearson, C., El Hajj, I., Gurel, L., Chew, W. C., & Hwu, W-M. W. (2018). A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction. In Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018 (pp. 64-74). [8425161] (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2018.00017

A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction. / Hidayetoglu, Mert; Pearson, Carl; El Hajj, Izzat; Gurel, Levent; Chew, Weng Cho; Hwu, Wen-Mei W.

Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 64-74 8425161 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Hidayetoglu, M, Pearson, C, El Hajj, I, Gurel, L, Chew, WC & Hwu, W-MW 2018, A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction. in Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018., 8425161, Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018, Institute of Electrical and Electronics Engineers Inc., pp. 64-74, 32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, Canada, 5/21/18. https://doi.org/10.1109/IPDPS.2018.00017
Hidayetoglu M, Pearson C, El Hajj I, Gurel L, Chew WC, Hwu W-MW. A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction. In Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 64-74. 8425161. (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018). https://doi.org/10.1109/IPDPS.2018.00017
Hidayetoglu, Mert ; Pearson, Carl ; El Hajj, Izzat ; Gurel, Levent ; Chew, Weng Cho ; Hwu, Wen-Mei W. / A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction. Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 64-74 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018).
@inproceedings{dd2fd927cff84698b5b26860ff5cef24,
title = "A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction",
abstract = "We present a massively-parallel solver for large Helmholtz-Type inverse scattering problems. The solver employs the distorted Born iterative method for capturing the multiples-cattering phenomena in image reconstructions. This method requires many full-wave forward-scattering solutions in each iteration, constituting the main performance bottleneck with its high computational complexity. As a remedy, we use the multilevel fast multipole algorithm (MLFMA). The solver scales among computing nodes using a two-dimensional parallelization strategy that distributes illuminations in one dimension, and MLFMA sub-Trees in the other dimension. Multi-core CPUs and GPUs are used to provide per-node speedup. We demonstrate a 76{\%} efficiency when scaling from 64 GPUs to 4,096 GPUs. The paper provides reconstruction of a 204.8?×204.8? image (4M unknowns) executed on 4,096 GPUs in near-real time (almost 2 minutes). To the best of our knowledge, this is the largest full-wave inverse scattering solution to date, in terms of both image size and computational resources.",
keywords = "GPU, Imaging, Inverse Scattering, Massive Parallelization, Multilevel Fast Multipole Algorithm",
author = "Mert Hidayetoglu and Carl Pearson and {El Hajj}, Izzat and Levent Gurel and Chew, {Weng Cho} and Hwu, {Wen-Mei W}",
year = "2018",
month = "8",
day = "3",
doi = "10.1109/IPDPS.2018.00017",
language = "English (US)",
isbn = "9781538643686",
series = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "64--74",
booktitle = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018",
address = "United States",

}

TY - GEN

T1 - A fast and massively-parallel inverse solver for multiple-scattering tomographic image reconstruction

AU - Hidayetoglu, Mert

AU - Pearson, Carl

AU - El Hajj, Izzat

AU - Gurel, Levent

AU - Chew, Weng Cho

AU - Hwu, Wen-Mei W

PY - 2018/8/3

Y1 - 2018/8/3

N2 - We present a massively-parallel solver for large Helmholtz-Type inverse scattering problems. The solver employs the distorted Born iterative method for capturing the multiples-cattering phenomena in image reconstructions. This method requires many full-wave forward-scattering solutions in each iteration, constituting the main performance bottleneck with its high computational complexity. As a remedy, we use the multilevel fast multipole algorithm (MLFMA). The solver scales among computing nodes using a two-dimensional parallelization strategy that distributes illuminations in one dimension, and MLFMA sub-Trees in the other dimension. Multi-core CPUs and GPUs are used to provide per-node speedup. We demonstrate a 76% efficiency when scaling from 64 GPUs to 4,096 GPUs. The paper provides reconstruction of a 204.8?×204.8? image (4M unknowns) executed on 4,096 GPUs in near-real time (almost 2 minutes). To the best of our knowledge, this is the largest full-wave inverse scattering solution to date, in terms of both image size and computational resources.

AB - We present a massively-parallel solver for large Helmholtz-Type inverse scattering problems. The solver employs the distorted Born iterative method for capturing the multiples-cattering phenomena in image reconstructions. This method requires many full-wave forward-scattering solutions in each iteration, constituting the main performance bottleneck with its high computational complexity. As a remedy, we use the multilevel fast multipole algorithm (MLFMA). The solver scales among computing nodes using a two-dimensional parallelization strategy that distributes illuminations in one dimension, and MLFMA sub-Trees in the other dimension. Multi-core CPUs and GPUs are used to provide per-node speedup. We demonstrate a 76% efficiency when scaling from 64 GPUs to 4,096 GPUs. The paper provides reconstruction of a 204.8?×204.8? image (4M unknowns) executed on 4,096 GPUs in near-real time (almost 2 minutes). To the best of our knowledge, this is the largest full-wave inverse scattering solution to date, in terms of both image size and computational resources.

KW - GPU

KW - Imaging

KW - Inverse Scattering

KW - Massive Parallelization

KW - Multilevel Fast Multipole Algorithm

UR - http://www.scopus.com/inward/record.url?scp=85052202478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052202478&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2018.00017

DO - 10.1109/IPDPS.2018.00017

M3 - Conference contribution

AN - SCOPUS:85052202478

SN - 9781538643686

T3 - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

SP - 64

EP - 74

BT - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -