More Web Proxy on the site http://driver.im/

research-article

ParaLog: enabling and accelerating online parallel monitoring of multithreaded applications

Authors:

Evangelos Vlachos,

Michelle L. Goodstein,

Michael A. Kozuch,

Phillip B. Gibbons,

Todd C. MowryAuthors Info & Claims

ASPLOS XV: Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems

Pages 271 - 284

https://doi.org/10.1145/1736020.1736051

Published: 13 March 2010 Publication History

Abstract

Instruction-grain lifeguards monitor the events of a running application at the level of individual instructions in order to identify and help mitigate application bugs and security exploits. Because such lifeguards impose a 10-100X slowdown on existing platforms, previous studies have proposed hardware designs to accelerate lifeguard processing. However, these accelerators are either tailored to a specific class of lifeguards or suitable only for monitoring singlethreaded programs.

We present ParaLog, the first design of a system enabling fast online parallel monitoring of multithreaded parallel applications. ParaLog supports a broad class of software-defined lifeguards. We show how three existing accelerators can be enhanced to support online multithreaded monitoring, dramatically reducing lifeguard overheads. We identify and solve several challenges in monitoring parallel applications and/or parallelizing these accelerators, including (i) enforcing inter-thread data dependences, (ii) dealing with inter-thread effects that are not reflected in coherence traffic, (iii) dealing with unmonitored operating system activity, and (iv) ensuring lifeguards can access shared metadata with negligible synchronization overheads. We present our system design for both Sequentially Consistent and Total Store Ordering processors. We implement and evaluate our design on a 16 core simulated CMP, using benchmarks from SPLASH-2 and PARSEC and two lifeguards: a data-flow tracking lifeguard and a memory-access checker lifeguard. Our results show that (i) our parallel accelerators improve performance by 2-9X and 1.13-3.4X for our two lifeguards, respectively, (ii) we are 5-126X faster than the time-slicing approach required by existing techniques, and (iii) our average overheads for applications with eight threads are 51% and 28% for the two lifeguards, respectively.

References

[1]

C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In PACT, 2008.

Digital Library

[2]

D. Bruening. Efficient, Transparent, and Comprehensive Runtime Code Manipulation. PhD thesis, MIT, 2004.

Digital Library

[3]

W. R. Bush, J. D. Pincus, and D. J. Sielaff. A static analyzer for finding dynamic programming errors. Software -- Practice and Experience, 30(7), 2000.

Digital Library

[4]

S. Chen, B. Falsafi, P. B. Gibbons, M. Kozuch, T. C. Mowry, R. Teodorescu, A. Ailamaki, L. Fix, G. R. Ganger, B. Lin, and S. W. Schlosser. Log-based architectures for general-purpose monitoring of deployed code. In ASID Workshop at ASPLOS, 2006.

Digital Library

[5]

S. Chen, M. Kozuch, P. B. Gibbons, M. Ryan, T. Strigkos, T. C. Mowry, O. Ruwase, E. Vlachos, B. Falsafi, and V. Ramachandran. Flexible hardware acceleration for instruction-grain lifeguards. IEEE Micro, 29(1):62--72, 2009. Top Picks from the 2008 Computer Architecture Conferences.

Digital Library

[6]

S. Chen, M. Kozuch, T. Strigkos, B. Falsafi, P. B. Gibbons, T. C. Mowry, V. Ramachandran, O. Ruwase, M. Ryan, and E. Vlachos. Flexible hardware acceleration for instruction-grain program monitoring. In ISCA, 2008.

Digital Library

[7]

J. Chung, M. Dalton, H. Kannan, and C. Kozyrakis. Thread-safe dynamic binary translation using transactional memory. In HPCA, 2008.

[8]

M. L. Corliss, E. C. Lewis, and A. Roth. DISE: A programmable macro engine for customizing applications. In ISCA, 2003.

Digital Library

[9]

J. R. Crandall and F. T. Chong. Minos: Control data attack prevention orthogonal to memory model. In MICRO, 2004.

Digital Library

[10]

M. Dalton, H. Kannan, and C. Kozyrakis. Raksha: A flexible information flow architecture for software security. In ISCA, 2007.

Digital Library

[11]

D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system--specific, programmer-written compiler extensions. In OSDI, 2000.

Digital Library

[12]

M. D. Ernst, J. Cockrell,W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. IEEE Trans. Software Engineering, 27(2), 2001.

Digital Library

[13]

C. Flanagan, K. R. M. Leino, M. Lillibridge, G. Nelson, J. B. Saxe, and R. Stata. Extended static checking for Java. In PLDI, 2002.

Digital Library

[14]

D. Geels, G. Altekar, S. Shenker, and I. Stoica. Replay debugging for distributed applications. In USENIX ATEC, 2006.

Digital Library

[15]

C. Gniady, B. Falsafi, and T. N. Vijaykumar. Is SC + ILP = RC? In ISCA, 1999.

Digital Library

[16]

