Name
Abstract | ||
|---|---|---|
We recently proposed the first hardware architecture enabling the iterative solution of systems of linear equations to accuracies limited only by the amount of available memory. 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.1× speedup in the solution of a set of representative linear systems through the avoidance of redundant digit calculation. For the computation of high-precision results, we also obtain an up-to 22.4 × memory requirement reduction over the same baseline. Finally, we demonstrate that solvers implemented following our proposals can show superiority over conventional arithmetic implementations by virtue of their runtime-tunable precisions. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ARITH.2018.8464691 | 2018 IEEE 25th Symposium on Computer Arithmetic (ARITH) |
Keywords | Field | DocType |
exact numeric computation,rounding error,superfluous digits,stationary iterative calculations,online arithmetic,redundant digit calculation,digit elision,arbitrary-accuracy iterative computation,hardware architecture,iterative solution,linear equations,linear systems,memory requirement reduction,ARCHITECT,arithmetic implementations,digit dependencies,forward error analysis | System of linear equations,Linear system,Iterative method,Round-off error,Computer science,Parallel computing,Algorithm,Geometric mean,Hardware architecture,Speedup,Computation | Conference |
ISSN | ISBN | Citations |
1063-6889 | 978-1-5386-2665-8 | 0 |
PageRank | References | Authors |
0.34 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| He Li | 1 | 5 | 5.21 |
| James J. Davis | 2 | 34 | 5.86 |
| John Wickerson | 3 | 142 | 10.08 |
| George A. Constantinides | 4 | 1391 | 160.26 |