Accurate critical path analysis via random trace construction

Pierre Salverda, Charles Tucker, Craig Zilles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a new approach to performing program analysis through, profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization
Pages64-73
Number of pages10
DOIs
StatePublished - May 19 2008

Publication series

NameProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization

Fingerprint

Critical path analysis
Hardware
Information use
Data storage equipment

Keywords

  • Instruction criticality
  • Profiling
  • Trace fabrication

ASJC Scopus subject areas

  • Software

Cite this

Salverda, P., Tucker, C., & Zilles, C. (2008). Accurate critical path analysis via random trace construction. In Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization (pp. 64-73). (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization). https://doi.org/10.1145/1356058.1356068

Accurate critical path analysis via random trace construction. / Salverda, Pierre; Tucker, Charles; Zilles, Craig.

Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization. 2008. p. 64-73 (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Salverda, P, Tucker, C & Zilles, C 2008, Accurate critical path analysis via random trace construction. in Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization. Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization, pp. 64-73. https://doi.org/10.1145/1356058.1356068
Salverda P, Tucker C, Zilles C. Accurate critical path analysis via random trace construction. In Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization. 2008. p. 64-73. (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization). https://doi.org/10.1145/1356058.1356068
Salverda, Pierre ; Tucker, Charles ; Zilles, Craig. / Accurate critical path analysis via random trace construction. Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization. 2008. pp. 64-73 (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization).
@inproceedings{d3efee897af14493beb41d00251fb161,
title = "Accurate critical path analysis via random trace construction",
abstract = "We present a new approach to performing program analysis through, profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.",
keywords = "Instruction criticality, Profiling, Trace fabrication",
author = "Pierre Salverda and Charles Tucker and Craig Zilles",
year = "2008",
month = "5",
day = "19",
doi = "10.1145/1356058.1356068",
language = "English (US)",
isbn = "9781595939784",
series = "Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization",
pages = "64--73",
booktitle = "Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization",

}

TY - GEN

T1 - Accurate critical path analysis via random trace construction

AU - Salverda, Pierre

AU - Tucker, Charles

AU - Zilles, Craig

PY - 2008/5/19

Y1 - 2008/5/19

N2 - We present a new approach to performing program analysis through, profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.

AB - We present a new approach to performing program analysis through, profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.

KW - Instruction criticality

KW - Profiling

KW - Trace fabrication

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

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

U2 - 10.1145/1356058.1356068

DO - 10.1145/1356058.1356068

M3 - Conference contribution

AN - SCOPUS:43449085237

SN - 9781595939784

T3 - Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization

SP - 64

EP - 73

BT - Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization

ER -