M. L. Goodstein, E. Vlachos, S. Chen, P. B. Gibbons, M. Kozuch, and T. C. Mowry. Butterfly analysis: Adapting dataflow analysis to dynamic parallel monitoring. In ASPLOS, 2010.

Digital Library

[17]

M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In HPCA, 1993.

Digital Library

[18]

D. R. Hower and M. D. Hill. Rerun: Exploiting episodes for lightweight memory race recording. In ISCA, 2008.

Digital Library

[19]

HP Labs. Cacti 5.1 Technical Report. http://www.hpl.hp.com/research/cacti/.

[20]

H. Kannan. Ordering decoupled metadata accesses in multiprocessors. In MICRO, 2009.

Digital Library

[21]

C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: Building customized program analysis tools with dynamic instrumentation. In PLDI, 2005.

Digital Library

[22]

P. Montesinos, L. Ceze, and J. Torrellas. DeLorean: Recording and deterministically replaying shared-memory multiprocessor execution efficiently. In ISCA, 2008.

Digital Library

[23]

P. Montesinos, M. Hicks, S. T. King, and J. Torrellas. Capo: A software-hardware interface for practical deterministic multiprocessor replay. In ASPLOS, 2009.

Digital Library

[24]

S. S. Mukherjee, B. Falsafi, M. D. Hill, and D. A. Wood. Coherent network interfaces for fine-grain communication. In ISCA, 1996.

Digital Library

[25]

V. Nagarajan and R. Gupta. Architectural support for shadow memory in multiprocessors. In VEE, 2009.

Digital Library

[26]

S. Narayanasamy, C. Pereira, and B. Calder. Recording shared memory dependencies using strata. In ASPLOS, 2006.

Digital Library

[27]

S. Narayanasamy, G. Pokam, and B. Calder. BugNet: Continuously recording program execution for deterministic replay debugging. In ISCA, 2005.

Digital Library

[28]

N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, U. Cambridge, 2004. http://valgrind.org.

[29]

N. Nethercote and J. Seward. Valgrind: A program supervision framework. Electronic Notes in Theoretical Computer Science, 89(2), 2003.

[30]

N. Nethercote and J. Seward. How to shadow every byte of memory used by a program. In VEE, 2007.

Digital Library

[31]

N. Nethercote and J. Seward. Valgrind: A framework for heavyweight dynamic binary instrumentation. In PLDI, 2007.

Digital Library

[32]

J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In NDSS, 2005.

[33]

E. B. Nightingale, D. Peek, P. M. Chen, and J. Flinn. Parallelizing security checks on commodity hardware. In ASPLOS, 2008.

Digital Library

[34]

G. Pokam, C. Pereira, K. Danne, R. Kassa, and A.-R. Adl-Tabatabai. Architecting a chunk--based memory race recorder in modern CMPs. In MICRO, 2009.

Digital Library

[35]

F. Qin, C.Wang, Z. Li, H. Kim, Y. Zhou, and Y. Wu. LIFT: A low-overhead practical information flow tracking system for detecting security attacks. In MICRO, 2006.

Digital Library

[36]

O. Ruwase, P. B. Gibbons, T. C. Mowry, V. Ramachandran, S. Chen, M. Kozuch, and M. Ryan. Parallelizing Dynamic Information Flow Tracking. In SPAA, 2008.

Digital Library

[37]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic race detector for multi-threaded programs. ACM TOCS, 15(4), 1997.

Digital Library

[38]

R. Shetty, M. Kharbutli, Y. Solihin, and M. Prvulovic. Heapmon: A helper-thread approach to programmable, automatic, and lowoverhead memory bug detection. IBM J. on Research and Development, 50(2/3), 2006.

Digital Library

[39]

G. E. Suh, J. W. Lee, D. Zhang, and S. Devadas. Secure program execution via dynamic information flow tracking. In ASPLOS, 2004.

Digital Library

[40]

G.-R. Uh, R. Cohn, B. Yadavalli, R. Peri, and R. Ayyagari. Analyzing dynamic binary instrumentation overhead. In WBIA Workshop at ASPLOS, 2006.

[41]

G. Venkataramani, I. Doudalis, Y. Solihin, and M. Prvulovic. Flexi-Taint: A programmable accelerator for dynamic taint propagation. In HPCA, 2008.

[42]

G. Venkataramani, B. Roemer, Y. Solihin, and M. Prvulovic. Mem-Tracker: Efficient and programmable support for memory access monitoring and debugging. In HPCA, 2007.

Digital Library

[43]

Virtutech Simics. http://www.virtutech.com/.

[44]

S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In ISCA, 1995.

Digital Library

[45]

M. Xu, R. Bodik, and M. D. Hill. A 'Flight Data Recorder' for enabling full-system multiprocessor deterministic replay. In ISCA, 2003.

Digital Library

[46]

M. Xu, R. Bodik, and M. D. Hill. A regulated transitive reduction (RTR) for longer memory race recording. In ASPLOS, 2006.

Digital Library

[47]

P. Zhou, R. Teodorescu, and Y. Zhou. HARD: Hardware-assisted lockset-based race detection. In HPCA, 2007.

