Another IEEE paper
[ipdf/documents.git] / LiteratureNotes.tex
1 \documentclass[8pt]{extarticle}
2 \usepackage{graphicx}
3 \usepackage{caption}
4 \usepackage{amsmath} % needed for math align
5 \usepackage{bm} % needed for maths bold face
6  \usepackage{graphicx}    % needed for including graphics e.g. EPS, PS
7 \usepackage{fancyhdr}   % needed for header
8
9 \usepackage{hyperref}
10
11  \topmargin -1.5cm        % read Lamport p.163
12  \oddsidemargin -0.04cm   % read Lamport p.163
13  \evensidemargin -0.04cm  % same as oddsidemargin but for left-hand pages
14  \textwidth 16.59cm
15  \textheight 21.94cm 
16  %\pagestyle{empty}       % Uncomment if don't want page numbers
17  \parskip 8.2pt           % sets spacing between paragraphs
18  %\renewcommand{\baselinestretch}{1.5}  % Uncomment for 1.5 spacing between lines
19  \parindent 0pt           % sets leading space for paragraphs
20 \linespread{0.8}
21
22
23 \newcommand{\vect}[1]{\boldsymbol{#1}} % Draw a vector
24 \newcommand{\divg}[1]{\nabla \cdot #1} % divergence
25 \newcommand{\curl}[1]{\nabla \times #1} % curl
26 \newcommand{\grad}[1]{\nabla #1} %gradient
27 \newcommand{\pd}[3][ ]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} %partial derivative
28 %\newcommand{\d}[3][ ]{\frac{d^{#1} #2}{d #3^{#1}}} %full derivative
29 \newcommand{\phasor}[1]{\tilde{#1}} % make a phasor
30 \newcommand{\laplacian}[1]{\nabla^2 {#1}} % The laplacian operator
31
32 \usepackage{color}
33 \usepackage{listings}
34
35 \definecolor{darkgray}{rgb}{0.95,0.95,0.95}
36 \definecolor{darkred}{rgb}{0.75,0,0}
37 \definecolor{darkblue}{rgb}{0,0,0.75}
38 \definecolor{pink}{rgb}{1,0.5,0.5}
39 \lstset{language=Java}
40 \lstset{backgroundcolor=\color{darkgray}}
41 \lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt}
42 \lstset{keywordstyle=\color{darkred}\bfseries}
43 \lstset{commentstyle=\color{darkblue}}
44 %\lstset{stringsyle=\color{red}}
45 \lstset{showstringspaces=false}
46 \lstset{basicstyle=\small}
47
48 \newcommand{\shell}[1]{\texttt{#1}}
49 \newcommand{\code}[1]{\texttt{#1}}
50
51 \begin{document}
52
53
54 \pagestyle{fancy}
55 \fancyhead{}
56 \fancyfoot{}
57
58 \fancyhead[LO, L]{}
59 \fancyfoot[CO, C]{\thepage}
60
61 \begin{center}
62         B.Eng. Final Year Project \par
63         {\bf \Large Literature Notes} \par
64         Sam Moore, David Gow \\
65         Faculty of Engineering, Computing and Mathematics, University of Western Australia \\
66         March 2014
67 \end{center}
68
69 \tableofcontents
70
71 \section{Postscript Language Reference Manual\cite{plrm}}
72
73 Adobe's official reference manual for PostScript.
74
75 It is big.
76
77 \section{Portable Document Format Reference Manual\cite{pdfref17}}
78
79 Adobe's official reference for PDF.
80
81 It is also big.
82
83 \pagebreak
84
85 \section{Portable Document Format (PDF) --- Finally...\cite{cheng2002portable}}
86
87 This is not spectacularly useful, is basically an advertisement for Adobe software.
88
89 {\bf Intro}
90 \begin{itemize}
91         \item Visual communications has been revolutionised by computing
92         \item BUT there have always been problems in exchanging formats
93         \item Filetypes like text, rich text, IGES, DXF, TIFF, JPEG, GIFF solve problems for particular types of files only
94         \item PDF solves everything for everyone; can include text, images, animation, sound, etc
95 \end{itemize}
96 {\bf PDF Features}
97 \begin{itemize}
98         \item Raster Image Process (RIP) --- For printing (presumably also displaying on screen)
99         \item Originally needed to convert to PS then RIP, with PS 3 can now RIP directly.
100         \item Reduced filesize due to compression
101         \item Four major applications - Stoy 1999\cite{stoy1999}
102                 \begin{enumerate}
103                         \item Download files from internet
104                         \item Files on CDs
105                         \item Files for outputing to printers
106                         \item Conventional [commercial scale?] printing
107                 \end{enumerate}
108         \item List of various (Adobe) PDF related software
109         \begin{itemize}
110                 \item Includes software for PS that converts to/from PDF 
111                 \item So PS was obviously pretty popular before PDF
112         \end{itemize}
113         \item Can Optimize for screen/printer [not clear how]
114         \item Can compress for size
115 \end{itemize}
116
117 \pagebreak
118 \section{Pixels or Perish \cite{hayes2012pixels}}
119
120 ``The art of scientific illustration will have to adapt to the new age of online publishing''
121 And therefore, JavaScript libraries ($\text{D}^3$) are the future.
122
123 The point is that we need to change from thinking about documents as paper to thinking of them as pixels.
124 This kind of makes it related to our paper, because it is the same way we are justifying our project. It does mention precision, but doesn't say we need to get more of it.
125
126 I get the feeling from this that Web based documents are a whole bunch of completely different design philosophies hacked together
127 with JavaScript.
128
129 This paper uses Metaphors a lot. I never met a phor that didn't over extend itself.
130
131
132 {\bf Intro}
133 \begin{itemize}
134         \item Drawings/Pictures are ornaments in science but they are not just ornamental
135         \item Processes have changed a lot; eg: photographic plates $\to$ digital images
136         \item ``we are about to turn the page --- if not close the book --- on yet another chapter in publishing history.'' (HO HO HO)
137         \item It would be cool to have animated figures in documents (eg: Population pyramid; changes with time); not just as ``supplements''
138         \item In the beginning, there was PostScript, 1970s and 1980s, John Warnock and Charles Geschke, Adobe Systems
139         \item PS is a language for vector graphics; objects are constructed from geometric primitives rather than a discrete array of pixels
140         \item PS is a complete programming language; an image is also a program; can exploit this to control how images are created based on data (eg: Faces)
141         \item PDF is ``flattened'' PS. No longer programable. Aspires to be ``virtual paper''.
142         \item But why are we using such powerful computing machines just to emulate sheets paper? (the author asks)
143 \end{itemize}
144
145 {\bf Web based Documents}
146 \begin{itemize}
147         \item HTML, CSS, JavaScript - The Axis of Web Documents
148         \begin{itemize}
149                 \item HTML - Defines document structure
150                 \item CSS - Defines presentation of elements in document
151                 \item JavaScript - Encodes actions, allows dynamic content (change the HTML/CSS)
152         \end{itemize}
153         \item \texttt{<canvas>} will let you draw anything (So in principle don't even need all of HTML/CSS)
154         \begin{itemize}
155                 \item Not device independent
156                 \item ``Coordinates can be specified with precision finer than pixel resolution'' {\bf (TODO: Investigate this?)}
157                 \item JavaScript operators to draw things on canvas are very similar to the PostScript model
158         \end{itemize}
159         \item SVG --- Same structure (Document Object Model (DOM)) as HTML
160         \begin{itemize}
161                 \item ``Noun language''
162                 \item Nouns define lines/curves etc, rather than paragraphs/lists
163                 \item Also borrows things from PostScript (eg: line caps and joints)
164                 \item IS device independent, ``very high precision'' {\bf (TODO: Investigate)}
165                 \item JavaScript can be used to interact with SVG too
166         \end{itemize}
167         \item $\text{D}^{3}$ (Data Driven Documents) - A JavaScript library
168         \begin{itemize}
169                 \item Idea is to create or modify elements of a DOM document using supplied data
170                 \item \url{https://github.com/mbostock/d3/wiki}
171         \end{itemize}
172         \item We are in a new Golden Age of data visualisation
173         \item Why do we still use PDFs?
174         \begin{itemize}
175                 \item PDFs are ``owned'' by the author/reader; you download it, store it, you can print it, etc
176                 \item HTML documents are normally on websites. They are not self contained. They often rely on remote content from other websites (annoying to download the whole document).
177         \end{itemize}
178         \item {\bf Conclusion} Someone should open up PDF to accept things like $\text{D}^{3}$ and other graphics formats (links nicely with \cite{barnes2013embedding})
179         \item Also, Harry Potter reference
180
181 \end{itemize}
182
183 \section{Embedding and Publishing Interactive, 3D Figures in PDF Files\cite{barnes2013embedding}}
184
185 \begin{itemize}
186         \item Linkes well with \cite{hayes2012pixels}; I heard you liked figures so I put a figure in your PDF
187         \item Title pretty much summarises it; similar to \cite{hayes2012pixels} except these guys actually did something practical
188 \end{itemize}
189
190 \section{27 Bits are not enough for 8 digit accuracy\cite{goldberg1967twentyseven}}
191
192 Proves with maths, that rounding errors mean that you need at least $q$ bits for $p$ decimal digits. $10^p < 2^{q-1}$
193
194 \begin{itemize}
195         \item Eg: For 8 decimal digits, since $10^8 < 2^{27}$ would expect to be able to represent with 27 binary digits
196         \item But: Integer part requires digits bits (regardless of fixed or floating point represenetation)
197         \item Trade-off between precision and range
198         \begin{itemize}
199                 \item 9000000.0 $\to$ 9999999.9 needs 24 digits for the integer part $2^{23} = 83886008$
200         \end{itemize}
201         \item Floating point zero = smallest possible machine exponent
202         \item Floating point representation:
203         \begin{align*}
204                 y &= 0.y_1 y_2 \text{...} y_q \times 2^{n}
205         \end{align*}
206         \item Can eliminate a bit by considering whether $n = -e$ for $-e$ the smallest machine exponent (???)
207         \begin{itemize}
208                 \item Get very small numbers with the same precision    
209                 \item Get large numbers with the extra bit of precision
210         \end{itemize}
211 \end{itemize}
212
213 \section{What every computer scientist should know about floating-point arithmetic\cite{goldberg1991whatevery}}
214
215 \begin{itemize}
216         \item Book: \emph{Floating Point Computation} by Pat Sterbenz (out of print... in 1991)
217     \item IEEE floating point standard becoming popular (introduced in 1987, this is 1991)
218     \begin{itemize}
219                 \item As well as structure, defines the algorithms for addition, multiplication, division and square root
220                 \item Makes things portable because results of operations are the same on all machines (following the standard)
221                 \item Alternatives to floating point: Floating slasi and Signed Logarithm (TODO: Look at these, although they will probably not be useful)
222
223         \end{itemize}
224         \item Base $\beta$ and precision $p$ (number of digits to represent with) - powers of the base can be represented exactly.
225         \item Largest and smallest exponents $e_{min}$ and $e_{max}$
226         \item Need bits for exponent and fraction, plus one for sign
227         \item ``Floating point number'' is one that can be represented exactly.
228         \item Representations are not unique! $0.01 \times 10^1 = 1.00 \times 10^{-1}$ Leading digit of one $\implies$ ``normalised''
229         \item Requiring the representation to be normalised makes it unique, {\bf but means it is impossible to represent zero}.
230         \begin{itemize}
231                 \item Represent zero as $1 \times \beta^{e_{min}-1}$ - requires extra bit in the exponent
232         \end{itemize}
233         \item {\bf Rounding Error}
234         \begin{itemize}
235                 \item ``Units in the last place'' eg: 0.0314159 compared to 0.0314 has ulp error of 0.159
236                 \item If calculation is the nearest floating point number to the result, it will still be as much as 1/2 ulp in error
237                 \item Relative error corresponding to 1/2 ulp can vary by a factor of $\beta$ ``wobble''. Written in terms of $\epsilon$
238                 \item Maths $\implies$ {\bf Relative error is always bounded by $\epsilon = (\beta/2)\beta^{-p}$}
239                 \item Fixed relative error $\implies$ ulp can vary by a factor of $\beta$ . Vice versa
240                 \item Larger $\beta \implies$ larger errors
241         \end{itemize}
242         \item {\bf Guard Digits}
243         \begin{itemize}
244                 \item In subtraction: Could compute exact difference and then round; this is expensive
245                 \item Keep fixed number of digits but shift operand right; discard precision. Lead to relative error up to $\beta - 1$
246                 \item Guard digit: Add extra digits before truncating. Leads to relative error of less than $2\epsilon$. This also applies to addition
247         \end{itemize}
248         \item {\bf Catastrophic Cancellation} - Operands are subject to rounding errors - multiplication
249         \item {\bf Benign Cancellation} - Subtractions. Error $< 2\epsilon$
250         \item Rearrange formula to avoid catastrophic cancellation
251         \item Historical interest only - speculation on why IBM used $\beta = 16$ for the system/370 - increased range? Avoids shifting
252         \item Precision: IEEE defines extended precision (a lower bound only)
253         \item Discussion of the IEEE standard for operations (TODO: Go over in more detail)
254         \item NaN allow continuing with underflow and Infinity with overflow
255         \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
256
257 \end{itemize}
258
259
260 %%%%
261 % David's Stuff
262 %%%%
263 \section{Compositing Digital Images\cite{porter1984compositing}}
264
265
266
267 Perter and Duff's classic paper "Compositing Digital Images" lays the
268 foundation for digital compositing today. By providing an "alpha channel,"
269 images of arbitrary shapes — and images with soft edges or sub-pixel coverage
270 information — can be overlayed digitally, allowing separate objects to be
271 rasterized separately without a loss in quality.
272
273 Pixels in digital images are usually represented as 3-tuples containing
274 (red component, green component, blue component). Nominally these values are in
275 the [0-1] range. In the Porter-Duff paper, pixels are stored as $(R,G,B,\alpha)$
276 4-tuples, where alpha is the fractional coverage of each pixel. If the image
277 only covers half of a given pixel, for example, its alpha value would be 0.5.
278
279 To improve compositing performance, albeit at a possible loss of precision in
280 some implementations, the red, green and blue channels are premultiplied by the
281 alpha channel. This also simplifies the resulting arithmetic by having the
282 colour channels and alpha channels use the same compositing equations.
283
284 Several binary compositing operations are defined:
285 \begin{itemize}
286 \item over
287 \item in
288 \item out
289 \item atop
290 \item xor
291 \item plus
292 \end{itemize}
293
294 The paper further provides some additional operations for implementing fades and
295 dissolves, as well as for changing the opacity of individual elements in a
296 scene.
297
298 The method outlined in this paper is still the standard system for compositing
299 and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL}. It is
300 all but guaranteed that this is the method we will be using for compositing
301 document elements in our project.
302
303 \section{Bresenham's Algorithm: Algorithm for computer control of a digital plotter\cite{bresenham1965algorithm}}
304 Bresenham's line drawing algorithm is a fast, high quality line rasterization
305 algorithm which is still the basis for most (aliased) line drawing today. The
306 paper, while originally written to describe how to control a particular plotter,
307 is uniquely suited to rasterizing lines for display on a pixel grid.
308
309 Lines drawn with Bresenham's algorithm must begin and end at integer pixel
310 coordinates, though one can round or truncate the fractional part. In order to
311 avoid multiplication or division in the algorithm's inner loop, 
312
313 The algorithm works by scanning along the long axis of the line, moving along
314 the short axis when the error along that axis exceeds 0.5px. Because error
315 accumulates linearly, this can be achieved by simply adding the per-pixel
316 error (equal to (short axis/long axis)) until it exceeds 0.5, then incrementing
317 the position along the short axis and subtracting 1 from the error accumulator.
318
319 As this requires nothing but addition, it is very fast, particularly on the
320 older CPUs used in Bresenham's time. Modern graphics systems will often use Wu's
321 line-drawing algorithm instead, as it produces antialiased lines, taking
322 sub-pixel coverage into account. Bresenham himself extended this algorithm to
323 produce Bresenham's circle algorithm. The principles behind the algorithm have
324 also been used to rasterize other shapes, including B\'{e}zier curves.
325
326 \section{Quad Trees: A Data Structure for Retrieval on Composite Keys\cite{finkel1974quad}}
327
328 This paper introduces the ``quadtree'' spatial data structure. The quadtree structure is
329 a search tree in which every node has four children representing the north-east, north-west,
330 south-east and south-west quadrants of its space.
331
332 \section{Xr: Cross-device Rendering for Vector Graphics\cite{worth2003xr}}
333
334 Xr (now known as Cairo) is an implementation of the PDF v1.4 rendering model,
335 independent of the PDF or PostScript file formats, and is now widely used
336 as a rendering API. In this paper, Worth and Packard describe the PDF v1.4 rendering
337 model, and their PostScript-derived API for it.
338
339 The PDF v1.4 rendering model is based on the original PostScript model, based around
340 a set of \emph{paths} (and other objects, such as raster images) each made up of lines
341 and B\'{e}zier curves, which are transformed by the ``Current Transformation Matrix.''
342 Paths can be \emph{filled} in a number of ways, allowing for different handling of self-intersecting
343 paths, or can have their outlines \emph{stroked}.
344 Furthermore, paths can be painted with RGB colours and/or patterns derived from either
345 previously rendered objects or external raster images.
346 PDF v1.4 extends this to provide, amongst other features, support for layering paths and
347 objects using Porter-Duff compositing\cite{porter1984compositing}, giving each painted path
348 the option of having an $\alpha$ value and a choice of any of the Porter-Duff compositing
349 methods.
350
351 The Cairo library approximates the rendering of some objects (particularly curved objects
352 such as splines) with a set of polygons. An \texttt{XrSetTolerance} function allows the user
353 of the library to set an upper bound on the approximation error in fractions of device pixels,
354 providing a trade-off between rendering quality and performance. The library developers found
355 that setting the tolerance to greater than $0.1$ device pixels resulted in errors visible to the
356 user.
357
358 \section{Glitz: Hardware Accelerated Image Compositing using OpenGL\cite{nilsson2004glitz}}
359
360 This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
361 the \texttt{Cairo} library. 
362
363 The paper describes how OpenGL's Porter-Duff compositing is easily suited to the Cairo/PDF v1.4
364 rendering model. Similarly, traditional OpenGL (pre-version 3.0 core) support a matrix stack
365 of the same form as Cairo.
366
367 The ``Glitz'' backend will emulate support for tiled, non-power-of-two patterns/textures if
368 the hardware does not support it.
369
370 Glitz can render both triangles and trapezoids (which are formed from pairs of triangles).
371 However, it cannot guarantee that the rasterization is pixel-precise, as OpenGL does not proveide
372 this consistently.
373
374 Glitz also supports multi-sample anti-aliasing, convolution filters for raster image reads (implemented
375 with shaders).
376
377 Performance was much improved over the software rasterization and over XRender accellerated rendering
378 on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when
379 some transformations were applied.
380
381 %% Sam again
382
383 \section{Boost Multiprecision Library\cite{boost_multiprecision}}
384
385 \begin{itemize}
386         \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.''
387         \item Specify number of digits for precision as a template argument.
388         \item Precision is fixed... {\bf possible approach to project:} Use \verb/boost::mpf_float<N>/ and increase \verb/N/ as more precision is required?
389 \end{itemize}
390
391
392 % Some hardware related sounding stuff...
393
394 \section{A CMOS Floating Point Unit\cite{kelley1997acmos}}
395
396 The paper describes the implentation of a FPU for PowerPC using a particular Hewlett Packard process (HP14B 0.5$\mu$m, 3M, 3.3V).
397 It implements a ``subset of the most commonly used double precision floating point instructions''. The unimplemented operations are compiled for the CPU.
398
399 The paper gives a description of the architecture and design methods.
400 This appears to be an entry to a student design competition.
401
402 Standard is IEEE 754, but the multiplier tree is a 64-bit tree instead of a 54 bit tree.
403 `` 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''.
404
405 HSPICE simulations used to determine transistor sizing.
406
407 Paper has a block diagram that sort of vaguely makes sense to me.
408 The rest requires more background knowledge.
409
410 \section{Simply FPU\cite{filiatreault2003simply}}
411
412 This is a webpage at one degree of seperation from wikipedia.
413
414 It talks about FPU internals, but mostly focuses on the instruction sets.
415 It includes FPU assembly code examples (!)
416
417 It is probably not that useful, I don't think we'll end up writing FPU assembly?
418
419 FPU's typically have 80 bit registers so they can support REAL4, REAL8 and REAL10 (single, double, extended precision).
420
421
422 \section{Floating Point Package User's Guide\cite{bishop2008floating}}
423
424 This is a technical report describing floating point VHDL packages \url{http://www.vhdl.org/fphdl/vhdl.html}
425
426 In theory I know VHDL (cough) so I am interested in looking at this further to see how FPU hardware works.
427 It might be getting a bit sidetracked from the ``document formats'' scope though.
428
429 The report does talk briefly about the IEEE standard and normalised / denormalised numbers as well.
430
431 See also: Java Optimized Processor\cite{jop} (it has a VHDL implementation of a FPU).
432
433 \section{Low-Cost Microarchitectural Support for Improved Floating-Point Accuracy\cite{dieter2007lowcost}}
434
435 Mentions how GPUs offer very good floating point performance but only for single precision floats.
436
437 Has a diagram of a Floating Point adder.
438
439 Talks about some magical technique called "Native-pair Arithmetic" that somehow makes 32-bit floating point accuracy ``competitive'' with 64-bit floating point numbers.
440
441 \section{Accurate Floating Point Arithmetic through Hardware Error-Free Transformations\cite{kadric2013accurate}}
442
443 From the abstract: ``This paper presents a hardware approach to performing ac-
444 curate floating point addition and multiplication using the idea of error-
445 free transformations. Specialized iterative algorithms are implemented
446 for computing arbitrarily accurate sums and dot products.''
447
448 The references for this look useful.
449
450 It also mentions VHDL.
451
452 So whenever hardware papers come up, VHDL gets involved...
453 I guess it's time to try and work out how to use the Opensource VHDL implementations.
454
455 This is about reduction of error in hardware operations rather than the precision or range of floats.
456 But it is probably still relevant.
457
458 \section{Floating Point Unit from JOP\cite{jop}}
459
460 This is a 32 bit floating point unit developed for JOP in VHDL.
461 I have been able to successfully compile it and the test program using GHDL\cite{ghdl}. 
462
463 Whilst there are constants (eg: \verb/FP_WIDTH = 32, EXP_WIDTH = 8, FRAC_WIDTH = 23/) defined, the actual implementation mostly uses magic numbers, so 
464 some investigation is needed into what, for example, the "52" bits used in the sqrt units are for.
465
466 \section{GHDL\cite{ghdl}}
467
468 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.
469
470 This reference explains how to use the \shell{ghdl} compiler, but not the VHDL language itself.
471
472 GHDL is capable of compiling a ``testbench'' - essentially an executable which simulates the design and ensures it meets test conditions.
473 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.
474
475 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.
476 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.
477
478 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.
479
480 \section{On the design of fast IEEE floating-point adders\cite{seidel2001onthe}}
481
482 This paper gives an overview of the ``Naive'' floating point addition/subtraction algorithm and gives several optimisation techniques:
483
484 TODO: Actually understand these...
485
486 \begin{itemize}
487         \item Use parallel paths (based on exponent)
488         \item Unification of significand result ranges
489         \item Reduction of IEEE rounding modes
490         \item Sign-magnitude computation of a difference
491         \item Compound Addition
492         \item Approximate counting of leading zeroes
493         \item Pre-computation of post-normalization shift
494 \end{itemize}
495
496 They then give an implementation that uses these optimisation techniques including very scary looking block diagrams.
497
498 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).
499
500 The paper concludes by summarising the optimisation techniques used by various adders in production (in 2001).
501
502 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.
503
504
505 % Back to software
506 \section{Basic Issues in Floating Point Arithmetic and Error Analysis\cite{demmel1996basic}}
507
508 These are lecture notes from U.C Berkelye CS267 in 1996.
509
510
511 \pagebreak
512 \bibliographystyle{unsrt}
513 \bibliography{papers}
514
515 \end{document}
516

UCC git Repository :: git.ucc.asn.au