Home My Page Projects Code Snippets Project Openings diderot

# SCM Repository

[diderot] View of /branches/pure-cfg/doc/field-norm/paper.tex
 [diderot] / branches / pure-cfg / doc / field-norm / paper.tex

# View of /branches/pure-cfg/doc/field-norm/paper.tex

Sat Nov 13 16:02:07 2010 UTC (10 years, 5 months ago) by jhr
File size: 3968 byte(s)
  Creating a branch to explore a pure CFG IL

\documentclass[11pt]{article}

\setlength{\textwidth}{6in}
\setlength{\oddsidemargin}{0.25in}
\setlength{\evensidemargin}{0.25in}
\setlength{\parskip}{5pt}

\input{defs}

\title{Normalization of Field and Probe Expressions}
\author{
John Reppy \\
University of Chicago \\
{\small\tt{}jhr@cs.uchicago.edu} \\
}
\date{\today}

\newcommand{\Fnorm}[1]{\mathcal{F}\LDB{}#1\RDB{}}
\newcommand{\Pnorm}[1]{\mathcal{P}\LDB{}#1\RDB{}}

\begin{document}

\maketitle
\thispagestyle{empty}

\bibliographystyle{../common/alpha}
\bibliography{../common/strings-short,../common/manticore}

\section{Introduction}

This note describes the symbolic transformations that are applied to field and probe expressions in
the Diderot compiler.
The purpose of these transformations is to make the actual compilation of probe operations
more straightforward.
We describe these transformations using three simple expression languages.
The first corresponds to the Diderot surface-language syntax for field and probe expressions.
The second language has the property that derivative operations have been pushed down to the
convolution kernels, and the third language reduces probes to work on images.

\section{The formal model}

In the discussion below, we  use a number of notational conventions that are
summarized in the following table:
\begin{center}
\begin{tabular}{cp{4in}}
$V$ & an image \\
$F$, $G$ & fields \\
$h$ & a piecewise polynomial convolution kernel \\
$s$ & a scalar \\
$\vecx$ & a position in world space
\end{tabular}%
\end{center}%

The source language of field expressions is
\begin{displaymath}
\begin{array}{rcll}
F & ::= & V\circledast{}h & \text{convolution} \\
& \mid & F+G & \text{addition} \\
& \mid & s F & \text{scaling} \\
& \mid & \nabla{}F & \text{differentiation}
\end{array}%
\end{displaymath}%
We normalize these expressions by pushing the differentiation operators down to the
kernels, which results in the following language of field expressions:
\begin{displaymath}
\begin{array}{rcll}
\hat{F} & ::= & V\circledast{}h^k & \text{convolution with $k$th derivative of $h$} \\
& \mid & \hat{F}+\hat{G} & \text{addition} \\
& \mid & s \hat{F} & \text{scaling} \\
\end{array}%
\end{displaymath}%
The normalization rules are as follows:
\begin{eqnarray*}
\Fnorm{\nabla{}(V\circledast{}h^k)} & = & V\circledast{}h^{k+1} \\
\Fnorm{\nabla{}(F+G)} & = & \Fnorm{\nabla{}F} + \Fnorm{\nabla{}G} \\
\Fnorm{\nabla{}(s F)} & = & s (\Fnorm{\nabla{}F})
\end{eqnarray*}%

The syntax of probe operations (after field normalization) is
\begin{displaymath}
\hat{F}\mkw{@}\vecx
\end{displaymath}%
We normalize these expressions by pushing the probes down to the leaves
and rewriting them as probes into images with the following syntax
\begin{displaymath}
V\mkw{@}_{h^k}\vecx
\end{displaymath}%
The probe normalization rules are as follows:
\begin{eqnarray*}
\Pnorm{(V\circledast{}h^k)\mkw{@}\vecx} & = & V\mkw{@}_{h^k}\vecx \\
\Pnorm{(\hat{F}+\hat{G})\mkw{@}\vecx} & = & \Pnorm{\hat{F}\mkw{@}\vecx} + \Pnorm{\hat{G}\mkw{@}\vecx} \\
\Pnorm{(s \hat{F})\mkw{@}\vecx} & = & s (\Pnorm{\hat{F}\mkw{@}\vecx})
\end{eqnarray*}%

\section{An example}
Consider the following Diderot fragment (taken from the \texttt{vr-lite.diderot} example).
\begin{lstlisting}[mathescape=true]
$\cdots$
field#1(3)[] F = img $\circledast$ bspln3;
$\cdots$
real val = F@pos;
vec3 grad = ($\nabla$ F)@pos;
\end{lstlisting}%
Applying the transformations will result in
\begin{lstlisting}[mathescape=true]
real val = img $\mkw{@}_{\mathtt{bspln3}}$ pos;
vec3 grad = img $\mkw{@}_{\mathtt{bspln3}^1}$ pos;
\end{lstlisting}%

\section{Implementation in the compiler}
These transformations are mostly implemented on the SimpleAST representation.
The final step of translating a probe of $(V\circledast{}h^k)\mkw{@}\vecx$
to $V\mkw{@}_{h^k}\vecx$ is done in the conversion to the HighIL representation.

\end{document}