ARCHITECT: Arbitrary-precision Hardware with Digit Elision for Efficient Iterative Compute

Publication available at:
Title: ARCHITECT: Arbitrary-precision Hardware with Digit Elision for Efficient Iterative Compute
Authors: Li, H
Davis, J
Wickerson, J
Constantinides, G
Item Type: Journal Article
Abstract: Many algorithms feature an iterative loop that converges to the result of interest. The numerical operations in such algorithms are generally implemented using finite-precision arithmetic, either fixed- or floating-point, most of which operate least-significant digit first. This results in a fundamental problem: if, after some time, the result has not converged, is this because we have not run the algorithm for enough iterations or because the arithmetic in some iterations was insufficiently precise? There is no easy way to answer this question, so users will often over-budget precision in the hope that the answer will always be to run for a few more iterations. We propose a fundamentally new approach: with the appropriate arithmetic able to generate results from most-significant digit first, we show that fixed compute-area hardware can be used to calculate an arbitrary number of algorithmic iterations to arbitrary precision, with both precision and approximant index increasing in lockstep. Consequently, datapaths constructed following our principles demonstrate efficiency over their traditional arithmetic equivalents where the latter's precisions are either under- or over-budgeted for the computation of a result to a particular accuracy. Use of most-significant digit-first arithmetic additionally allows us to declare certain digits to be stable at runtime, avoiding their recalculation in subsequent iterations and thereby increasing performance and decreasing memory footprints. Versus arbitrary-precision iterative solvers without the optimisations we detail herein, we achieve up-to 16x performance speedups and 1.9x memory savings for the evaluated benchmarks.
Issue Date: Feb-2020
Date of Acceptance: 22-Sep-2019
DOI: 10.1109/TVLSI.2019.2945257
ISSN: 1063-8210
Publisher: IEEE
Start Page: 516
End Page: 529
Journal / Book Title: IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume: 28
Issue: 2
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Royal Academy Of Engineering
Imagination Technologies Ltd
Imperial College London
Funder's Grant Number: EP/P010040/1
11908 (EP/K034448/1)
Prof Constantinides Chair
Prof Constantinides Chair
Imperial College London
Keywords: cs.AR
Computer Hardware & Architecture
0805 Distributed Computing
0906 Electrical and Electronic Engineering
1006 Computer Hardware
Publication Status: Published
Open Access location:
Online Publication Date: 2019-10-24
Appears in Collections:Electrical and Electronic Engineering
Faculty of Engineering

Unless otherwise indicated, items in Spiral are protected by copyright and are licensed under a Creative Commons Attribution NonCommercial NoDerivatives License.

Creative Commons