A 1.5th order approximation to a 1st draft
authorSam Moore <matches@ucc.asn.au>
Fri, 10 Oct 2014 09:45:09 +0000 (17:45 +0800)
committerSam Moore <matches@ucc.asn.au>
Fri, 10 Oct 2014 09:45:09 +0000 (17:45 +0800)
This will probably have to be good enough, as I need to catch a bus.

14 files changed:
chapters/Background.tex
chapters/Background/FixedPoint.tex
chapters/Background/FloatingPointOnTheGPU.tex
chapters/Background/Floats.tex
chapters/Background/Floats/Definition.tex
chapters/Background/Floats/Operations.tex
chapters/Background/Standards/Precision.tex
chapters/Process.tex
figures/fglrx.png [new file with mode: 0644]
figures/gpufloats.pdf [new file with mode: 0644]
figures/intel.png [new file with mode: 0644]
figures/nvidia.png [new file with mode: 0644]
figures/x86-64.png [new file with mode: 0644]
thesis.pdf

index 10852bb..6a7b3a5 100644 (file)
@@ -13,6 +13,7 @@
 
 
 
+
 \section{Fixed Point and Integer Number Representations}
 \input{chapters/Background/FixedPoint}
 \section{Floating Point Number Representations}
@@ -20,6 +21,8 @@
 \section{Rational Number Representations}
 \input{chapters/Background/Rationals}
 
+\section{Floating Point Operations on the CPU and GPU}
+\input{chapters/Background/FloatingPointOnTheGPU}
 
 
 
index 707dab2..352e9d3 100644 (file)
@@ -3,7 +3,7 @@ A positive real number $z$ may be written as the sum of smaller integers ``digit
        z &= \displaystyle\sum_{i=-\infty}^{\infty} d_i \beta^{i}\label{fixedpointZ}
 \end{align}
 Where each digit $d_i < \beta$ the base. A set of $\beta$ unique symbols are used to represent values of $d_i$.
-A seperate sign '-' can be used to represent negative integers using equation \eqref{fixedpointZ}.
+A seperate sign '-' can be used to represent negative reals using equation \eqref{fixedpointZ}.
 
 To express a real number using equation \eqref{fixedpointZ} in practice we are limited to a finite number of terms between $i = -m$ and $i = n$. Fixed point representations are capable of representing a discrete set of numbers $0 \leq |z| \leq \beta^{n+1}-\beta^{-m}$ seperated by $\Delta z = \beta^{-m} \leq 1$. In the case $m = 0$, only integers can be represented.
 
@@ -13,7 +13,7 @@ Example integer representation in base 10 (decimal) and base 2 (binary):
        1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
 \end{align*}
 
