chapters/Progress.tex

   1 \chapter{Progress Report}\label{Progress Report}
   2
   3 This chapter outlines 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:
   8 \begin{enumerate}
   9         \item Rendering Vector Graphics
  10         \item Representations of Vector Documents
  11         \item Floating Point number representations
  12 \end{enumerate}
  13
  14 In summary, we have found:
  15 \begin{itemize}
  16         \item Rasterisation of Vector Graphics is non-trivial but well understood
  17         \item Traditionally rasterisation has been performed on the CPU and rendering on a dedicated GPU; current interest is in techniques for utilising the GPU directly to rasterise vector graphics.
  18         \item The popular standards for document formats including PostScript, PDF, HTML, SVG require IEEE-754 binary32 precision
  19         \item Fixed precision floating point numbers make a trade off between precision and range
  20         \item IEEE-754 is widely used although there are instances of languages or processors which do not conform exactly to the standard
  21         \item GPUs in particular may not conform to IEEE-754, trading some accuracy of operations for performance
  22 \end{itemize}
  23
  24 \section{Development of Testbed Software}
  25
  26 We have produced a basic Document Viewer capable of rendering simple primitives under translation and scaling. OpenGL 3.1 is used to interface with graphics hardware. This software has the following features:
  27 \begin{enumerate}
  28         \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.
  29         \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
  30         \item Test documents can be loaded and saved so that we can compare different versions of the program on identical inputs
  31         \item Transformations can be performed on either the GPU or CPU
  32         \item Performance of rendering can be measured
  33 \end{enumerate}
  34
  35 We have found the performance of coordinate transforms on the GPU to be far superior to the CPU. However, at large enough scales it becomes apparent that the GPU is performing operations at a lower precision than the CPU. See Figure \ref{}.
  36
  37
  38
  39 \section{Floating Point Precision}
  40
  41 Algorithms for floating point arithmetic may be implemented in software (CPU) or on dedicated hardware (FPU). We have made progress towards both approaches.
  42
  43 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.
  44
  45 Mainly motivated by producing Figure \ref{minifloat.pdf} we have also implemented functions to convert arbitrary real numbers (which may themselves 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.
  46
  47 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.
  48
  49 \subsection{Prototype Document Formats}
  50
  51 Our testbed software is capable of reading primitive attributes from either a binary file or XML plain text file. Our format is closest 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.
  52
  53 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.
  54
  55
  56 \section{Version Control and Backup of Work}
  57
  58 Git is a distributed version control system widely used in the development of open source software\cite{}. 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} and \url{david's website probably I guess}\footnote{These are all actually on the same filesystem but it sounds impressive anyway}
  59
  60 \section{Timeline}
  61
  62 Deadlines enforced by the faculty of Engineering Computing and Mathematics are \emph{italicised}. Tasks completed as of the submission of this report are struck through. \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}.
  63
  64 \begin{center}
  65 \begin{tabular}{l|p{0.5\textwidth}}
  66         {\bf Date} & {\bf Milestone}\\
  67         \hline
  68         $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
  69         \hline
  70         ? May & Draft Progress Report and Literature Review \\
  71         \hline
  72         $26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\
  73         \hline
  74         $9^{\text{th}}$ June & Demonstrations of limitations of floating point precision in the Testbed software. \\
  75         $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. \\
  76         \hline
  77         $1^{\text{st}}$ August & Experiments and comparison of various infinite precision implementations completed. \\
  78         \hline
  79         $1^{\text{st}}$ September & Advanced features implemented and tested, work underway on Final Report. \\
  80         \hline
  81         TBA & \emph{Conference Abstract and Presentation due.} \\
  82         \hline
  83         $10^{\text{th}}$ October & \emph{Draft of Final Report due.} \\
  84         \hline
  85         $27^{\text{th}}$ October & \emph{Final Report due.}\\
  86         \hline
  87 \end{tabular}
  88 \end{center}
  89