An analytical approach for error PMF characterization in approximate circuits

Deepashree Sengupta; Farhana Sharmin Snigdha; Jiang Hu; Sachin S. Sapatnekar

doi:10.1109/TCAD.2018.2803626

An analytical approach for error PMF characterization in approximate circuits

Deepashree Sengupta, Farhana Sharmin Snigdha, Jiang Hu, Sachin S. Sapatnekar

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

Approximate computing has emerged as a circuit design technique that can reduce system power without significantly sacrificing the output quality in error-resilient applications. However, there exists only a few approaches for systematically and efficiently determining the error introduced by approximate hardware units. This paper focuses on the development of error analysis techniques for approximate circuits consisting of adders and multipliers, which are the key hardware components used in error-resilient applications. A novel algorithm has been presented, using the Fourier and the Mellin transforms, that efficiently determines the probability distribution of the error introduced by approximation in a circuit, abstracted as a directed acyclic graph. The algorithm is generalized for signed operations through two's complement representation, and its accuracy is demonstrated to be within 1% of Monte Carlo simulations, while being over an order of magnitude faster.

Original language	English (US)
Article number	8283743
Pages (from-to)	70-83
Number of pages	14
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	38
Issue number	1
DOIs	https://doi.org/10.1109/TCAD.2018.2803626
State	Published - Jan 2019

Bibliographical note

Funding Information:
Dr. Sengupta was a recipient of the Doctoral Dissertation Fellowship from the University of Minnesota.

Funding Information:
Manuscript received March 20, 2017; revised July 28, 2017 and October 25, 2017; accepted December 20, 2017. Date of publication February 7, 2018; date of current version December 19, 2018. This work was supported in part by the NSF under Awards CCF-1162267, CCF-1525925, and CCF-1525749, and in part by the 2016 Doctoral Dissertation Fellowship from University of Minnesota. This paper was recommended by Associate Editor J. Cortadella. (Corresponding author: Deepashree Sengupta.) D. Sengupta, F. S. Snigdha, and S. S. Sapatnekar are with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: sengupta@umn.edu).

Publisher Copyright:
© 1982-2012 IEEE.

Keywords

Approximate computing
Fourier transform
Mellin transform
error distribution

Publisher link

10.1109/TCAD.2018.2803626

Find It

Find It at U of M Libraries

Cite this

@article{7b3fbc94e98d4e72adba9696362d08e9,

title = "An analytical approach for error PMF characterization in approximate circuits",

abstract = "Approximate computing has emerged as a circuit design technique that can reduce system power without significantly sacrificing the output quality in error-resilient applications. However, there exists only a few approaches for systematically and efficiently determining the error introduced by approximate hardware units. This paper focuses on the development of error analysis techniques for approximate circuits consisting of adders and multipliers, which are the key hardware components used in error-resilient applications. A novel algorithm has been presented, using the Fourier and the Mellin transforms, that efficiently determines the probability distribution of the error introduced by approximation in a circuit, abstracted as a directed acyclic graph. The algorithm is generalized for signed operations through two's complement representation, and its accuracy is demonstrated to be within 1% of Monte Carlo simulations, while being over an order of magnitude faster.",

keywords = "Approximate computing, Fourier transform, Mellin transform, error distribution",

author = "Deepashree Sengupta and Snigdha, {Farhana Sharmin} and Jiang Hu and Sapatnekar, {Sachin S.}",

note = "Funding Information: Dr. Sengupta was a recipient of the Doctoral Dissertation Fellowship from the University of Minnesota. Funding Information: Manuscript received March 20, 2017; revised July 28, 2017 and October 25, 2017; accepted December 20, 2017. Date of publication February 7, 2018; date of current version December 19, 2018. This work was supported in part by the NSF under Awards CCF-1162267, CCF-1525925, and CCF-1525749, and in part by the 2016 Doctoral Dissertation Fellowship from University of Minnesota. This paper was recommended by Associate Editor J. Cortadella. (Corresponding author: Deepashree Sengupta.) D. Sengupta, F. S. Snigdha, and S. S. Sapatnekar are with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: sengupta@umn.edu). Publisher Copyright: {\textcopyright} 1982-2012 IEEE.",

year = "2019",

month = jan,

doi = "10.1109/TCAD.2018.2803626",

language = "English (US)",

volume = "38",

pages = "70--83",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - An analytical approach for error PMF characterization in approximate circuits

AU - Sengupta, Deepashree

AU - Snigdha, Farhana Sharmin

AU - Hu, Jiang

AU - Sapatnekar, Sachin S.

N1 - Funding Information: Dr. Sengupta was a recipient of the Doctoral Dissertation Fellowship from the University of Minnesota. Funding Information: Manuscript received March 20, 2017; revised July 28, 2017 and October 25, 2017; accepted December 20, 2017. Date of publication February 7, 2018; date of current version December 19, 2018. This work was supported in part by the NSF under Awards CCF-1162267, CCF-1525925, and CCF-1525749, and in part by the 2016 Doctoral Dissertation Fellowship from University of Minnesota. This paper was recommended by Associate Editor J. Cortadella. (Corresponding author: Deepashree Sengupta.) D. Sengupta, F. S. Snigdha, and S. S. Sapatnekar are with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: sengupta@umn.edu). Publisher Copyright: © 1982-2012 IEEE.

PY - 2019/1

Y1 - 2019/1

N2 - Approximate computing has emerged as a circuit design technique that can reduce system power without significantly sacrificing the output quality in error-resilient applications. However, there exists only a few approaches for systematically and efficiently determining the error introduced by approximate hardware units. This paper focuses on the development of error analysis techniques for approximate circuits consisting of adders and multipliers, which are the key hardware components used in error-resilient applications. A novel algorithm has been presented, using the Fourier and the Mellin transforms, that efficiently determines the probability distribution of the error introduced by approximation in a circuit, abstracted as a directed acyclic graph. The algorithm is generalized for signed operations through two's complement representation, and its accuracy is demonstrated to be within 1% of Monte Carlo simulations, while being over an order of magnitude faster.

AB - Approximate computing has emerged as a circuit design technique that can reduce system power without significantly sacrificing the output quality in error-resilient applications. However, there exists only a few approaches for systematically and efficiently determining the error introduced by approximate hardware units. This paper focuses on the development of error analysis techniques for approximate circuits consisting of adders and multipliers, which are the key hardware components used in error-resilient applications. A novel algorithm has been presented, using the Fourier and the Mellin transforms, that efficiently determines the probability distribution of the error introduced by approximation in a circuit, abstracted as a directed acyclic graph. The algorithm is generalized for signed operations through two's complement representation, and its accuracy is demonstrated to be within 1% of Monte Carlo simulations, while being over an order of magnitude faster.

KW - Approximate computing

KW - Fourier transform

KW - Mellin transform

KW - error distribution

UR - http://www.scopus.com/inward/record.url?scp=85041519500&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041519500&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2018.2803626

DO - 10.1109/TCAD.2018.2803626

M3 - Article

AN - SCOPUS:85041519500

SN - 0278-0070

VL - 38

SP - 70

EP - 83

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 1

M1 - 8283743

ER -

An analytical approach for error PMF characterization in approximate circuits

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this