index fd86b5a..08b23e1 100644 (file)
@@ -188,7 +188,270 @@ This paper uses Metaphors a lot. I never met a phor that didn't over extend itse
\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}}

+Proves with maths, that rounding errors mean that you need at least $q$ bits for $p$ decimal digits. $10^p < 2^{q-1}$
+
+\begin{itemize}
+       \item Eg: For 8 decimal digits, since $10^8 < 2^{27}$ would expect to be able to represent with 27 binary digits
+       \item But: Integer part requires digits bits (regardless of fixed or floating point represenetation)
+       \item Trade-off between precision and range
+       \begin{itemize}
+               \item 9000000.0 $\to$ 9999999.9 needs 24 digits for the integer part $2^{23} = 83886008$
+       \end{itemize}
+       \item Floating point zero = smallest possible machine exponent
+       \item Floating point representation:
+       \begin{align*}
+               y &= 0.y_1 y_2 \text{...} y_q \times 2^{n}
+       \end{align*}
+       \item Can eliminate a bit by considering whether $n = -e$ for $-e$ the smallest machine exponent (???)
+       \begin{itemize}
+               \item Get very small numbers with the same precision
+               \item Get large numbers with the extra bit of precision
+       \end{itemize}
+\end{itemize}
+
+\section{What every computer scientist should know about floating-point arithmetic\cite{goldberg1991whatevery}}
+
+\begin{itemize}
+       \item Book: \emph{Floating Point Computation} by Pat Sterbenz (out of print... in 1991)
+    \item IEEE floating point standard becoming popular (introduced in 1987, this is 1991)
+    \begin{itemize}
+               \item As well as structure, defines the algorithms for addition, multiplication, division and square root
+               \item Makes things portable because results of operations are the same on all machines (following the standard)
+               \item Alternatives to floating point: Floating slasi and Signed Logarithm (TODO: Look at these, although they will probably not be useful)
+
+       \end{itemize}
+       \item Base $\beta$ and precision $p$ (number of digits to represent with) - powers of the base can be represented exactly.
+       \item Largest and smallest exponents $e_{min}$ and $e_{max}$
+       \item Need bits for exponent and fraction, plus one for sign
+       \item Floating point number'' is one that can be represented exactly.
+       \item Representations are not unique! $0.01 \times 10^1 = 1.00 \times 10^{-1}$ Leading digit of one $\implies$ normalised''
+       \item Requiring the representation to be normalised makes it unique, {\bf but means it is impossible to represent zero}.
+       \begin{itemize}
+               \item Represent zero as $1 \times \beta^{e_{min}-1}$ - requires extra bit in the exponent
+       \end{itemize}
+       \item {\bf Rounding Error}
+       \begin{itemize}
+               \item Units in the last place'' eg: 0.0314159 compared to 0.0314 has ulp error of 0.159
+               \item If calculation is the nearest floating point number to the result, it will still be as much as 1/2 ulp in error
+               \item Relative error corresponding to 1/2 ulp can vary by a factor of $\beta$ wobble''. Written in terms of $\epsilon$
+               \item Maths $\implies$ {\bf Relative error is always bounded by $\epsilon = (\beta/2)\beta^{-p}$}
+               \item Fixed relative error $\implies$ ulp can vary by a factor of $\beta$ . Vice versa
+               \item Larger $\beta \implies$ larger errors
+       \end{itemize}
+       \item {\bf Guard Digits}
+       \begin{itemize}
+               \item In subtraction: Could compute exact difference and then round; this is expensive
+               \item Keep fixed number of digits but shift operand right; discard precision. Lead to relative error up to $\beta - 1$
+               \item Guard digit: Add extra digits before truncating. Leads to relative error of less than $2\epsilon$. This also applies to addition
+       \end{itemize}
+       \item {\bf Catastrophic Cancellation} - Operands are subject to rounding errors - multiplication
+       \item {\bf Benign Cancellation} - Subtractions. Error $< 2\epsilon$
+       \item Rearrange formula to avoid catastrophic cancellation
+       \item Historical interest only - speculation on why IBM used $\beta = 16$ for the system/370 - increased range? Avoids shifting
+       \item Precision: IEEE defines extended precision (a lower bound only)
+       \item Discussion of the IEEE standard for operations (TODO: Go over in more detail)
+       \item NaN allow continuing with underflow and Infinity with overflow
+       \item Incidentally, some people think that the solution to such anomalies is never to compare floating-point numbers for equality but instead to consider them equal if they are within some error bound E. This is hardly a cure all, because it raises as many questions as it answers.'' - On equality of floating point numbers
+
+\end{itemize}
+
+
+%%%%
+% David's Stuff
+%%%%
+\section{Compositing Digital Images\cite{porter1984compositing}}
+
+
+
+Perter and Duff's classic paper "Compositing Digital Images" lays the
+foundation for digital compositing today. By providing an "alpha channel,"
+images of arbitrary shapes — and images with soft edges or sub-pixel coverage
+information — can be overlayed digitally, allowing separate objects to be
+rasterized separately without a loss in quality.
+
+Pixels in digital images are usually represented as 3-tuples containing
+(red component, green component, blue component). Nominally these values are in
+the [0-1] range. In the Porter-Duff paper, pixels are stored as $(R,G,B,\alpha)$
+4-tuples, where alpha is the fractional coverage of each pixel. If the image
+only covers half of a given pixel, for example, its alpha value would be 0.5.
+
+To improve compositing performance, albeit at a possible loss of precision in
+some implementations, the red, green and blue channels are premultiplied by the
+alpha channel. This also simplifies the resulting arithmetic by having the
+colour channels and alpha channels use the same compositing equations.
+
+Several binary compositing operations are defined:
+\begin{itemize}
+\item over
+\item in
+\item out
+\item atop
+\item xor
+\item plus
+\end{itemize}
+
+dissolves, as well as for changing the opacity of individual elements in a
+scene.
+
+The method outlined in this paper is still the standard system for compositing
+and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL}. It is
+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}}
+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,
+is uniquely suited to rasterizing lines for display on a pixel grid.
+
+Lines drawn with Bresenham's algorithm must begin and end at integer pixel
+coordinates, though one can round or truncate the fractional part. In order to
+avoid multiplication or division in the algorithm's inner loop,
+
+The algorithm works by scanning along the long axis of the line, moving along
+the short axis when the error along that axis exceeds 0.5px. Because error
+accumulates linearly, this can be achieved by simply adding the per-pixel
+error (equal to (short axis/long axis)) until it exceeds 0.5, then incrementing
+the position along the short axis and subtracting 1 from the error accumulator.
+
+As this requires nothing but addition, it is very fast, particularly on the
+older CPUs used in Bresenham's time. Modern graphics systems will often use Wu's
+line-drawing algorithm instead, as it produces antialiased lines, taking
+sub-pixel 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.
+
+
+This paper introduces the quadtree'' spatial data structure. The quadtree structure is
+a search tree in which every node has four children representing the north-east, north-west,
+south-east and south-west quadrants of its space.
+
+\section{Xr: Cross-device 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
+as a rendering API. In this paper, Worth and Packard describe the PDF v1.4 rendering
+model, and their PostScript-derived API for it.
+
+The PDF v1.4 rendering model is based on the original PostScript model, based around
+a set of \emph{paths} (and other objects, such as raster images) each made up of lines
+and B\'{e}zier curves, which are transformed by the Current Transformation Matrix.''
+Paths can be \emph{filled} in a number of ways, allowing for different handling of self-intersecting
+paths, or can have their outlines \emph{stroked}.
+Furthermore, paths can be painted with RGB colours and/or patterns derived from either
+previously rendered objects or external raster images.
+PDF v1.4 extends this to provide, amongst other features, support for layering paths and
+objects using Porter-Duff compositing\cite{porter1984compositing}, giving each painted path
+the option of having an $\alpha$ value and a choice of any of the Porter-Duff compositing
+methods.
+
+The Cairo library approximates the rendering of some objects (particularly curved objects
+such as splines) with a set of polygons. An \texttt{XrSetTolerance} function allows the user
+of the library to set an upper bound on the approximation error in fractions of device pixels,
+providing a trade-off between rendering quality and performance. The library developers found
+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}}
+
+This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
+the \texttt{Cairo} library.
+
+The paper describes how OpenGL's Porter-Duff compositing is easily suited to the Cairo/PDF v1.4
+rendering model. Similarly, traditional OpenGL (pre-version 3.0 core) support a matrix stack
+of the same form as Cairo.
+
+The Glitz'' backend will emulate support for tiled, non-power-of-two patterns/textures if
+the hardware does not support it.
+
+Glitz can render both triangles and trapezoids (which are formed from pairs of triangles).
+However, it cannot guarantee that the rasterization is pixel-precise, as OpenGL does not proveide
+this consistently.
+
+Glitz also supports multi-sample anti-aliasing, convolution filters for raster image reads (implemented
+
+Performance was much improved over the software rasterization and over XRender accellerated rendering
+on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when
+some transformations were applied.
+
+%% Sam again
+
+\section{Boost Multiprecision Library\cite{boost_multiprecision}}
+
+\begin{itemize}
+       \item The Multiprecision Library provides integer, rational and floating-point types in C++ that have more range and precision than C++'s ordinary built-in types.''
+       \item Specify number of digits for precision as a template argument.
+       \item Precision is fixed... {\bf possible approach to project:} Use \verb/boost::mpf_float<N>/ and increase \verb/N/ as more precision is required?
+\end{itemize}
+
+
+% Some hardware related sounding stuff...
+
+\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.
+
+The paper gives a description of the architecture and design methods.
+This appears to be an entry to a student design competition.
+
+Standard is IEEE 754, but the multiplier tree is a 64-bit tree instead of a 54 bit tree.
+ The primary reason for implementing a larger tree is for future additions of SIMD [Single Instruction Multiple Data (?)] instructions similar to Intel's MMX and Sun's VIS instructions''.
+
+HSPICE simulations used to determine transistor sizing.
+
+Paper has a block diagram that sort of vaguely makes sense to me.
+The rest requires more background knowledge.
+
+\section{Simply FPU\cite{filiatreault2003simply}}
+
+This is a webpage at one degree of seperation from wikipedia.
+
+It talks about FPU internals, but mostly focuses on the instruction sets.
+It includes FPU assembly code examples (!)
+
+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}}
+
+This is a technical report describing floating point VHDL packages \url{http://www.vhdl.org/fphdl/vhdl.html}
+
+In theory I know VHDL (cough) so I am interested in looking at this further to see how FPU hardware works.
+It might be getting a bit sidetracked from the document formats'' scope though.
+
+The report does talk briefly about the IEEE standard and normalised / denormalised numbers as well.
+
+See also: Java Optimized Processor\cite{jop} (it has a VHDL implementation of a FPU).
+
+\section{Low-Cost Microarchitectural Support for Improved Floating-Point Accuracy\cite{dieter2007lowcost}}
+
+Mentions how GPUs offer very good floating point performance but only for single precision floats.
+
+Has a diagram of a Floating Point adder.
+
+Talks about some magical technique called "Native-pair Arithmetic" that somehow makes 32-bit floating point accuracy competitive'' with 64-bit floating point numbers.
+
+\section{Accurate Floating Point Arithmetic through Hardware Error-Free 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-
+free transformations. Specialized iterative algorithms are implemented
+for computing arbitrarily accurate sums and dot products.''
+
+The references for this look useful.
+
+It also mentions VHDL.
+
+So whenever hardware papers come up, VHDL gets involved...
+I guess it's time to try and work out how to use the Opensource VHDL implementations. UCC git Repository :: git.ucc.asn.au