Article

Performance analysis of concurrent systems with early evaluation

Authors:

Jorge Júlvez,

Jordi Cortadella,

Michael KishinevskyAuthors Info & Claims

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

Pages 448 - 455

https://doi.org/10.1145/1233501.1233590

Published: 05 November 2006 Publication History

Get Access

Abstract

Early evaluation allows to execute operations when enough information at the inputs has been received to determine the value at the outputs. Systems that can tolerate variable-latency units, such as latency-insensitive or asynchronous systems, can enhance their performance by using early evaluation. The most relevant example of a unit with early evaluation is the multiplexor: the output can be determined as soon as the information of the selected channel arrives, without waiting for the other channels.

This paper analyzes the potential impact of early evaluation in concurrent systems. An analytical model, based on a Petri net extension with early firing is proposed to estimate the performance. The reduction of the analytical model to a linear programming formulation for an efficient estimation of the upper bound for the system throughput is proposed. The results show the accuracy of the model and the benefits of early evaluation.

References

[1]

M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling with Generalized Stochastic Petri Nets. Wiley, 1995.

Digital Library

Google Scholar

[2]

C. Brej and J. Garside. Early output logic using anti-tokens. In Int. Workshop on Logic Synthesis, pages 302--309, May 2003.

Google Scholar

[3]

J. Campos, G. Chiola, and M. Silva. Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector. IEEE Transactions on Software Engineering, 17(2):117--125, February 1991.

Digital Library

Google Scholar

[4]

L. Carloni, K. McMillan, and A. Sangiovanni-Vincentelli. Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design, 20(9):1059--1076, Sept. 2001.

Digital Library

Google Scholar

[5]

F. Commoner, A. W. Holt, S. Even, and A. Pnueli. Marked directed graphs. Journal of Computer and System Sciences, 5:511--523, 1971.

Digital Library

Google Scholar

[6]

A. Dasdan and R. K. Gupta. Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Transactions on Computer-Aided Design, 17(10):889--899, 1998.

Digital Library

Google Scholar

[7]

R. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309--311, 1978.

Crossref

Google Scholar

[8]

M. K. Molloy. Performance Analysis Using Stochastic Petri Nets. IEEE Trans. on Computers, 31(9):913--917, 1982.

Digital Library

Google Scholar

[9]

T. Murata. Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, pages 541--580, Apr. 1989.

Google Scholar

[10]

R. Reese, M. Thornton, C. Traver, and D. Hemmendinger. Early evaluation for performance enhancement in phased logic. IEEE Transactions on Computer-Aided Design, 24(4):532--550, Apr. 2005.

Digital Library

Google Scholar

[11]

J. Sparsø and S. Furber, editors. Principles of Asynchronous Circuit Design: A Systems Perspective. Kluwer Academic Publishers, 2001.

Crossref

Google Scholar

[12]

A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, and M. Pietkiewicz-Koutny. On the models for asynchronous circuit behaviour with OR causality. Formal Methods in System Design, 9(3):189--233, 1996.

Digital Library

Google Scholar

Cited By

View all

Kilada EStevens KPhillips JHu AGraeb H(2011)Synchronous elasticization at a reduced costProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132497(794-801)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132497
Casu M(2011)Half-buffer retiming and token cages for synchronous elastic circuitsIET Computers & Digital Techniques10.1049/iet-cdt.2010.01165:4(318-330)Online publication date: Jul-2011
https://doi.org/10.1049/iet-cdt.2010.0116
Galceran-Oms MCortadella JKishinevsky MScheffer LPhillips JHu A(2010)Symbolic performance analysis of elastic systemsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133593(778-785)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133593
Show More Cited By

Recommendations

Early Thermographic Screening of Breast Abnormality in Women with Dense Breast by Thermal, Fractal, and Statistical Analysis
Artificial Intelligence over Infrared Images for Medical Applications and Medical Image Assisted Biomarker Discovery
Abstract
Objectives: Breast cancer is the prime reason for cancer mortality in women across the globe and India. Early screening to identify breast abnormality before the actual symptoms are visible is the only effective way of reducing associated ...
3D shape analysis for early diagnosis of malignant lung nodules
MICCAI'11: Proceedings of the 14th international conference on Medical image computing and computer-assisted intervention - Volume Part III

An alternative method of diagnosing malignant lung nodules by their shape, rather than conventional growth rate, is proposed. The 3D surfaces of the detected lung nodules are delineated by spherical harmonic analysis that represents a 3D surface of the ...
Performance analysis of MIMO systems with multiuser diversity

In this paper, we present a comprehensive performance analysis for multiple-input multiple-output (MIMO) systems with multiuser diversity over Rayleigh fading channels. We derive exact closed-form expressions of the outage probability and the average ...

Comments

Information & Contributors

Information

Published In

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
161
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kilada EStevens KPhillips JHu AGraeb H(2011)Synchronous elasticization at a reduced costProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132497(794-801)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132497
Casu M(2011)Half-buffer retiming and token cages for synchronous elastic circuitsIET Computers & Digital Techniques10.1049/iet-cdt.2010.01165:4(318-330)Online publication date: Jul-2011
https://doi.org/10.1049/iet-cdt.2010.0116
Galceran-Oms MCortadella JKishinevsky MScheffer LPhillips JHu A(2010)Symbolic performance analysis of elastic systemsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133593(778-785)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133593
Galceran-Oms MCortadella JBufistov DKishinevsky MDe Micheli GAl-Hashimi BMueller WMacii E(2010)Automatic microarchitectural pipeliningProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871160(961-964)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871160
Júlvez J(2009)Basic qualitative properties of Petri nets with multi-guarded transitionsProceedings of the 2009 conference on American Control Conference10.5555/1702715.1703159(5026-5031)Online publication date: 10-Jun-2009
https://dl.acm.org/doi/10.5555/1702715.1703159
Bufistov DCortadella JGalceran-Oms MJúlvez JKishinevsky M(2009)Retiming and recycling for elastic systems with early evaluationProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1629988(288-291)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1629988
Li CCarloni L(2009)Leveraging local intracore information to increase global performance in block-based design of systems-on-chipIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200915728:2(165-178)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TCAD.2008.2009157
Casu MMacchiarulo L(2009)Adaptive Latency Insensitive Protocols and Elastic Circuits with Early EvaluationElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2009.07.027245(35-50)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.entcs.2009.07.027
Kam TKishinevsky MCortadella JGalceran-Oms MNassif SRoychowdhury J(2008)Correct-by-construction microarchitectural pipeliningProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509558(434-441)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509558
Hoover GBrewer FSciuto D(2008)Synthesizing synchronous elastic flow networksProceedings of the conference on Design, automation and test in Europe10.1145/1403375.1403449(306-311)Online publication date: 10-Mar-2008
https://dl.acm.org/doi/10.1145/1403375.1403449
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Cited By

Index Terms

Recommendations

Early Thermographic Screening of Breast Abnormality in Women with Dense Breast by Thermal, Fractal, and Statistical Analysis

3D shape analysis for early diagnosis of malignant lung nodules

Performance analysis of MIMO systems with multiuser diversity

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Early Thermographic Screening of Breast Abnormality in Women with Dense Breast by Thermal, Fractal, and Statistical Analysis

3D shape analysis for early diagnosis of malignant lung nodules

Performance analysis of MIMO systems with multiuser diversity

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations