12
IRUS Total
Downloads

Digit stability inference for iterative methods using redundant number representation

File Description SizeFormat 
He Digit Stability Inference.pdfAccepted version419.93 kBAdobe PDFView/Open
Title: Digit stability inference for iterative methods using redundant number representation
Authors: Li, H
McInerney, I
Davis, J
Constantinides, G
Item Type: Journal Article
Abstract: In our recent work on iterative computation in hardware, we showed that arbitrary-precision solvers can perform more favorably than their traditional arithmetic equivalents when the latter's precisions are either under- or over-budgeted for the solution of the problem at hand. Significant proportions of these performance improvements stem from the ability to infer the existence of identical most-significant digits between iterations. This technique uses properties of algorithms operating on redundantly represented numbers to allow the generation of those digits to be skipped, increasing efficiency. It is unable, however, to guarantee that digits will stabilize, i.e., never change in any future iteration. In this article, we address this shortcoming, using interval and forward error analyses to prove that digits of high significance will become stable when computing the approximants of systems of linear equations using stationary iterative methods. We formalize the relationship between matrix conditioning and the rate of growth in most-significant digit stability, using this information to converge to our desired results more quickly. Versus our previous work, an exemplary hardware realization of this new technique achieves an up-to 2.2x speedup in the solution of a set of variously conditioned systems using the Jacobi method.
Issue Date: 1-Jul-2021
Date of Acceptance: 16-Jun-2020
URI: http://hdl.handle.net/10044/1/81050
DOI: 10.1109/TC.2020.3003529
ISSN: 0018-9340
Publisher: Institute of Electrical and Electronics Engineers
Start Page: 1074
End Page: 1080
Journal / Book Title: IEEE Transactions on Computers
Volume: 70
Issue: 7
Copyright Statement: © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. This document is the Accepted Manuscript version of a published work appearing in IEEE Transactions on Computers, https://doi.org/10.1109/TC.2020.3003529
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: EP/P010040/1
Keywords: math.NA
math.NA
cs.NA
Computer Hardware & Architecture
0803 Computer Software
0805 Distributed Computing
1006 Computer Hardware
Publication Status: Published
Open Access location: https://arxiv.org/abs/2006.09427
Online Publication Date: 2020-06-19
Appears in Collections:Electrical and Electronic Engineering
Faculty of Engineering