NDLI: Estimation of probabilistic bounds on phase CPI and relevance in WCET analysis

Please wait, while we are loading the content...

Wireless innovations for smartphones

Internet-of-energy: combining embedded computing and communication for the smart grid

Debugging embedded multimedia application traces through periodic pattern mining

Finite automata with time-delay blocks

Server-based scheduling of parallel real-time tasks

Trigger memoization in self-triggered control

Shared hardware data structures for hard real-time systems

Code-level timing analysis of embedded software: emsoft'12 invited talk session outline

Estimation of probabilistic bounds on phase CPI and relevance in WCET analysis

An overview of the career of Paul Caspi

Programming parallelism with futures in lustre

On model based synthesis of embedded control software

Mixed critical system design and analysis

Computing without processors

Trends in automotive embedded systems

Smart layers and dumb result: IO characterization of an android-based smartphone

Synthesis from incompatible specifications

Operating system support for redundant multithreading

Feedback thermal control of real-time systems on multicore processors

A low-overhead dedicated execution support for stream applications on shared-memory cmp

Assessing the suitability of the NGMP multi-core processor in the space domain

Towards network-on-chip agreement protocols

A new data flow analysis model for TDM

Runtime verification of real-time embedded systems

A standards-based, fully-open software platform for smart embedded systems

Research issues in smart phones, notepads and related services

XEMU: an efficient QEMU based binary mutation testing framework for embedded software

Timed model checking with abstractions: towards worst-case response time analysis in resource-sharing manycore systems

Flattening hierarchical scheduling

Synthesis of minimal-error control software

Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared srams

Compositional temporal analysis model for incremental hard real-time system design

Input-output robustness for discrete systems

Estimation of probabilistic bounds on phase CPI and relevance in WCET analysis

Content Provider	ACM Digital Library
Author	Ravindar, Archana Srikant, Y. N.
Abstract	Estimating program worst case execution time(WCET) accurately and efficiently is a challenging task. Several programs exhibit phase behavior wherein cycles per instruction (CPI) varies in phases during execution. Recent work has suggested the use of phases in such programs to estimate WCET with minimal instrumentation. However the suggested model uses a function of mean CPI that has no probabilistic guarantees. We propose to use Chebyshev's inequality that can be applied to any arbitrary distribution of CPI samples, to probabilistically bound CPI of a phase. Applying Chebyshev's inequality to phases that exhibit high CPI variation leads to pessimistic upper bounds. We propose a mechanism that refines such phases into sub-phases based on program counter(PC) signatures collected using profiling and also allows the user to control variance of CPI within a sub-phase. We describe a WCET analyzer built on these lines and evaluate it with standard WCET and embedded benchmark suites on two different architectures for three chosen probabilities, p={0.9, 0.95 and 0.99}. For p=0.99, refinement based on PC signatures alone, reduces average pessimism of WCET estimate by 36%(77%) on Arch1(Arch2). Compared to Chronos, an open source static WCET analyzer, the average improvement in estimates obtained by refinement is 5%(125%) on Arch1(Arch2). On limiting variance of CPI within a sub-phase to {50%, 10%, 5% and 1%} of its original value, average accuracy of WCET estimate improves further to {9%, 11%, 12% and 13%} respectively, on Arch1. On Arch2, average accuracy of WCET improves to 159% when CPI variance is limited to 50% of its original value and improvement is marginal beyond that point.
Starting Page	165
Ending Page	174
Page Count	10
File Format	PDF
ISBN	9781450314251
DOI	10.1145/2380356.2380388
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-10-07
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Confidence intervals Probabilistic bounds Profiling Soft real-time systems Wcet analysis Phase behavior Cpi Chebyshev inequality
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in