Digital Library

[48]

Y. Zhou, P. Zhou, F. Qin,W. Liu, and J. Torrellas. Efficient and flexible architectural support for dynamic monitoring. ACM TACO, 2(1), 2005.

Digital Library

Cited By

Zhang YLiu TSun ZChen ZLi XZuo ZJust RFraser G(2023)Catamaran: Low-Overhead Memory Safety Enforcement via Parallel AccelerationProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598098(816-828)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598098
Chowdhary SNagarakatte SSpinellis DGousios GChechik MDi Penta M(2021)Parallel shadow execution to accelerate the debugging of numerical errorsProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468585(615-626)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468585
Song YLee Y(2017)A Parallel FastTrack Data Race Detector on Multi-core Systems2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.87(387-396)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.87
Show More Cited By

Index Terms

ParaLog: enabling and accelerating online parallel monitoring of multithreaded applications

Recommendations

ParaLog: enabling and accelerating online parallel monitoring of multithreaded applications
ASPLOS '10

Instruction-grain lifeguards monitor the events of a running application at the level of individual instructions in order to identify and help mitigate application bugs and security exploits. Because such lifeguards impose a 10-100X slowdown on existing ...
ParaLog: enabling and accelerating online parallel monitoring of multithreaded applications
ASPLOS '10

Instruction-grain lifeguards monitor the events of a running application at the level of individual instructions in order to identify and help mitigate application bugs and security exploits. Because such lifeguards impose a 10-100X slowdown on existing ...
Efficient Java exception handling in just-in-time compilation
Research Articles

Java uses exceptions to provide elegant error handling capabilities during program execution. However, the presence of exception handlers complicates the job of the just-in-time (JIT) compiler, while exceptions are rarely used in most programs. This ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS XV: Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems

March 2010

422 pages

ISBN:9781605588391

DOI:10.1145/1736020

General Chair:
James C. Hoe
Carnegie Mellon University, USA
,
Program Chair:
Vikram S. Adve
University of Illinois at Urbana-Champaign, USA

ACM SIGARCH Computer Architecture News Volume 38, Issue 1
ASPLOS '10
March 2010
399 pages
ISSN:0163-5964
DOI:10.1145/1735970
Issue’s Table of Contents
ACM SIGPLAN Notices Volume 45, Issue 3
ASPLOS '10
March 2010
399 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1735971
Issue’s Table of Contents

Copyright © 2010 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 March 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASPLOS '10

Sponsor:

ASPLOS '10: Architectural Support for Programming Languages and Operating Systems

March 13 - 17, 2010

Pennsylvania, Pittsburgh, USA

Acceptance Rates

ASPLOS XV Paper Acceptance Rate 32 of 181 submissions, 18%;

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
533
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YLiu TSun ZChen ZLi XZuo ZJust RFraser G(2023)Catamaran: Low-Overhead Memory Safety Enforcement via Parallel AccelerationProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598098(816-828)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598098
Chowdhary SNagarakatte SSpinellis DGousios GChechik MDi Penta M(2021)Parallel shadow execution to accelerate the debugging of numerical errorsProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468585(615-626)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468585
Song YLee Y(2017)A Parallel FastTrack Data Race Detector on Multi-core Systems2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.87(387-396)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.87
Lucia BCeze LOlukotun KSmith AHundt RMars J(2015)Data provenance tracking for concurrent programsProceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization10.5555/2738600.2738619(146-156)Online publication date: 7-Feb-2015
https://dl.acm.org/doi/10.5555/2738600.2738619
Goodstein MGibbons PKozuch MMowry T(2015)Tracking and Reducing Uncertainty in Dataflow Analysis-Based Dynamic Parallel MonitoringProceedings of the 2015 International Conference on Parallel Architecture and Compilation (PACT)10.1109/PACT.2015.20(266-279)Online publication date: 18-Oct-2015
https://dl.acm.org/doi/10.1109/PACT.2015.20
Lucia BCeze L(2015)Data provenance tracking for concurrent programs2015 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2015.7054195(146-156)Online publication date: Feb-2015
https://doi.org/10.1109/CGO.2015.7054195
Devecsery DChow MDou XFlinn JChen PFlinn JLevy H(2014)Eidetic systemsProceedings of the 11th USENIX conference on Operating Systems Design and Implementation10.5555/2685048.2685090(525-540)Online publication date: 6-Oct-2014
https://dl.acm.org/doi/10.5555/2685048.2685090
Deng DZhang WLu S(2013)Efficient concurrency-bug detection across inputsACM SIGPLAN Notices10.1145/2544173.250953948:10(785-802)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509539
Deng DZhang WLu SHosking AEugster PLopes C(2013)Efficient concurrency-bug detection across inputsProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509539(785-802)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509539
Wester BDevecsery DChen PFlinn JNarayanasamy S(2013)Parallelizing data race detectionACM SIGPLAN Notices10.1145/2499368.245112048:4(27-38)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451120
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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents