From: Sam Moore Date: Fri, 10 Oct 2014 09:45:09 +0000 (+0800) Subject: A 1.5th order approximation to a 1st draft X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=commitdiff_plain;h=689e433b348588e05f47d23385dbf05d239c95d2 A 1.5th order approximation to a 1st draft This will probably have to be good enough, as I need to catch a bus. --- diff --git a/chapters/Background.tex b/chapters/Background.tex index 10852bb..6a7b3a5 100644 --- a/chapters/Background.tex +++ b/chapters/Background.tex @@ -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} diff --git a/chapters/Background/FixedPoint.tex b/chapters/Background/FixedPoint.tex index 707dab2..352e9d3 100644 --- a/chapters/Background/FixedPoint.tex +++ b/chapters/Background/FixedPoint.tex @@ -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 diff --git a/chapters/Background/FloatingPointOnTheGPU.tex b/chapters/Background/FloatingPointOnTheGPU.tex index bd5ea29..0d40fb1 100644 --- a/chapters/Background/FloatingPointOnTheGPU.tex +++ b/chapters/Background/FloatingPointOnTheGPU.tex @@ -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 diff --git a/chapters/Background/Floats.tex b/chapters/Background/Floats.tex index 7eba8a2..65a99e4 100644 --- a/chapters/Background/Floats.tex +++ b/chapters/Background/Floats.tex @@ -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} diff --git a/chapters/Background/Floats/Definition.tex b/chapters/Background/Floats/Definition.tex index 62d2c71..33f1a15 100644 --- a/chapters/Background/Floats/Definition.tex +++ b/chapters/Background/Floats/Definition.tex @@ -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. diff --git a/chapters/Background/Floats/Operations.tex b/chapters/Background/Floats/Operations.tex index 1a724f9..5624892 100644 --- a/chapters/Background/Floats/Operations.tex +++ b/chapters/Background/Floats/Operations.tex @@ -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}. diff --git a/chapters/Background/Standards/Precision.tex b/chapters/Background/Standards/Precision.tex index afb5f24..0a9511c 100644 --- a/chapters/Background/Standards/Precision.tex +++ b/chapters/Background/Standards/Precision.tex @@ -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} diff --git a/chapters/Process.tex b/chapters/Process.tex index 73e631d..3e64319 100644 --- a/chapters/Process.tex +++ b/chapters/Process.tex @@ -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 @@ -120,5 +128,6 @@ \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 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 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 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 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 index 0000000..03d9a94 Binary files /dev/null and b/figures/x86-64.png differ diff --git a/thesis.pdf b/thesis.pdf index 19a5b53..a99c352 100644 Binary files a/thesis.pdf and b/thesis.pdf differ