chapters/Progress.tex

   1 \chapter{Progress Report}\label{Progress}
   2
   3 We describe the current state of our research in relation to the aims outlined in Chapter \ref{Introduction}.
   4
   5 \section{Literature Review}
   6
   7 We have examined a range of literature that can be broadly classed into three different areas (with major references indicated):
   8 \begin{enumerate}
   9         \item Rendering Vector Graphics \cite{computergraphics2, knuth1983metafont, kilgard2012gpu}
  10         \begin{itemize}
  11                 \item Rasterisation of Vector Graphics is non-trivial but well understood
  12                 \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
  13         \end{itemize}
  14         \item Representations of Vector Documents \cite{hayes2012pixels, plrm, knuth1984texbook, svg2011-1.1, pdfref17}
  15         \begin{itemize}
  16                 \item Traditional approaches are be based on a programmatic model (PostScript, {\TeX}, DVI)
  17                 \item The Document Object Model (DOM) used by web technologies is a powerful way to produce dynamic documents (HTML5, SVG, Javascript)
  18                 \item These approaches can overlap (PDF)
  19         \end{itemize}
  20         \item Number Representations \cite{ieee754std2008, HFP, goldberg1991whatevery, fousse2007mpfr}
  21         \begin{itemize}
  22                 \item Most document standards either specify, suggest, or imply a IEEE-754 floating point representation ({\TeX} is an exception)
  23                 \item IEEE-754 is widely used, although there are instances of languages or processors which do not conform exactly to the standard
  24                 \item Some GPUs in particular may not conform to IEEE-754, possibly trading some accuracy for performance
  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 or infinite precision, possibly including symbolic computation
  31         \item Floating point errors in the context of computing B\'{e}zier Curves or similar
  32         \item How well GPUs conform or do not conform to IEEE-754 in more detail
  33         \item Additional aspects of rendering vector documents including shading
  34 \end{enumerate}
  35
  36 \section{Development of Testbed Software}
  37
  38 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:
  39 \begin{enumerate}
  40         \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.
  41         \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
  42         \item Test documents can be loaded and saved so that we can compare different versions of the program on identical inputs
  43         \item The time for rendering can be measured
  44         \item Coordinate transformations may be performed on either the GPU or CPU
  45 \end{enumerate}
  46
  47 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.
  48
  49 \section{Floating Point Arithmetic}
  50
  51 Algorithms for floating point arithmetic may be implemented in software (CPU) or on dedicated hardware (FPU). We have made progress towards both approaches.
  52
  53 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.
  54
  55 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.
  56
  57 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.
  58
  59 \section{Prototype Document Formats}
  60
  61 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.
  62
  63 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.
  64
  65 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.
  66
  67 \section{Version Control and Backup of Work}
  68
  69 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}.
  70
  71 \section{Timeline}
  72
  73 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}.
  74
  75 \begin{center}
  76 \begin{tabular}{l|p{0.5\textwidth}}
  77         {\bf Date} & {\bf Milestone} \\
  78         \hline
  79         $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
  80         \hline
  81         $17^{\text{th}}$ May & Draft Progress Report and Literature Review \\
  82         \hline
  83         $26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\
  84         \hline
  85         $9^{\text{th}}$ June & Demonstrations of limitations of floating point precision in the Testbed software. \\
  86         $1^{\text{st}}$ July & At least one implementation of infinite precision for basic primitives (lines, polygons, curves) completed. Other implementations, advanced features, and areas for more detailed research identified. \\
  87         \hline
  88         $1^{\text{st}}$ August & Experiments and comparison of various infinite precision implementations completed. \\
  89         \hline
  90         $1^{\text{st}}$ September & Advanced features implemented and tested, work underway on Final Report. \\
  91         \hline
  92         TBA & \emph{Conference Abstract and Presentation due.} \\
  93         \hline
  94         $10^{\text{th}}$ October & \emph{Draft of Final Report due.} \\
  95         \hline
  96         $27^{\text{th}}$ October & \emph{Final Report due.}\\
  97         \hline
  98 \end{tabular}
  99 \end{center}
 100