-
+{\bf FIXME} Add Maths reference (Cantor's Diagonal argument) without going into all the Pure maths details
 
 
 
index bd5ea29..0d40fb1 100644 (file)
@@ -1,8 +1,18 @@
-\subsection{Rasterisation on the CPU and GPU}
+%\subsection{Rasterisation on the CPU and GPU}
+
+{\bf FIXME: I feel this section is important but I'm not quite sure where to place it; it could almost work as a paper by itself (in fact I sort of wrote one for it already...)}
 
 Traditionally, vector images have been rasterized by the CPU before being sent to a specialised Graphics Processing Unit (GPU) for drawing\cite{computergraphics2}. Rasterisation of simple primitives such as lines and triangles have been supported directly by GPUs for some time through the OpenGL standard\cite{openglspec}. However complex shapes (including those based on B{\'e}zier curves such as font glyphs) must either be rasterised entirely by the CPU or decomposed into simpler primitives that the GPU itself can directly rasterise. There is a significant body of research devoted to improving the performance of rendering such primitives using the latter approach, mostly based around the OpenGL\cite{openglspec} API\cite{robart2009openvg, leymarie1992fast, frisken2000adaptively, green2007improved, loop2005resolution, loop2007rendering}. Recently Mark Kilgard of the NVIDIA Corporation described an extension to OpenGL for NVIDIA GPUs capable of drawing and shading vector paths\cite{kilgard2012gpu,kilgard300programming}. From this development it seems that rasterization of vector graphics may eventually become possible upon the GPU.
 
 It is not entirely clear how well supported the IEEE-754 standard for floating point computation is amongst GPUs\footnote{Informal technical articles are abundant on the internet --- Eg: Regarding the Dolphin Wii GPU Emulator: \url{https://dolphin-emu.org/blog} (accessed 2014-05-22)}. Although the OpenGL API does use IEEE-754 number representations, research by Hillesland and Lastra in 2004 suggested that many GPUs were not internally compliant with the standard\cite{hillesland2004paranoia}. 
 
-\rephrase{We implemented a GPU and CPU renderer so we could compare them}.
+In order to explore this, we implemented a simple fragment shader to render a circle. Points $x^2 + y^2 < 1$ should be black. When scaled to bounds of width $\approx 10^{-6}$ the edges of the circle become jagged due to imprecision. However, the behaviour is quite different depending on GPU model. A CPU renderer was also implemented to evaluate the same function using IEEE-754 singles.
+
+\begin{figure}[H]
+       \centering
+       \includegraphics[width=0.7\textwidth]{figures/gpufloats.pdf}
+       \caption{Difference in evaluating $x^2 + y^2 < 1$ for the x86\_64 and various GPUs\\
+       The view bounds are identical}
+\end{figure}
+
 %Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations
index 7eba8a2..65a99e4 100644 (file)
@@ -3,8 +3,9 @@
 \input{chapters/Background/Floats/Visualisation}
 
 
-%\subsection{Floating Point Operations}
-%\input{chapters/Background/Floats/Operations}
+\subsection{Floating Point Operations}
+{\bf FIXME:} Appendix?
+\input{chapters/Background/Floats/Operations}
 
 
 \subsection{Arbitrary Precision Floating Point Numbers}
index 62d2c71..33f1a15 100644 (file)
@@ -1,11 +1,14 @@
 Whilst a Fixed Point representation keeps the ``point'' (the location considered to be $i = 0$ in \eqref{fixedpointZ}) at the same position in a string of bits, Floating point representations can be thought of as scientific notation; an ``exponent'' and fixed point value are encoded, with multiplication by the exponent moving the position of the point.
 
+
+{\bf FIXME: Cite properly} The use of floating point arithmetic in computer systems was pioneered by Knuth\cite{}, Goldberg\cite{goldbern1967twentyseven}, Dekker\cite{}, and others, but modern systems are largely compatable with the IEEE-754 standard pioneered by William Kahan in 1985 \cite{ieee754std1985} and revised (also with contributions from Kahan) in 2008\cite{ieee754std2008}.
+
 A floating point number $x$ is commonly represented by a tuple of values $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}: $x = (-1)^{s} \times m \times B^{e}$
 
 Where $s$ is the sign and may be zero or one, $m$ is commonly called the ``mantissa'' and $e$ is the exponent. Whilst $e$ is an integer in some range $\pm e_max$, the mantissa $m$ is a fixed point value in the range $0 < m < B$. 
 
 
-The choice of base $B = 2$ in the original IEEE-754 standard matches the nature of modern hardware. It has also been found that this base in general gives the smallest rounding errors\cite{HFP}. %Early computers had in fact used a variety of representations including $B=3$ or even $B=7$\cite{goldman1991whatevery}, and the revised IEEE-754 standard specifies a decimal representation $B = 10$ intended for use in financial applications\cite{ieee754std2008}\footnote{Eg: The smallest valid unit of currency \$0.01 could not be represented exactly in base 2}. From now on we will restrict ourselves to considering base 2 floats.
+The choice of base $B = 2$ in the original IEEE-754 standard matches the nature of modern hardware. It has also been found that this base in general gives the smallest rounding errors\cite{HFP}. Early computers had in fact used a variety of representations including $B=3$ or even $B=7$\cite{goldman1991whatevery}, and the revised IEEE-754 standard specifies a decimal representation $B = 10$ intended for use in financial applications\cite{ieee754std2008}\footnote{Eg: The smallest valid unit of currency \$0.01 could not be represented exactly in base 2}. From now on we will restrict ourselves to considering base 2 floats.
 
 The IEEE-754 encoding of $s$, $e$ and $m$ requires a fixed number of continuous bits dedicated to each value. Originally two encodings were defined: binary32 and binary64. $s$ is always encoded in a single leading bit, whilst (8,23) and (11,53) bits are used for the (exponent, mantissa) encodings respectively. 
 
index 1a724f9..5624892 100644 (file)
@@ -1,6 +1,5 @@
 
-
-Real values which cannot be represented exactly in a floating point representation must be rounded to the nearest floating point value. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Referring to Figure \ref{floats.pdf} it can be seen that the largest possible rounding error is half the distance between successive floats; this means that rounding errors increase as the value to be represented increases.
+Real values which cannot be represented exactly in a floating point representation must be rounded to the nearest floating point value. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Referring to Figure \ref{floats.pdf} it can be seen that the largest possible rounding error is half the distance between successive floats; this means that rounding errors increase as the value to be represented increases. For the result of a particular operation, the maximum possible rounding error can be determined and is commonly expressed in ``units in the last place'' (ulp), with 1 ulp equivelant to half the distance between successive floats\cite{goldberg1991whatevery}.
 
 
 
index afb5f24..0a9511c 100644 (file)
@@ -1,25 +1,23 @@
 
-We briefly summarise the requirements of the standards discussed so far in regards to the precision of mathematical operations.
-
 \subsection{PostScript}
 The PostScript reference describes a ``Real'' object for representing coordinates and values as follows: ``Real objects approximate mathematical real numbers within a much larger interval, but with limited precision; they are implemented as floating-point numbers''\cite{plrm}. There is no reference to the precision of mathematical operations, but the implementation limits \emph{suggest} a range of $\pm10^{38}$ ``approximate'' and the smallest values not rounded to zero are $\pm10^{-38}$ ``approximate''.
 
 \subsection{PDF}
 PDF defines ``Real'' objects in a similar way to PostScript, but suggests a range of $\pm3.403\times10^{38}$ and smallest non-zero values of $\pm1.175\times10^{38}$\cite{pdfref17}. A note in the PDF 1.7 manual mentions that Acrobat 6 now uses IEEE-754 single precision floats, but ``previous versions used 32-bit fixed point numbers'' and ``... Acrobat 6 still converts floating-point numbers to fixed point for some components''.
-\begin{comment}
+%\begin{comment}
 \subsection{{\TeX} and METAFONT}
 
 In ``The METAFONT book'' Knuth appears to describe coordinates as fixed point numbers: ``The computer works internally with coordinates that are integer multiples of $\frac{1}{65536} \approx 0.00002$ of the width of a pixel''\cite{knuth1983metafont}. \footnote{This corresponds to using $16$ bits for the fractional component of a fixed point representation} There is no mention of precision in ``The {\TeX} book''. In 2007 Beebe claimed that {\TeX} uses a $14.16$ fixed point encoding, and that this was due to the lack of standardised floating point arithmetic on computers at the time; a problem that the IEEE-754 was designed to solve\cite{beebe2007extending}. Beebe also suggested that {\TeX} and METAFONT could now be modified to use IEEE-754 arithmetic.
-\end{comment}
+%\end{comment}
 
 \subsection{SVG}
 
 The SVG standard specifies a minimum precision equivelant to that of ``single precision floats'' (presumably referring to IEEE-754) with a range of \verb/-3.4e+38F/ to \verb/+3.4e+38F/, and states ``It is recommended that higher precision floating point storage and computation be performed on operations such as
 coordinate system transformations to provide the best possible precision and to prevent round-off errors.''\cite{svg2011-1.1} An SVG Viewer may refer to itself as ``High Quality'' if it uses a minimum of ``double precision'' floats.
-\begin{comment}
+%\begin{comment}
 \subsection{Javascript}
-%We include Javascript here due to its relation with the SVG, HTML5 and PDF standards.
+We include Javascript here due to its relation with the SVG, HTML5 and PDF standards.
 According to the EMCA-262 standard, ``The Number type has exactly 18437736874454810627 (that is, $2^64-^53+3$) values, 
 representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic''\cite{ecma-262}. 
 The Number type does differ slightly from IEEE-754 in that there is only a single valid representation of ``Not a Number'' (NaN). The EMCA-262 does not define an ``integer'' representation.
-\end{comment}
+%\end{comment}
index 73e631d..3e64319 100644 (file)
@@ -6,6 +6,11 @@
 \begin{itemize}
        \item Collaborated with David Gow on the design and implementation of the SVG viewer
        \item Individual work: Applying GMP Rationals (Sam), Quadtree (David)
+       \begin{itemize}
+               \item CPU renderer, SVG parsing, Control Panel, Python Scripts - Sam
+               \item Most of the OpenGL stuff, Scaling/Translating controls - David
+               \item Other parts were worked on by everyone
+       \end{itemize}
        \item Used git to collaborate \url{https://git.ucc.asn.au}
        \item Used preprocessor defines to not interfere with each other's code too much
        \item David used a \verb/goto/ letting the team down
@@ -14,6 +19,9 @@
 \section{Structure of Software}
 \begin{itemize}
        \item CPU and GPU renderer supported
+       \begin{itemize}
+               \item See figure in ``Floating Point Operations on the CPU and GPU''
+       \end{itemize}
        \item Rendering of Cubic B\'{e}ziers (no antialiasing)
        \item Partial implementation of shading Paths on CPU (abandoned)
        \item Ability to move the view around the document with the mouse
 \begin{itemize}
        \item This is mostly covered in the Results chapter
        \item Control the program through stdin using a python script   
+       \item Results plotted with matplotlib
 \end{itemize}
 
diff --git a/figures/fglrx.png b/figures/fglrx.png
new file mode 100644 (file)
index 0000000..1298471
Binary files /dev/null and b/figures/fglrx.png differ
diff --git a/figures/gpufloats.pdf b/figures/gpufloats.pdf
new file mode 100644 (file)
index 0000000..70b0eff
Binary files /dev/null and b/figures/gpufloats.pdf differ
diff --git a/figures/intel.png b/figures/intel.png
new file mode 100644 (file)
index 0000000..aa70955
Binary files /dev/null and b/figures/intel.png differ
diff --git a/figures/nvidia.png b/figures/nvidia.png
new file mode 100644 (file)
index 0000000..85a2d0a
Binary files /dev/null and b/figures/nvidia.png differ
diff --git a/figures/x86-64.png b/figures/x86-64.png
new file mode 100644 (file)
index 0000000..03d9a94
Binary files /dev/null and b/figures/x86-64.png differ
index 19a5b53..a99c352 100644 (file)
Binary files a/thesis.pdf and b/thesis.pdf differ

UCC git Repository :: git.ucc.asn.au