Digit elision for arbitrary-accuracy iterative computation

File Description SizeFormat 
paper 28.pdfFile embargoed until 01 January 10000360.02 kBAdobe PDF    Request a copy
Title: Digit elision for arbitrary-accuracy iterative computation
Authors: Li, H
Davis, JJ
Wickerson, J
Constantinides, G
Item Type: Conference Paper
Abstract: Recently, a fixed compute-resource hardware architecture was proposed to enable the iterative solution of systems of linear equations to arbitrary accuracies. This technique, named ARCHITECT, achieves exact numeric computation by using online arithmetic to allow the refinement of results from earlier iterations over time, eschewing rounding error. ARCHITECT has a key drawback, however: often, many more digits than strictly necessary are generated, with this problem exacerbating the more accurate a solution is sought. In this paper, we infer the locations of these superfluous digits within stationary iterative calculations by exploiting online arithmetic’s digit dependencies and using forward error analysis. We demonstrate that their lack of computation is guaranteed not to affect the ability to reach a solution of any accuracy. Versus ARCHITECT, our illustrative hardware implementation achieves a geometric mean 20.1x speedup in the solution of a set of representative linear systems through the avoidance of redundant digit calculation. For the calculation of high-precision results, we also obtain an up-to 22.4x memory requirement reduction over the same architecture. Finally, we demonstrate that iterative solvers implemented following our proposals show superiority over conventional arithmetic implementations by virtue of their runtime-tunable precisions.
Issue Date: 25-Jun-2018
Date of Acceptance: 6-Apr-2018
URI: http://hdl.handle.net/10044/1/58750
Publisher: IEEE
Copyright Statement: This paper is embargoed until publication.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: 11908 (EP/K034448/1)
EP/P010040/1
Conference Name: IEEE Symposium on Computer Arithmetic (ARITH) 2018
Publication Status: Accepted
Start Date: 2018-06-25
Finish Date: 2018-06-27
Conference Place: Amherst, MA, USA
Embargo Date: publication subject to indefinite embargo
Appears in Collections:Faculty of Engineering
Electrical and Electronic Engineering



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx