XGitUrl: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LiteratureNotes.tex;h=0e423ca18a466348619618ca1e756123724fb3d3;hp=0d3abd5c1cc062b1fcf77ebd7ce421817848678c;hb=6f5f55579b969668419ea925e07f6c86442ef582;hpb=7e67ff636259c96c79b06d4ff1a690fbdefa05ea
diff git a/LiteratureNotes.tex b/LiteratureNotes.tex
index 0d3abd5..0e423ca 100644
 a/LiteratureNotes.tex
+++ b/LiteratureNotes.tex
@@ 1,11 +1,12 @@
\documentclass[8pt]{extarticle}
+\documentclass[8pt]{extreport}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{amsmath} % needed for math align
\usepackage{bm} % needed for maths bold face
\usepackage{graphicx} % needed for including graphics e.g. EPS, PS
\usepackage{fancyhdr} % needed for header

+%\usepackage{epstopdf} % Converts eps to pdf before including. Do it manually instead.
+\usepackage{float}
\usepackage{hyperref}
\topmargin 1.5cm % read Lamport p.163
@@ 45,9 +46,8 @@
\lstset{showstringspaces=false}
\lstset{basicstyle=\small}



+\newcommand{\shell}[1]{\texttt{#1}}
+\newcommand{\code}[1]{\texttt{#1}}
\begin{document}
@@ 69,21 +69,31 @@
\tableofcontents
\section{Postscript Language Reference Manual\cite{plrm}}
+\chapter{Literature Summaries}
+
+\section{Postscript Language Reference Manual \cite{plrm}}
Adobe's official reference manual for PostScript.
It is big.
\section{Portable Document Format Reference Manual\cite{pdfref17}}
+\section{Portable Document Format Reference Manual \cite{pdfref17}}
Adobe's official reference for PDF.
It is also big.
+\section{IEEE Standard for FloatingPoint Arithmetic \cite{ieee2008754}}
+
+The IEEE (revised) 754 standard.
+
+It is also big.
+
+
+
\pagebreak
\section{Portable Document Format (PDF)  Finally...\cite{cheng2002portable}}
+\section{Portable Document Format (PDF)  Finally... \cite{cheng2002portable}}
This is not spectacularly useful, is basically an advertisement for Adobe software.
@@ 116,7 +126,7 @@ This is not spectacularly useful, is basically an advertisement for Adobe softwa
\end{itemize}
\pagebreak
\section{Pixels or Perish \cite{hayes2012pixels}}
+\section{Pixels or Perish \cite{hayes2012pixels}}
``The art of scientific illustration will have to adapt to the new age of online publishing''
And therefore, JavaScript libraries ($\text{D}^3$) are the future.
@@ 181,14 +191,14 @@ This paper uses Metaphors a lot. I never met a phor that didn't over extend itse
\end{itemize}
\section{Embedding and Publishing Interactive, 3D Figures in PDF Files\cite{barnes2013embedding}}
+\section{Embedding and Publishing Interactive, 3D Figures in PDF Files \cite{barnes2013embedding}}
\begin{itemize}
\item Linkes well with \cite{hayes2012pixels}; I heard you liked figures so I put a figure in your PDF
\item Title pretty much summarises it; similar to \cite{hayes2012pixels} except these guys actually did something practical
\end{itemize}
\section{27 Bits are not enough for 8 digit accuracy\cite{goldberg1967twentyseven}}
+\section{27 Bits are not enough for 8 digit accuracy \cite{goldberg1967twentyseven}}
Proves with maths, that rounding errors mean that you need at least $q$ bits for $p$ decimal digits. $10^p < 2^{q1}$
@@ 211,7 +221,7 @@ Proves with maths, that rounding errors mean that you need at least $q$ bits for
\end{itemize}
\end{itemize}
\section{What every computer scientist should know about floatingpoint arithmetic\cite{goldberg1991whatevery}}
+\section{What every computer scientist should know about floatingpoint arithmetic \cite{goldberg1991whatevery}}
\begin{itemize}
\item Book: \emph{Floating Point Computation} by Pat Sterbenz (out of print... in 1991)
@@ 261,7 +271,7 @@ Proves with maths, that rounding errors mean that you need at least $q$ bits for
%%%%
% David's Stuff
%%%%
\section{Compositing Digital Images\cite{porter1984compositing}}
+\section{Compositing Digital Images \cite{porter1984compositing}}
@@ 301,7 +311,7 @@ and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL
all but guaranteed that this is the method we will be using for compositing
document elements in our project.
\section{Bresenham's Algorithm: Algorithm for computer control of a digital plotter\cite{bresenham1965algorithm}}
+\section{Bresenham's Algorithm: Algorithm for computer control of a digital plotter \cite{bresenham1965algorithm}}
Bresenham's line drawing algorithm is a fast, high quality line rasterization
algorithm which is still the basis for most (aliased) line drawing today. The
paper, while originally written to describe how to control a particular plotter,
@@ 324,13 +334,13 @@ subpixel coverage into account. Bresenham himself extended this algorithm to
produce Bresenham's circle algorithm. The principles behind the algorithm have
also been used to rasterize other shapes, including B\'{e}zier curves.
\section{Quad Trees: A Data Structure for Retrieval on Composite Keys\cite{finkel1974quad}}
+\section{Quad Trees: A Data Structure for Retrieval on Composite Keys \cite{finkel1974quad}}
This paper introduces the ``quadtree'' spatial data structure. The quadtree structure is
a search tree in which every node has four children representing the northeast, northwest,
southeast and southwest quadrants of its space.
\section{Xr: Crossdevice Rendering for Vector Graphics\cite{worth2003xr}}
+\section{Xr: Crossdevice Rendering for Vector Graphics \cite{worth2003xr}}
Xr (now known as Cairo) is an implementation of the PDF v1.4 rendering model,
independent of the PDF or PostScript file formats, and is now widely used
@@ 356,7 +366,7 @@ providing a tradeoff between rendering quality and performance. The library dev
that setting the tolerance to greater than $0.1$ device pixels resulted in errors visible to the
user.
\section{Glitz: Hardware Accelerated Image Compositing using OpenGL\cite{nilsson2004glitz}}
+\section{Glitz: Hardware Accelerated Image Compositing using OpenGL \cite{nilsson2004glitz}}
This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
the \texttt{Cairo} library.
@@ 381,7 +391,7 @@ some transformations were applied.
%% Sam again
\section{Boost Multiprecision Library\cite{boost_multiprecision}}
+\section{Boost Multiprecision Library \cite{boost_multiprecision}}
\begin{itemize}
\item ``The Multiprecision Library provides integer, rational and floatingpoint types in C++ that have more range and precision than C++'s ordinary builtin types.''
@@ 392,7 +402,7 @@ some transformations were applied.
% Some hardware related sounding stuff...
\section{A CMOS Floating Point Unit\cite{kelley1997acmos}}
+\section{A CMOS Floating Point Unit \cite{kelley1997acmos}}
The paper describes the implentation of a FPU for PowerPC using a particular Hewlett Packard process (HP14B 0.5$\mu$m, 3M, 3.3V).
It implements a ``subset of the most commonly used double precision floating point instructions''. The unimplemented operations are compiled for the CPU.
@@ 420,7 +430,7 @@ It is probably not that useful, I don't think we'll end up writing FPU assembly?
FPU's typically have 80 bit registers so they can support REAL4, REAL8 and REAL10 (single, double, extended precision).
\section{Floating Point Package User's Guide\cite{bishop2008floating}}
+\section{Floating Point Package User's Guide \cite{bishop2008floating}}
This is a technical report describing floating point VHDL packages \url{http://www.vhdl.org/fphdl/vhdl.html}
@@ 433,13 +443,13 @@ See also: Java Optimized Processor\cite{jop} (it has a VHDL implementation of a
\section{LowCost Microarchitectural Support for Improved FloatingPoint Accuracy\cite{dieter2007lowcost}}
Mentions how GPUs offer very good floating point performance but only for single precision floats.
+Mentions how GPUs offer very good floating point performance but only for single precision floats. (NOTE: This statement seems to contradict \cite{hillesland2004paranoia}.
Has a diagram of a Floating Point adder.
Talks about some magical technique called "Nativepair Arithmetic" that somehow makes 32bit floating point accuracy ``competitive'' with 64bit floating point numbers.
\section{Accurate Floating Point Arithmetic through Hardware ErrorFree Transformations\cite{kadric2013accurate}}
+\section{Accurate Floating Point Arithmetic through Hardware ErrorFree Transformations \cite{kadric2013accurate}}
From the abstract: ``This paper presents a hardware approach to performing ac
curate floating point addition and multiplication using the idea of error
@@ 456,17 +466,165 @@ I guess it's time to try and work out how to use the Opensource VHDL implementat
This is about reduction of error in hardware operations rather than the precision or range of floats.
But it is probably still relevant.
\section{Floating Point Unit from JOP\cite{jop}}
+This has the Fast2Sum algorithm but for the love of god I cannot see how you can compute anything other than $a + b = 0 \forall a,b$ using the algorithm as written in their paper. It references Dekker\cite{dekker1971afloating} and Kahn; will look at them instead.
+
+\section{Floating Point Unit from JOP \cite{jop}}
This is a 32 bit floating point unit developed for JOP in VHDL.
I have been able to successfully compile it and the test program using GHDL\cite{ghdl}.
+Whilst there are constants (eg: \verb/FP_WIDTH = 32, EXP_WIDTH = 8, FRAC_WIDTH = 23/) defined, the actual implementation mostly uses magic numbers, so
+some investigation is needed into what, for example, the "52" bits used in the sqrt units are for.
+
+\section{GHDL \cite{ghdl}}
+
+GHDL is an open source GPL licensed VHDL compiler written in Ada. It had packages in debian up until wheezy when it was removed. However the sourceforge site still provides a \shell{deb} file for wheezy.
+
+This reference explains how to use the \shell{ghdl} compiler, but not the VHDL language itself.
+
+GHDL is capable of compiling a ``testbench''  essentially an executable which simulates the design and ensures it meets test conditions.
+A common technique is using a text file to provide the inputs/outputs of the test. The testbench executable can be supplied an argument to save a \shell{vcd} file which can be viewed in \shell{gtkwave} to see timing diagrams.
+
+Sam has successfully compiled the VHDL design for an FPU in JOP\cite{jop} into a ``testbench'' executable which uses standard i/o instead of a regular file.
+Using unix domain sockets we can execute the FPU as a child process and communicate with it from our document viewing test software. This means we can potentially simulate alternate hardware designs for FPUs and witness the effect they will have on precision in the document viewer.
+
+Using \shell{ghdl} the testbench can also be linked as part a C/C++ program and run using a function; however there is still no way to communicate with it other than forking a child process and using a unix domain socket anyway. Also, compiling the VHDL FPU as part of our document viewer would clutter the code repository and probably be highly unportable. The VHDL FPU has been given a seperate repository.
+
+\section{On the design of fast IEEE floatingpoint adders \cite{seidel2001onthe}}
+
+This paper gives an overview of the ``Naive'' floating point addition/subtraction algorithm and gives several optimisation techniques:
+
+TODO: Actually understand these...
+
+\begin{itemize}
+ \item Use parallel paths (based on exponent)
+ \item Unification of significand result ranges
+ \item Reduction of IEEE rounding modes
+ \item Signmagnitude computation of a difference
+ \item Compound Addition
+ \item Approximate counting of leading zeroes
+ \item Precomputation of postnormalization shift
+\end{itemize}
+
+They then give an implementation that uses these optimisation techniques including very scary looking block diagrams.
+
+They simulated the FPU. Does not mention what simulation method was used directly, but cites another paper (TODO: Look at this. I bet it was VHDL).
+
+The paper concludes by summarising the optimisation techniques used by various adders in production (in 2001).
+
+This paper does not specifically mention the precision of the operations, but may be useful because a faster adder design might mean you can increase the precision.
+
+\section{Re: round32 ( round64 ( X ) ) ?= round32 ( X ) \cite{beebe2011round32}}
+
+I included this just for the quote by Nelson H. F. Beebe:
+
+``It is too late now to repair the mistakes of the past that are present
+in millions of installed systems, but it is good to know that careful
+research before designing hardware can be helpful.''
+
+This is in regards to the problem of double rounding. It provides a reference for a paper that discusses a rounding mode that eliminates the problem, and a software implementation.
+
+It shows that the IEEE standard can be fallible!
+
+Not sure how to work this into our literature review though.
+
% Back to software
\section{Basic Issues in Floating Point Arithmetic and Error Analysis\cite{demmel1996basic}}
+\section{Basic Issues in Floating Point Arithmetic and Error Analysis \cite{demmel1996basic}}
These are lecture notes from U.C Berkelye CS267 in 1996.
+\section{Charles Babbage \cite{dodge_babbage, nature1871babbage}}
+
+Tributes to Charles Babbage. Might be interesting for historical background. Don't mention anything about floating point numbers though.
+
+\section{GPU FloatingPoint Paranoia \cite{hillesland2004paranoia}}
+
+This paper discusses floating point representations on GPUs. They have reproduced the program \emph{Paranoia} by William Kahan for characterising floating point behaviour of computers (pre IEEE) for GPUs.
+
+
+There are a few remarks about GPU vendors not being very open about what they do or do not do with
+
+
+Unfortunately we only have the extended abstract, but a pretty good summary of the paper (written by the authors) is at: \url{www.cs.unc.edu/~ibr/projects/paranoia/}
+
+From the abstract:
+
+``... [GPUs are often similar to IEEE] However, we have found
+that GPUs do not adhere to IEEE standards for floatingpoint op
+erations, nor do they give the information necessary to establish
+bounds on error for these operations ... ''
+
+and ``...Our goal is to determine the error bounds on floatingpoint op
+eration results for quickly evolving graphics systems. We have cre
+ated a tool to measure the error for four basic floatingpoint opera
+tions: addition, subtraction, multiplication and division.''
+
+The implementation is only for windows and uses glut and glew and things.
+Implement our own version?
+
+\section{A floatingpoint technique for extending the available precision \cite{dekker1971afloating}}
+
+This is Dekker's formalisation of the Fast2Sum algorithm originally implemented by Kahn.
+
+\begin{align*}
+ z &= \text{RN}(x + y) \\
+ w &= \text{RN}(z  x) \\
+ zz &= \text{RN}(y  w) \\
+ \implies z + zz &= x + y
+\end{align*}
+
+There is a version for multiplication.
+
+I'm still not quite sure when this is useful. I haven't been able to find an example for $x$ and $y$ where $x + y \neq \text{Fast2Sum}(x, y)$.
+
+\section{Handbook of FloatingPoint Arithmetic \cite{HFP}}
+
+This book is amazingly useful and pretty much says everything there is to know about Floating Point numbers.
+It is much easier to read than Goldberg or Priest's papers.
+
+I'm going to start working through it and compile their test programs.
+
+\chapter{General Notes}
+
+\section{Rounding Errors}
+
+They happen. There is ULP and I don't mean a political party.
+
+TODO: Probably say something more insightful. Other than "here is a graph that shows errors and we blame rounding".
+
+\subsection{Results of calculatepi}
+
+We can calculate pi by numerically solving the integral:
+\begin{align*}
+ \int_0^1 \left(\frac{4}{1+x^2}\right) dx &= \pi
+\end{align*}
+
+Results with Simpson Method:
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=0.8\textwidth]{figures/calculatepi.pdf}
+ \caption{Example of accumulated rounding errors in a numerical calculation}
+\end{figure}
+
+Tests with \verb/calculatepi/ show it's not quite as simple as just blindly replacing all your additions with Fast2Sum from Dekker\cite{dekker1971afloating}.
+ie: The graph looks exactly the same for single precision. \verb/calculatepi/ obviously also has multiplication ops in it which I didn't change. Will look at after sleep maybe.
+
+\subsection{A sequence that seems to converge to a wrong limit  pgs 910, \cite{HFP}}
+
+\begin{align*}
+ u_n &= \left\{ \begin{array}{c} u_0 = 2 \\ u_1 = 4 \\ u_n = 111  \frac{1130}{u_{n1}} + \frac{3000}{u_{n1}u_{n2}}\end{array}\right.
+\end{align*}
+
+The limit of the series should be $6$ but when calculated with IEEE floats it is actually $100$
+The authors show that the limit is actually $100$ for different starting values, and the error in floating point arithmetic causes the series to go to that limit instead.
+
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=0.8\textwidth]{figures/handbook11.pdf}
+ \caption{Output of Program 1.1 from \emph{Handbook of FloatingPoint Arithmetic}\cite{HFP} for various IEEE types}
+\end{figure}
+
\pagebreak
\bibliographystyle{unsrt}
\bibliography{papers}