Parallelism, Patterns, and Performance in Iterative MRI Reconstruction

Magnetic Resonance Imaging (MRI) is a non-invasive and highly flexiblemedical imaging modality that does not expose patients ionizing radiation.MR Image acquisitions can be designed by varying a large number ofcontrast-generation parameters, and many clinical diagnosticapplications exist.However, imaging speed is a fundamental limitation to many potentialapplications.Traditionally, MRI data have been collected at Nyquist sampling rates to producealias-free images.However, many recent scan acceleration techniques produce sub-Nyquistsamplings.For example, Parallel Imaging is a well-established acceleration techniquethat receives the MR signal simultaneously from multiple receive channels.Compressed sensing leverages randomized undersampling and the compressibility(e.g. via Wavelet transforms or Total-Variation) of medical imagesto allow more aggressive undersampling.Reconstruction of clinically viable images from these highly acceleratedacquisitions requires powerful, usually iterative algorithms.Non-Cartesian pulse sequences that perform non-equispaced sampling of k-spacefurther increase computational intensity of reconstruction, as theypreclude direct use of the Fast Fourier Transform (FFT).Most iterative algorithms can be understood by considering the MRIreconstruction as an inverse problem, where measurements of un-observableparameters are made via an observation function that models the acquisitionprocess.Traditional direct reconstruction methods attempt to invert thisobservation function, whereas iterative methods require its repeated computationand computation of its adjoint.As a result, na\"ive sequential implementations of iterative reconstructionsproduce unfeasibly long runtimes. Their computational intensity is asubstantial barrier to their adoption in clinical MRI practice.A powerful new family of massively parallel microprocessor architectures hasemerged simultaneously with the development of these new reconstructiontechniques.Due to fundamental limitations in silicon fabrication technology,sequential microprocessors reached the power-dissipation limits ofcommodity cooling systems in the early 2000's.The techniques used by processor architects to extract instruction-levelparallelism from sequential programs face ever-diminishing returns, and furtherperformance improvement of sequential processors via increasing clock-frequencyhas become impractical.However, circuit density and process feature sizes still improve atMoore's Law rates. With every generation of silicon fabrication technology,a larger number of transistors are available to system architects.Consequently, all microprocessor vendors now exclusively produce multi-coreparallel processors.Additionally, the move towards on-chip parallelism has allowed processorarchitects a larger degree of freedom in the design of multi-threaded pipelinesand memory hierarchies.Many of the inefficiencies inherent in superscalar out-of-order design arebeing replaced by the high efficiency afforded by throughput-oriented designs.The move towards on-chip parallelism has resulted in a vast increasein the amount of computational power available in commodity systems.However, this move has also shifted the burden of computational performancetowards software developers.In particular, the highly efficient implementation of MRI reconstructionson these systems requires manual parallelization and optimization.Thus, while ubiquitous parallelism provides a solution to the computationalintensity of iterative MRI reconstructions, it alsoposes a substantial software productivity challenge.In this thesis, we propose that a principled approach to the design andimplementation of reconstruction algorithms can ameliorate this softwareproductivity issue.We draw much inspiration from developments in thefield of computational science, which has faced similar parallelizationand software development challenges for several decades.We propose a Software Architecture for the implementation of reconstructionalgorithms, which composes two Design Patterns that originated inthe domain of massively parallel scientific computing.This architecture allows for the most computationally intense operationsperformed by MRI reconstructions to be implemented as re-usable libraries.Thus the software development effort required to produce highly efficientand heavily optimized implementations of these operations can be amortizedover many different reconstruction systems.Additionally, the architecture prescribes several different strategies formapping reconstruction algorithms onto parallel processors, easing theburden of parallelization.We describe the implementation of a complete reconstruction, $\ell_1$-SPIRiT,according to these strategies.$\ell_1$-SPIRiT is a general reconstruction framework that seamlessly integratesall three of the scan acceleration techniques mentioned above.Our implementation achieves substantial performance improvement over baseline,and has enabled substantial clinical evaluation of its approach to combiningParallel Imaging and Compressive Sensing.Additionally, we include an in-depth description of the performance optimizationof the non-uniform Fast Fourier Transform (nuFFT), an operation used in allnon-Cartesian reconstructions.This discussion complements well our description of $\ell_1$-SPIRiT, which wehave only implemented for Cartesian samplings