Advances in computation of the maximum of a set of random variables

Debjit Sinha; Hai Zhou; Narendra V. Shenoy

doi:10.1109/ISQED.2006.22

Advances in computation of the maximum of a set of random variables

Debjit Sinha, Hai Zhou, Narendra V. Shenoy

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Scopus citations

Abstract

This paper quantifies the approximation error in Clark's approach presented in C. E. Clark (1961) to computing the maximum (max) of Gaussian random variables; a fundamental operation in statistical timing. We show that a finite look up table can be used to store these errors. Based on the error computations, approaches to different orderings for pair-wise max operations on a set of Gaussians are proposed. Experiments show accuracy improvements in the computation of the max of multiple Gaussians by up to 50% in comparison to the traditional approach. To the best of our knowledge, this is the first work addressing the mentioned issues.

Original language	English (US)
Title of host publication	Proceedings - 7th International Symposium on Quality Electronic Design, ISQED 2006
Pages	306-311
Number of pages	6
DOIs	https://doi.org/10.1109/ISQED.2006.22
State	Published - Dec 1 2006
Event	7th International Symposium on Quality Electronic Design, ISQED 2006 - San Jose, CA, United States Duration: Mar 27 2006 → Mar 29 2006

Publication series

Name	Proceedings - International Symposium on Quality Electronic Design, ISQED
ISSN (Print)	1948-3287
ISSN (Electronic)	1948-3295

Other

Other	7th International Symposium on Quality Electronic Design, ISQED 2006
Country/Territory	United States
City	San Jose, CA
Period	3/27/06 → 3/29/06

ASJC Scopus subject areas

Hardware and Architecture
Electrical and Electronic Engineering
Safety, Risk, Reliability and Quality

Access to Document

10.1109/ISQED.2006.22

Cite this

@inproceedings{9941cc5cec094b6d939185a14bd156ad,

title = "Advances in computation of the maximum of a set of random variables",

abstract = "This paper quantifies the approximation error in Clark's approach presented in C. E. Clark (1961) to computing the maximum (max) of Gaussian random variables; a fundamental operation in statistical timing. We show that a finite look up table can be used to store these errors. Based on the error computations, approaches to different orderings for pair-wise max operations on a set of Gaussians are proposed. Experiments show accuracy improvements in the computation of the max of multiple Gaussians by up to 50% in comparison to the traditional approach. To the best of our knowledge, this is the first work addressing the mentioned issues.",

author = "Debjit Sinha and Hai Zhou and Shenoy, {Narendra V.}",

year = "2006",

month = dec,

day = "1",

doi = "10.1109/ISQED.2006.22",

language = "English (US)",

isbn = "0769525237",

series = "Proceedings - International Symposium on Quality Electronic Design, ISQED",

pages = "306--311",

booktitle = "Proceedings - 7th International Symposium on Quality Electronic Design, ISQED 2006",

note = "7th International Symposium on Quality Electronic Design, ISQED 2006 ; Conference date: 27-03-2006 Through 29-03-2006",

}

Sinha, D, Zhou, H & Shenoy, NV 2006, Advances in computation of the maximum of a set of random variables. in Proceedings - 7th International Symposium on Quality Electronic Design, ISQED 2006., 1613154, Proceedings - International Symposium on Quality Electronic Design, ISQED, pp. 306-311, 7th International Symposium on Quality Electronic Design, ISQED 2006, San Jose, CA, United States, 3/27/06. https://doi.org/10.1109/ISQED.2006.22

Advances in computation of the maximum of a set of random variables. / Sinha, Debjit; Zhou, Hai; Shenoy, Narendra V.
Proceedings - 7th International Symposium on Quality Electronic Design, ISQED 2006. 2006. p. 306-311 1613154 (Proceedings - International Symposium on Quality Electronic Design, ISQED).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Advances in computation of the maximum of a set of random variables

AU - Sinha, Debjit

AU - Zhou, Hai

AU - Shenoy, Narendra V.

PY - 2006/12/1

Y1 - 2006/12/1

N2 - This paper quantifies the approximation error in Clark's approach presented in C. E. Clark (1961) to computing the maximum (max) of Gaussian random variables; a fundamental operation in statistical timing. We show that a finite look up table can be used to store these errors. Based on the error computations, approaches to different orderings for pair-wise max operations on a set of Gaussians are proposed. Experiments show accuracy improvements in the computation of the max of multiple Gaussians by up to 50% in comparison to the traditional approach. To the best of our knowledge, this is the first work addressing the mentioned issues.

AB - This paper quantifies the approximation error in Clark's approach presented in C. E. Clark (1961) to computing the maximum (max) of Gaussian random variables; a fundamental operation in statistical timing. We show that a finite look up table can be used to store these errors. Based on the error computations, approaches to different orderings for pair-wise max operations on a set of Gaussians are proposed. Experiments show accuracy improvements in the computation of the max of multiple Gaussians by up to 50% in comparison to the traditional approach. To the best of our knowledge, this is the first work addressing the mentioned issues.

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

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

U2 - 10.1109/ISQED.2006.22

DO - 10.1109/ISQED.2006.22

M3 - Conference contribution

AN - SCOPUS:84867807783

SN - 0769525237

SN - 9780769525235

T3 - Proceedings - International Symposium on Quality Electronic Design, ISQED

SP - 306

EP - 311

BT - Proceedings - 7th International Symposium on Quality Electronic Design, ISQED 2006

T2 - 7th International Symposium on Quality Electronic Design, ISQED 2006

Y2 - 27 March 2006 through 29 March 2006

ER -

Advances in computation of the maximum of a set of random variables

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this