Home My Page Projects Code Snippets Project Openings diderot

# SCM Repository

[diderot] View of /trunk/doc/whitepaper/intro.tex
 [diderot] / trunk / doc / whitepaper / intro.tex

# View of /trunk/doc/whitepaper/intro.tex

Tue Aug 17 18:09:10 2010 UTC (11 years, 10 months ago) by jhr
File size: 6963 byte(s)
  minor edits

%!TEX root = paper.tex
%

\section{Introduction}

The analysis of structure in three-dimensional images is increasingly
valuable for biomedical research and computational science.
\emph{Computed Tomography} (CT) and \emph{Magnetic Resonance Imaging}
(MRI) scanners continue
to improve in speed and resolution, driving clinical research in
image-based screening and diagnosis, and recent microscopy techniques
are producing detailed snapshots of cellular processes for biomedical
research.
Regardless of the image modality or application, the values
stored at individual samples in the three-dimensional image are
measurements of some essential physical or biological quantity, and
the spatial structure of those values indirectly represents relevant
features of the scanned object or system.
Image analysis plays the
crucial role of detecting and extracting the salient image structure
in order to build geometric and quantitative models of anatomy or
organization.

%Volumetric imagery
%also arises in non-destructive testing of manufacturing, siesmology
%and geophysics, and homeland security.

Ideally, image analysis research creates efficient and powerful tools
that increase the scientific utility and impact of image acquisitions.
In practice, a combination of factors limits the development and
application of novel image-analysis methods.
The computational burden
of processing images is increasing as devices produce images of higher
resolution (\eg{}, typical CT scans have gone from $128^3$ to roughly $512^3$
resolutions~\cite{GLK:Reiser2008}).
With the latest scanning technologies, it is also more common for the values measured at
each sample to be multi-dimensional rather than a single scalar, which
further complicates implementing mathematically correct methods.
% diffusion-weighted MRI now commonly measures at least 30 value per
% sample, and the simplest tensor models estimated from these
% measurements have at least six degrees of freedom per point.
While image-analysis algorithms are computationally expensive, there
is hope in being able to exploit modern parallel hardware to greatly
reduce their running time.
Unfortunately, the scientists involved in
creating the latest imaging experiments and acquisitions are usually
not in a position to implement correspondingly sophisticated analysis
algorithms that run on the latest parallel hardware, which reinforces the
gap between the class of methods advanced by computer science
research and those that gain currency in scientific research
applications.

We propose a new way to express and implement image-analysis algorithms that
strives for both efficiency and flexibility.
Our proposed approach is based on a \emph{domain-specific language} (DSL)
that encapsulates the mathematical ingredients of working in
a smooth image domain (reconstructed from discrete samples) and
offers a powerful abstraction with which analysis algorithms can be
decomposed into a coordinated set of actors that capture the parallelism
inherent in these algorithms.

One advantage of DSLs is that they provide a high-level programming model
that allows domain experts to program using the natural notation and concepts of the domain.
For example, parser generators, such as Yacc~\cite{yacc}, allow language syntax
to be specified using the notation of context-free grammars, and form compilers,
such as FFC~\cite{ffc}, take high-level descriptions of a finite element variational form
and generate low-level C code for efficient evaluation of the element tensor
and associated quantities.
A second advantage is that DSLs allow for \emph{domain-specific} optimizations,
which can result in highly-efficient implementations.
Thirdly, we can view a DSL as a program generator, which have proven to be
a very effective way to get portable high-performance code.
For example, the leading FFT library (FFTW~\cite{fftw}) uses a program generator
to generate versions of the FFT algorithm that are specialized for many different
hardware targets.
Thus, DSLs can provide both a very high-level programming model with very high-performance
executables on a variety of target platforms.

As others have argued~\cite{hanrahan:dsl-gpu}, the use of DSLs for parallelism
Getting the maximum performance for a parallel program on a particular parallel platform
usually requires hand tuning the program for the given platform.
But such a tuned program is not portable and will have to be retuned, or even rewritten,
to take full advantage of any new platform.
For example, clusters, multicore SMP systems, and GPUs (Graphics Processing Units)
are parallel systems that are found in many labs, and that have very different computational
and memory-system characteristics.
As the FFTW library demonstrates, domain-specific program generation is one solution to
the portable performance problem.
DSLs provide a high-level interface to such program generators.
Our proposed research follows this model of fixing the application domain (to image
analysis in our case) and combining domain-specific optimizations with target-specific
program generation to get a high-level programming language with high performance.

There are three equally important aspects of the proposed research.
\begin{enumerate}
\item
To design a high-level, mathematical programming model that allows existing
visualization and analysis methods to be expressed in simple and readily
understood programs.
\item
To test and evolve this programming model by exploring a range of
both established and novel image-analysis algorithms.
\item
And to develop techniques for implementing the programming
model so that a given program can be compiled to high-performance
implementations on a variety of parallel-hardware platforms without
hand-tuning the code for each platform.
\end{enumerate}%

This proposal is a collaboration between PI Reppy, who has extensive experience
in both parallel and sequential language design and implementation, and PI Kindlmann, who
has extensive domain expertise in the area of image analysis.
The proposed research will make contributions to both the area of parallel-language
design and implementation and to the area of image analysis and visualization.

The proposal is organized as follows.
In the next section, we give an overview of the image-analysis domain
and the numeric techniques that have proven useful for extracting features
from image data.
This survey motivates the major aspects of our proposed DSL design, which we
discuss in \secref{sec:design}.
We then discuss the challenges of implementing this language on parallel hardware,
with a particular focus on GPUs, in \secref{sec:impl}.
Our research plan is described in \secref{sec:plan}, followed by a discussion of
the broader impact of the proposed research.
Finally, we describe the PI backgrounds and existing NSF support.
Related work is discussed throughout the proposal.