Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] View of /branches/opencl/doc/diderot.tex
ViewVC logotype

View of /branches/opencl/doc/diderot.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1673 - (download) (as text) (annotate)
Fri Dec 9 19:56:10 2011 UTC (7 years, 8 months ago) by jhr
File size: 7676 byte(s)
  Creating a branch for hacking on the OpenCL target
\documentclass[11pt]{article}

\input{defs}

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

\title{Diderot design}
\author{
  Gordon Kindlmann \\
  University of Chicago \\
  {\small\tt{}glk@cs.uchicago.edu} \\
\and
  John Reppy \\
  University of Chicago \\
  {\small\tt{}jhr@cs.uchicago.edu} \\
\and
  Thomas Schultz \\
  University of Chicago \\
  {\small\tt{}t.schultz@uchicago.edu} \\
}
\date{\today}

\begin{document}

\maketitle
\thispagestyle{empty}

\section{Introduction}
This document is a semi-formal design of Diderot.

\section{Types}
The syntax of Diderot types is given in \figref{fig:types}.
\begin{figure}[t]
  \begin{displaymath}
    \begin{array}{rclr}
      \rho  & ::= & $\ldots$ & \text{NRRD scalar types} \\[1em]
      \iota & ::= & \TYbool & \text{booleans} \\
           & \mid & \TYint & \text{integers} \\[1em]
      % \mu for memory, where images of rawtensors will live (or on disk)
      \mu & ::= & \TYrawten{\Seq{d}}{\rho} & \begin{minipage}[l]{3in}\begin{flushright}
          tensors of order $|\Seq{d}|$ and dimensions $\Seq{d}$,\\with coefficients of type $\rho$
          \end{flushright}\end{minipage}\\[1em]
      \theta & ::= & \TYtensor{\Seq{d}} & \begin{minipage}[l]{3in}\begin{flushright}
          tensors of order $|\Seq{d}|$ and dimensions $\Seq{d}$,\\with real coefficients
          \end{flushright}\end{minipage}\\[1em]
      \tau & ::= & \iota \\
           & \mid & \theta \\
           & \mid & \TYmatrix{n}{m} & \text{$n\times{}m$ matrix} \\
           & \mid & \TYimage{d}{\mu} & \text{$d$-dimension image of $\mu$ values}\\
           & \mid & \TYkern{k} & \text{convolution kernel with $k$ derivatives} \\
           & \mid & \TYfield{k}{d}{\theta} & \text{$d$-dimension field of $\theta$ values with $k$ derivatives} \\
    \end{array}%
  \end{displaymath}%
  where $o\in\Nat$ is the tensor order, $d,n,m\in\SET{2,3}$ are dimensions,
  and $k\in\Nat$ is the differentiability of a field.
  \caption{Diderot types}
  \label{fig:types}
\end{figure}%
We use some type abbreviations for common cases:
\begin{eqnarray*}
  \TYreal & = & \TYtensor{\epsilon} \quad\text{for any $d$} \\
  \TYvec{d} & = & \TYtensor{d}
\end{eqnarray*}%

\section{Operations}

\subsection{Scalar operations}
\noindent{}\point Arithmetic:
\begin{displaymath}
  \begin{array}{cl}
    \BinopTy{{\odot}}{\tau}{\tau}{\tau}
    & \text{for $\odot\in\SET{\OP{+},\OP{-},\OP{*},\OP{/}}$ and $\tau\in\SET{\TYint,\TYreal}$} \\
    \UnopTy{\OP{-}}{\tau}{\tau}
    & \text{for $\tau\in\SET{\TYint,\TYreal}$}
  \end{array}%
\end{displaymath}%

\noindent{}\point Comparisons:
\begin{displaymath}
  \BinopTy{{\odot}}{\tau}{\tau}{\TYbool}
  \qquad\text{for $\odot\in\SET{\OP{<},{\leq},\OP{=},{\neq}\OP{>},{\geq}}$ and $\tau\in\SET{\TYint,\TYreal}$}
\end{displaymath}%


\subsection{Matrix operations}

\subsection{Tensor operations}

\noindent{}\point Addition:
\begin{displaymath}
  \BinopTy{{\odot}}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d}}}
  \qquad\text{for $\odot\in\SET{\OP{+},\OP{-}}$}
\end{displaymath}%

\noindent{}\point Negation:
\begin{displaymath}
  \UnopTy{\OP{-}}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d}}}
\end{displaymath}%

\noindent{}\point Scalar division:
\begin{displaymath}
  \BinopTy{\OP{/}}{\TYtensor{\Seq{d}}}{\TYreal}{\TYtensor{\Seq{d}}}
\end{displaymath}%

\noindent{}\point Scalar multiplication (scalar times order-N):
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{\OP{*}}{\TYreal}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d}}} \\
    \BinopTy{\OP{*}}{\TYtensor{\Seq{d}}}{\TYreal}{\TYtensor{\Seq{d}}}
  \end{array}%
\end{displaymath}%

\noindent{}\point Tensor scalar multiplication (contraction of two order-N 
tensors down to a scalar, \eg{} dot product of vectors, double dot
product of 2nd-order tensors)
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{{?}}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d}}}{\TYreal} 
  \end{array}%
