A low complexity scaling method for the Lanczos Kernel in fixed-point arithmetic
File(s)IEEETC_paper_accepted.pdf (701.54 KB)
Accepted version
Author(s)
Jerez, JL
Constantinides, GA
Kerrigan, EC
Type
Journal Article
Abstract
We consider the problem of enabling fixed-point implementation of linear algebra kernels on low-cost embedded systems, as well as motivating more efficient computational architectures for scientific applications. Fixed-point arithmetic presents additional design challenges compared to floating-point arithmetic, such as having to bound peak values of variables and control their dynamic ranges. Algorithms for solving linear equations or finding eigenvalues are typically nonlinear and iterative, making solving these design challenges a nontrivial task. For these types of algorithms, the bounding problem cannot be automated by current tools. We focus on the Lanczos iteration, the heart of well-known methods such as conjugate gradient and minimum residual. We show how one can modify the algorithm with a low-complexity scaling procedure to allow us to apply standard linear algebra to derive tight analytical bounds on all variables of the process, regardless of the properties of the original matrix. It is shown that the numerical behavior of fixed-point implementations of the modified problem can be chosen to be at least as good as a floating-point implementation, if necessary. The approach is evaluated on field-programmable gate array (FPGA) platforms, highlighting orders of magnitude potential performance and efficiency improvements by moving form floating-point to fixed-point computation.
Date Issued
2015-02-01
Online Publication Date
2015-02-01
2015-11-09T14:26:19Z
Date Acceptance
2013-07-29
ISSN
0018-9340
Publisher
Institute of Electrical and Electronics Engineers
Start Page
303
End Page
315
Journal / Book Title
IEEE Transactions on Computers
Volume
64
Issue
2
Copyright Statement
© 2015 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.
Source Database
web-of-science
Sponsor
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Identifier
https://ieeexplore.ieee.org/document/6577389
Grant Number
EP/G031576/1
EP/I020357/1
EP/I012036/1
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Engineering, Electrical & Electronic
Computer Science
Engineering
Computer arithmetic
computations on matrices
numerical algorithms
design aids
PERFORMANCE
ALGORITHMS
SYSTEMS
Computer Hardware & Architecture
0803 Computer Software
0805 Distributed Computing
1006 Computer Hardware
Publication Status
Published