This will probably have to be good enough, as I need to catch a bus.
14 files changed:
\section{Fixed Point and Integer Number Representations}
\input{chapters/Background/FixedPoint}
\section{Floating Point Number Representations}
\section{Fixed Point and Integer Number Representations}
\input{chapters/Background/FixedPoint}
\section{Floating Point Number Representations}
\section{Rational Number Representations}
\input{chapters/Background/Rationals}
\section{Rational Number Representations}
\input{chapters/Background/Rationals}
+\section{Floating Point Operations on the CPU and GPU}
+\input{chapters/Background/FloatingPointOnTheGPU}
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$.
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.
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.
1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
\end{align*}
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
-\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}.
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
%Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations
\input{chapters/Background/Floats/Visualisation}
\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}
\subsection{Arbitrary Precision Floating Point Numbers}
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.
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$.
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.
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.
-
-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}.
-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''.
\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''.
\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.
\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.
\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.
\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.
-%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.
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.
\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 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
\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
\section{Structure of Software}
\begin{itemize}
\item CPU and GPU renderer supported
\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
\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
\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