This Small Business Innovation Research (SBIR) Phase I project proposes to enable computer generation of high performance software for image processing problems. For computing intensive functions, the by far most common approach is hand-optimization for every new platform. SpiralGen's technology has the potential to demonstrate that it is possible to automatically produce performance-competitive code (code that is a good as human-written code and takes optimal advantage of multiple cores) for an important class of image processing functions. The approach is based on a blend of mathematics, programming languages, symbolic computation, compilers, and optimization.
Image processing (including its close cousin video processing) is one of the most demanding computing domains due to its higher-dimensional nature. Key application domains that can benefit from the proposed technology include military applications (surveillance, target recognition), consumer multimedia processing, medical imaging (computer tomography), oil exploration, and computer vision. The company's technology has the ability to provide a longterm solution to the porting and optimization problem: applications are ported by regenerating performance critical components optimized for the new platform. As a result, new more capable platforms can be deployed faster.
There is broad interest in the medical imaging community to decrease data acquisition / analysis times, improve data resolution, and reduce patient radiation dose. For example, in applications such as computed tomography (CT) diagnostic imaging, improved iterative image reconstruction algorithms can enable radiation dose reduction by providing a higher tolerance to noise (i.e., lower radiation level) while maintaining image quality. However, these iterative reconstruction algorithms can be impractically slow, taking several hours on realistic data sets, thus creating a barrier to deployment. Attempts to reduce reconstruction times by optimizing the software using human optimization experts have been less than successful to date. SpiralGen can solve this problem by optimizing the algorithms using automated software optimization technology, developed at Carnegie Mellon University over the past decade, called Spiral. The goal of Phase I of this SBIR program was to demonstrate the application of Spiral technology to improve the performance of iterative image reconstruction algorithms, and thereby enable their widespread deployment. As a demonstration we chose a recently proposed algorithm [Lustig 2008] that uses compressed sensing (CS) to reconstruct undersampled magnetic resonance imaging (MRI) images. This approach applies iterative techniques to "fill in" missing parts of the data, and has proven to be very effective in reconstructing clinical quality MRI images from undersampled data. However, CS-based reconstruction is a computationally expensive iterative algorithm. The computation time to reconstruct a single MRI slice measures in minutes, which is clinically unacceptable. The attached graph shows reconstruction times for a single 512x512 (0.5 sec vs. 16 sec), 1Kx1K (2.3 sec vs. 95 sec), and 2Kx2K (11.6 sec vs. 378 sec) image slice (45 algorithm iterations) for two implementations: a standard C code implementation of the Lustig algorithm, and an implementation optimized by Spiral. The Spiral optimized implementation effectively utilizes all 12 available cores and improves performance 30-40X by exploiting the in-slice parallelism. (Traditional optimization efforts would hit memory bandwidth barriers, limiting CPU core utilization to about 4 to 5 cores before performance improvements begin to flatten out.) The optimization achieved here can be further combined with parallel reconstruction of multiple slices to more efficiently use all of the available computation power. In Phase II of this SBIR program, SpiralGen intends to apply the same automated code generation technology to iterative algorithms for other imaging modalities such as CT and ultrasound.
