chapters/Progress.tex

   1 \chapter{Progress Report}\label{Progress}
   2
   3 We describe the current state of our project in relation to the aims outlined in Chapter \ref{Introduction}. At this stage work on the project has been done in collaboration with David Gow; however the Project Proposals and Literature Reviews were produced individually.
   4
   5 \section{Literature Review}
   6 The literature examined in Chapter\ref{Background} can broadly classed into three different areas (with major references indicated):
   7 \begin{enumerate}
   8         \item Rendering Vector Graphics \cite{computergraphics2, knuth1983metafont, kilgard2012gpu}
   9         \begin{itemize}
  10                 \item Rasterisation of Vector Graphics is non-trivial but well understood
  11                 \item Traditionally most rasterisation has been performed on the CPU and drawing on a dedicated GPU; current interest is in techniques for utilising the GPU directly to rasterise vector graphics
  12         \end{itemize}
  13         \item Representations of Vector Documents \cite{hayes2012pixels, plrm, knuth1984texbook, svg2011-1.1, pdfref17}
  14         \begin{itemize}
  15                 \item Traditional approaches are be based on a programmatic model (PostScript, {\TeX}, DVI)
  16                 \item The Document Object Model (DOM) used by web technologies is a powerful way to produce dynamic documents (HTML5, SVG, Javascript)
  17                 \item These approaches can overlap (PDF)
  18         \end{itemize}
  19         \item Number Representations \cite{ieee754std2008, HFP, goldberg1991whatevery, fousse2007mpfr}
  20         \begin{itemize}
  21                 \item Most document standards either specify, suggest, or imply a IEEE-754 floating point representation ({\TeX} is an exception)
  22                 \item IEEE-754 is widely used, although there are instances of languages or processors which do not conform exactly to the standard
  23                 \item Some GPUs in particular may not conform to IEEE-754, possibly trading some accuracy for performance
  24                 \item Arbitrary precision floating point arithmetic is possible through several libraries
  25         \end{itemize}
  26 \end{enumerate}
  27
  28 To improve the Literature Review we could consider the following topics in more detail:
  29 \begin{enumerate}
  30         \item Additional approaches to arbitrary precision possibly including symbolic computation
  31         \item Floating point errors in the context of computing B\'{e}zier Curves or similar
  32         \item Algorithms for reducing overall error other than Fast2Sum
  33         \item Alternative number representations such as rationals (eg: $\frac{1}{3}$)
  34         \item How well GPUs conform or do not conform to IEEE-754 in more detail
  35         \item Additional aspects of rendering vector documents including shading
  36 \end{enumerate}
  37
  38
  39 \section{Development of Testbed Software}
  40
  41 We have produced a basic Document Viewer capable of rendering simple primitives under translation and scaling. The OpenGL 3.1 API is used to interface with graphics hardware. This software has the following features:
  42 \begin{enumerate}
  43         \item A type name \verb/Real/ is used in place of the standard floating point types \verb/float/, \verb/double/ or \verb/long double/. This type name can be redefined to refer to one of the standard types or a custom real number representation, allowing us to easily recompile and test our software for different representations.
  44         \item Screenshots can be overlaid on top of each other to get a pixel comparison of the graphical output of different versions of the program
  45         \item Test documents can be loaded and saved so that we can compare different versions of the program on identical inputs
  46         \item The time for rendering can be measured
  47         \item Coordinate transformations may be performed on either the GPU or CPU
  48 \end{enumerate}
  49
  50 We have noticed the CPU produces more precise coordinate transformations at large ``zoom'' levels, but is significantly slower than the GPU. We have yet to quantitatively measure this difference.
  51
  52 \section{Floating Point Arithmetic}
  53
  54 Algorithms for floating point arithmetic may be implemented in software (CPU) or on dedicated hardware (FPU). We have made progress towards both approaches.
  55
  56 An open source Virtual FPU implemented in the VHDL language has been successfully compiled and can be substituted into our testbed software in place of native arithmetic running on the CPU. The timing diagram for this FPU throughout the execution of test programs can be extracted. Currently the virtual FPU is restricted to 32 bit floats and the square root operation is unimplemented.
  57
  58 Mainly motivated by producing Figure \ref{minifloat.pdf} we have also implemented functions to convert an arbitrary \verb/Real/ type (which may be IEEE-754 floats) to and from a fixed size floating point representation of our choosing. We have not implemented any operations for floating point arithmetic using these representations.
  59
  60 By using the functions to convert real numbers to variable precision floats as an interface for the virtual FPU, we hope to illustrate the limitations of floating point arithmetic more clearly than would be possible using IEEE-754 binary32 as is native to the C and C++ languages.
  61
  62 \section{Prototype Document Formats}
  63
  64 Our testbed software is capable of reading primitive attributes from either a binary file or XML plain text file. Our format is conceptually similar to the Document Object Model, although there is currently only one generation in the tree as no primitives can contain other elements as of yet.
  65
  66 If time permits, we plan to extend our XML format to cover a subset of the SVG standard. This may allow us to compare the rasterisation of an SVG using our own software and traditional software relying on IEEE-754 floats.
  67
  68 Some of the figures produced for Chapter \ref{Background} may prove useful as standard test images for comparing the qualitative performance of versions of our software.
  69
  70 \section{Version Control and Backup of Work}
  71
  72 Git is a distributed version control system widely used in the development of open source software. All rescources created for or used by this project have been placed in git repositories on several servers. The repositories are publically accessable at \url{http://git.ucc.asn.au}, \url{http://szmoore.net/ipdf}.
  73
  74 \section{Timeline}
  75
  76 Deadlines enforced by the faculty of Engineering Computing and Mathematics are \emph{italicised}.\footnote{David Gow is being assessed under the 2014 rules for a BEng (Software) Final Year Project, whilst the author is being assessed under the 2014 rules for a BEng (Mechatronics) Final Year Project; deadlines and requirements as shown in Gow's proposal\cite{proposalGow} may differ}.
  77
  78 \begin{center}
  79 \begin{tabular}{l|p{0.5\textwidth}}
  80         {\bf Date} & {\bf Milestone} \\
  81         \hline
  82         $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
  83         \hline
  84         $17^{\text{th}}$ May & Draft Progress Report and Literature Review \\
  85         \hline
  86         $26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\
  87         \hline
  88         $9^{\text{th}}$ June & Demonstrations of limitations of floating point precision in the Testbed software. \\
  89         $1^{\text{st}}$ July & At least one implementation of arbitrary precision for basic primitives (lines, polygons, curves) completed. Other implementations, advanced features, and areas for more detailed research identified. \\
  90         \hline
  91         $1^{\text{st}}$ August & Experiments and comparison of various arbitrary precision implementations completed. \\
  92         \hline
  93         $1^{\text{st}}$ September & Advanced features implemented and tested, work underway on Final Report. \\
  94         \hline
  95         TBA & \emph{Conference Abstract and Presentation due.} \\
  96         \hline
  97         $10^{\text{th}}$ October & \emph{Draft of Final Report due.} \\
  98         \hline
  99         $27^{\text{th}}$ October & \emph{Final Report due.}\\
 100         \hline
 101 \end{tabular}
 102 \end{center}
 103