\end{displaymath}%
Defined by $c = A_{\vec{i}}B_{\vec{i}}$
~(\eg{} $\mathbf{a}\cdot\mathbf{b} = a_ib_i$  or $\mathbf{A:B} = A_{ij}B_{ij}$)
NOTE: In this and subsequent index notation expressions, a vector over the index variable
(\eg{} $\vec{i}$) means that the variable is in fact standing for a sequence of
contiguous index variables \\
Possible direct notation syntax: ~~ {\tt .} (period) ~~ {\tt :} (colon) ~~ {\tt dot} ~~ {\tt o}

\noindent{}\point Tensor product (aka outer product; order output is sum of orders)
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{{?}}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d'}}}{\TYtensor{\Seq{d}\Seq{d'}}} 
  \end{array}%
\end{displaymath}%
Defined by $C_{\vec{i}\vec{j}} = A_{\vec{i}}B_{\vec{j}}$ \\
Possible direct notation syntax: ~~ {\tt x} ~~ {\tt (x)} ~~ {\tt out}

\noindent{}\point Matrix Multiply
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{{?}}{\TYtensor{\Seq{d}}}{\TYtensor{d_1 d_2}}{\TYtensor{\Seq{d}}} \\
    \BinopTy{{?}}{\TYtensor{d_1 d_2}}{\TYtensor{\Seq{d}}}{\TYtensor{\Seq{d}}} 
  \end{array}%
\end{displaymath}%
Defined by $C_{i\vec{k}} = A_{ij}B_{j\vec{k}}$ and $C_{\vec{i}k} = B_{\vec{i}j}A_{jk}$ 
~(\eg{} $u_i = M_{ij}v_j$ or $T_{ijl} = S_{ijk}M_{kl}$) \\
Possible direct notation syntax: ~~ ?

\noindent{}\point Contracting out last or first index of tensor (order $o \geq 1$) 
with vector 
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{{?}}{\TYtensor{d'\Seq{d}}}{\TYvec{d}}{\TYtensor{\Seq{d}}} \\
    \BinopTy{{?}}{\TYvec{d}}{\TYtensor{d'\Seq{d}}}{\TYtensor{\Seq{d}}}
  \end{array}%
\end{displaymath}%
Defined by $C_{\vec{i}} = A_{\vec{i}j}v_j$ and $C_{\vec{j}} = v_iA_{j\vec{j}}$ \\
Possible direct notation syntax: ~~ ?

\noindent{}\point Arbitrary ``tensor comprehension''. The product can also be
expressed in general index notation, and which may increase, preserve, or
decrease the tensor order.
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{{?}}{\TYtensor{\Seq{d}}}{\TYtensor{p}{d}}{\TYtensor{q}{d}} 
  \end{array}%
\end{displaymath}%
Defined by the conventions of Einstein summation notation. \\
Possible syntax: {\tt <A.i.j.k,B.j.k.l>} ~~ {\tt <A\_i\_j\_k,B\_j\_k\_l>}

\subsection{Field operations}

\noindent{}\point Creation from an image:
\begin{displaymath}
  \BinopTy{\OPconvolve}{\TYkern{k}}{\TYimage{d'}{\TYrawten{\Seq{d}}{\rho}}}{\TYfield{k}{d'}{\TYtensor{\Seq{d}}}}
\end{displaymath}%

\noindent{}\point Scalar multiplication:
\begin{displaymath}
  \begin{array}{c}
    \BinopTy{\OP{*}}{\TYreal}{\TYfield{k}{d}{\theta}}{\TYfield{k}{d}{\theta}} \\
    \BinopTy{\OP{*}}{\TYfield{k}{d}{\theta}}{\TYreal}{\TYfield{k}{d}{\theta}}
  \end{array}%
\end{displaymath}%

\noindent{}\point Scalar division:
\begin{displaymath}
  \BinopTy{\OP{/}}{\TYfield{k}{d}{\theta}}{\TYreal}{\TYfield{k}{d}{\theta}}
\end{displaymath}%

\noindent{}\point Negation:
\begin{displaymath}
  \UnopTy{\OP{-}}{\TYfield{k}{d}{\theta}}{\TYfield{k}{d}{\theta}}
\end{displaymath}%

\noindent{}\point Addition:
\begin{displaymath}
  \begin{array}{c}
  \BinopTy{{\odot}}{\TYfield{k}{d}{\theta}}{\theta}{\TYfield{k}{d}{\theta}} \\
  \BinopTy{{\odot}}{\theta}{\TYfield{k}{d}{\theta}}{\TYfield{k}{d}{\theta}} \\
  \BinopTy{{\odot}}{\TYfield{k_1}{d}{\theta}}{\TYfield{k_2}{d}{\theta}}{\TYfield{\min(k_1,k_2)}{d}{\theta}}
  \end{array}%
  \qquad\text{for $\odot\in\SET{\OP{+},\OP{-}}$}
\end{displaymath}%

\noindent{}\point Differentiation:
\begin{displaymath}
  \UnopTy{\OPdiff}{\TYfield{k}{d'}{\TYtensor{\Seq{d}}}}{\TYfield{k-1}{d'}{\TYtensor{d'\Seq{d}}}}
  \qquad\text{for $k > 0$}
\end{displaymath}%

\noindent{}\point Probing:
\begin{displaymath}
  \BinopTy{\OP{@}}{\TYfield{k}{d}{\theta}}{\TYvec{d}}{\theta}
\end{displaymath}%

\end{document}

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0