architect: Arbitrary-precision Constant-hardware Iterative Compute

File Description SizeFormat 
fpt17.pdfAccepted version451.08 kBAdobe PDFView/Open
Title: architect: Arbitrary-precision Constant-hardware Iterative Compute
Authors: Li, H
Davis, JJ
Wickerson, JP
Constantinides, GA
Item Type: Conference Paper
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: armed 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 iteration index increasing in lockstep. Thus, 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. For the execution of 100 iterations of the Jacobi method, we obtain a 1.60x increase in frequency and 15.7x LUT and 50.2x flip-flop reductions over a 2048-bit parallel-in, serial-out traditional arithmetic equivalent, along with 46.2x LUT and 83.3x flip-flop decreases versus the state-of-the-art online arithmetic implementation.
Issue Date: 5-Feb-2018
Date of Acceptance: 15-Sep-2017
ISBN: 978-1-5386-2656-6
Publisher: IEEE
Start Page: 73
End Page: 79
Journal / Book Title: 2017 International Conference on Field Programmable Technology (ICFPT)
Copyright Statement: © 2017 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.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Royal Academy Of Engineering
Imagination Technologies Ltd
Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: 11908 (EP/K034448/1)
Prof Constantinides Chair
Prof Constantinides Chair
Conference Name: International Conference on Field-programmable Technology (FPT) 2017
Keywords: Science & Technology
Computer Science, Information Systems
Engineering, Electrical & Electronic
Computer Science
Publication Status: Published
Start Date: 2017-12-11
Finish Date: 2017-12-13
Conference Place: Melbourne, Australia
Online Publication Date: 2018-02-05
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