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

SCM Repository

[diderot] Annotation of /trunk/doc/probe/paper.tex
ViewVC logotype

Annotation of /trunk/doc/probe/paper.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 160 - (view) (download) (as text)

1 : jhr 156 \documentclass[11pt]{article}
2 :    
3 :     \input{defs}
4 :     \usepackage{graphicx}
5 :     \usepackage{listings}
6 :     \lstset{
7 : jhr 160 basicstyle=\ttfamily\small,
8 : jhr 156 keywordstyle=\bfseries,
9 :     showstringspaces=false,
10 :     }
11 : jhr 160 \lstdefinelanguage{OpenCL}[]{C}{%
12 :     morekeywords={
13 :     char2,char4,char8,char16,
14 :     uchar2,uchar4,uchar8,uchar16,
15 :     short2,short4,short8,short16,
16 :     ushort2,ushort4,ushort8,ushort16,
17 :     int2,int4,int8,int16,
18 :     uint2,uint4,uint8,uint16,
19 :     long2,long4,long8,long16,
20 :     ulong2,ulong4,ulong8,ulong16,
21 :     float2,float4,float8,float16,
22 :     ufloat2,ufloat4,ufloat8,ufloat16,
23 :     double2,double4,double8,double16,
24 :     udouble2,udouble4,udouble8,udouble16,
25 :     constant,__constant,kernel,__kernel,private,__private},
26 :     moredirectives={version},
27 :     deletekeywords={}
28 :     }
29 : jhr 156
30 :     \lstset{
31 :     language=C,
32 :     }
33 :    
34 :     \setlength{\textwidth}{6in}
35 :     \setlength{\oddsidemargin}{0.25in}
36 :     \setlength{\evensidemargin}{0.25in}
37 :     \setlength{\parskip}{5pt}
38 :    
39 :     \newcommand{\matM}{\mathbf{M}}
40 : jhr 157 \newcommand{\vecx}{\mathbf{x}}
41 : jhr 159 \newcommand{\vecp}{\mathbf{p}}
42 : jhr 156 \newcommand{\vecn}{\mathbf{n}}
43 :     \newcommand{\vecf}{\mathbf{f}}
44 :     \newcommand{\VEC}[1]{\left\langle{#1}\right\rangle}
45 :     \newcommand{\FLOOR}[1]{\left\lfloor{#1}\right\rfloor}
46 :    
47 :     \title{Compiling probe operations for Diderot}
48 :     \author{
49 :     John Reppy \\
50 :     University of Chicago \\
51 :     {\small\tt{}jhr@cs.uchicago.edu} \\
52 :     }
53 :     \date{\today}
54 :    
55 :     \begin{document}
56 :    
57 :     \maketitle
58 :     \thispagestyle{empty}
59 :    
60 :     \bibliographystyle{../common/alpha}
61 :     \bibliography{../common/strings-short,../common/manticore}
62 :    
63 :     \section{Introduction}
64 :    
65 :     This note describes the code needed to implement a probe of a field operation.
66 :    
67 :     In the discussion below, we use $\matM^{-1}$ for the homogeneous matrix that maps from world
68 : jhr 157 coordinates to image coordinates and use $\vecx$ for the position vector.
69 : jhr 156
70 :     \section{Probing a 1D scalar field}
71 :     The simplest case is probing a 1D scalar field $F = V\circledast{}h$, where $s$ is the support
72 :     of $h$.
73 : jhr 160 The probe $F\mkw{@}p$ is computed as follows:
74 : jhr 156 \begin{eqnarray*}
75 : jhr 160 \left[\begin{array}{c} x \\ 1 \end{array}\right] & = & \matM^{-1} \left[\begin{array}{c} p \\ 1 \end{array}\right] \qquad \text{\textit{transform to image space}} \\
76 :     n & = & \FLOOR{x} \qquad \text{\textit{integer part of position}} \\
77 :     f & = & x - f \qquad \text{\textit{fractional part of position}} \\
78 :     F\mkw{@}p & = & \sum_{i=1-s}^s {V(n+i) h(f - i)}
79 : jhr 156 \end{eqnarray*}%
80 :     The convolution $h$ is represented as a symmetric piecewise polynomial formed
81 :     from $s$ polynomials $h_1,\,\ldots,\,h_s$.
82 :     \begin{displaymath}
83 :     h(x) = \left\{\begin{array}{ll}
84 : jhr 158 0 & \text{$x < -s$} \\
85 : jhr 157 h_i(-x) & \text{$-s \leq -i \leq x < 1-i \leq 0$} \\
86 : jhr 156 h_i(x) & \text{$0 < i-1 \leq x < i \leq s$} \\
87 :     0 & \text{$x > s$} \\
88 :     \end{array}\right.
89 :     \end{displaymath}%
90 :     Thus, we can rewrite the probe computation as
91 :     \begin{displaymath}
92 : jhr 157 F\mkw{@}x = \sum_{i=1-s}^{0} {V(n+i) h_{1-i}(i - f)} + \sum_{i=1}^s {V(n+i) h_i(f - i)}
93 : jhr 156 \end{displaymath}%
94 :     \figref{fig:1d-probe} illustrates the situation for a kernel $h$ with support $s = 2$,
95 :     and \figref{fig:1d-probe-code} gives the C code for the probe operation, assuming that
96 :     $h$ is represented by third-degree polynomials.
97 :     \begin{figure}[t]
98 :     \begin{center}
99 :     \includegraphics[scale=0.8]{pictures/convo}
100 :     \end{center}%
101 :     \caption{1D scalar probe}
102 :     \label{fig:1d-probe}
103 :     \end{figure}%
104 :    
105 :     \begin{figure}[t]
106 :     \begin{quote}
107 : jhr 160 \lstset{language=C}
108 : jhr 156 \begin{lstlisting}
109 :     double img[]; // image data
110 :     double h1[4], h2[4]; // kernel
111 :    
112 :     double probe (double x)
113 :     {
114 :     double imgX = transform(x); // image-space position
115 :     double n, f;
116 :    
117 :     f = modf (imgPos, &n);
118 :    
119 : jhr 160 double value = 0.0, t;
120 : jhr 156
121 : jhr 160 t = -1.0 - f;
122 :     value += img[n-1] * (h2[0] + t*(h2[1] + t*(h2[2] + t*h2[3])));
123 :     t = -f;
124 :     value += img[n] * (h1[0] + t*(h1[1] + t*(h1[2] + t*h1[3])));
125 :     t = f - 1.0;
126 :     value += img[n+1] * (h1[0] + t*(h1[1] + t*(h1[2] + t*h1[3])));
127 :     t = f - 2.0;
128 :     value += img[n+2] * (h2[0] + t*(h2[1] + t*(h2[2] + t*h2[3])));
129 : jhr 156
130 :     return value;
131 :     }
132 :     \end{lstlisting}%
133 :     \end{quote}%
134 : jhr 157 \caption{Computing $F\mkw{@}x$ for a 1D scalar field in C}
135 : jhr 156 \label{fig:1d-probe-code}
136 :     \end{figure}
137 : jhr 160 If we look at the four lines that define \texttt{value}, we see an opportunity for
138 :     using SIMD parallelism to speed the computation.
139 :     \figref{fig:1d-probe-code-opencl} gives the OpenCL for for the probe function, where
140 :     we have lifted the kernel coefficients into the vector constants \texttt{a}, \texttt{b},
141 :     \texttt{c}, and \texttt{d}.
142 : jhr 156 \begin{figure}[t]
143 :     \begin{quote}
144 : jhr 160 \lstset{language=OpenCL}
145 : jhr 156 \begin{lstlisting}
146 :     double4 d = (double4)(h2[0], h1[0], h1[0], h2[0]); // x^0 coeffs
147 :     double4 c = (double4)(h2[1], h1[1], h1[1], h2[1]); // x^1 coeffs
148 :     double4 b = (double4)(h2[2], h1[2], h1[2], h2[2]); // x^2 coeffs
149 :     double4 a = (double4)(h2[3], h1[3], h1[3], h2[3]); // x^3 coeffs
150 :    
151 :     double probe (double x)
152 :     {
153 :     double imgX = transform(x); // image-space position
154 :     double n, f;
155 :    
156 :     f = modf (imgPos, &n);
157 :    
158 :     double4 v = (double4)(img[n-1], img[n], img[n+1], img[n+2]);
159 : jhr 160 double4 t = (double4)(-1.0 - f, -f, f - 1.0, f - 2.0);
160 :     return dot(v, d + t*(c + t*(b + t*a)));
161 : jhr 156 }
162 :     \end{lstlisting}%
163 :     \end{quote}%
164 : jhr 157 \caption{Computing $F\mkw{@}x$ for a 1D scalar field in OpenCL}
165 : jhr 156 \label{fig:1d-probe-code-opencl}
166 :     \end{figure}
167 :    
168 :     \section{Probing a 3D scalar field}
169 :    
170 :     The more common case is when the field is a convolution of a scalar 3-dimensional
171 :     field ($F = V\circledast{}h$).
172 :     Let $s$ be the support of $h$.
173 : jhr 159 Then the probe $F\mkw{@}\vecp$ is computed as follows:
174 : jhr 156 \begin{eqnarray*}
175 : jhr 159 \vecx & = & \matM^{-1} \vecp \qquad \text{\textit{transform to image space}} \\
176 :     \vecn & = & \FLOOR{\vecx} \qquad \text{\textit{integer part of position}} \\
177 :     \vecf & = & \vecx - \vecn \qquad \text{\textit{fractional part of position}} \\
178 :     F\mkw{@}\vecp & = & \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h(\vecf_x - i) h(\vecf_y - j) h(\vecf_z - k)}}}
179 : jhr 156 \end{eqnarray*}%
180 : jhr 160 Note that the kernel $h$ is evaluated $2s$ times per axis (\ie{}, $6s$ times in 3D).
181 : jhr 156
182 :     \begin{figure}[t]
183 :     \begin{quote}
184 : jhr 160 \lstset{language=C}
185 : jhr 156 \begin{lstlisting}
186 :     typedef double vec3[3];
187 :    
188 :     typedef struct {
189 :     int degree;
190 :     double coeff[];
191 :     } polynomial;
192 :    
193 :     typedef struct {
194 :     int support;
195 :     polynomial *segments[];
196 :     } kernel;
197 :    
198 :     double probe (vec3 ***img, kernel *h, vec3 pos)
199 :     {
200 :     }
201 :     \end{lstlisting}%
202 :     \end{quote}%
203 : jhr 157 \caption{Computing $F\mkw{@}\vecx$ for a 3D scalar field in C}
204 : jhr 156 \end{figure}
205 :    
206 : jhr 159 \section{Probing a 3D derivative field}
207 :     We next consider the case of probing the derivative of a scalar field $F = V\circledast{}h$, where $s$ is the support
208 :     of $h$.
209 :     The probe $(\mkw{D}\;F)\mkw{@}\vecp$ produces a vector result as follows:
210 :     \begin{eqnarray*}
211 :     \vecx & = & \matM^{-1} \vecp \qquad \text{\textit{transform to image space}} \\
212 :     \vecn & = & \FLOOR{\vecx} \qquad \text{\textit{integer part of position}} \\
213 :     \vecf & = & \vecx - \vecn \qquad \text{\textit{fractional part of position}} \\
214 :     (\mkw{D}\;F)\mkw{@}\vecp & = & \left[\begin{array}{c}
215 :     \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h'(\vecf_x - i) h(\vecf_y - j) h(\vecf_z - k)}}} \\
216 :     \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h(\vecf_x - i) h'(\vecf_y - j) h(\vecf_z - k)}}} \\
217 :     \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h(\vecf_x - i) h(\vecf_y - j) h'(\vecf_z - k)}}} \\
218 :     \end{array}\right]
219 :     \end{eqnarray*}%
220 :    
221 : jhr 156 \end{document}

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