NDLI: Efficient worst case timing analysis of data caching

Content Provider	IEEE Xplore Digital Library
Author	Sung-Kwan Kim Sang Lyul Min Rhan Ha
Copyright Year	1996
Description	Author affiliation: Dept. of Comput. Eng., Seoul Nat. Univ., South Korea (Sung-Kwan Kim; Sang Lyul Min)
Abstract	Recent progress in worst case timing analysis of programs has made it possible to perform accurate timing analysis of pipelined execution and instruction caching. However there has not been much progress in worst case timing analysis of data caching. This is mainly due to load/store instructions that reference multiple memory locations such as those used to implement array and pointer based references. These load/store instructions are called dynamic load/store instructions and most current analysis techniques take a very conservative approach to their timing analysis. In many cases, it is assumed that each of the references from a dynamic load/store instruction will miss in the cache and replace a cache block that would otherwise lead to a cache hit. This conservative approach results in severe overestimation of the worst case execution time (WCET). The paper proposes two techniques to minimize the WCET overestimation due to such load/store instructions. The first technique uses a global data flow analysis technique to reduce the number of load/store instructions that are misclassified as dynamic load/store instructions. The second technique utilizes data dependence analysis to minimize the adverse impact of dynamic load/store instructions. The paper also compares the WCET bounds of simple benchmark programs that are predicted with and without applying the proposed techniques. The results show that they significantly (up to 20%) improve the accuracy of WCET estimation especially for programs with a large number of references from dynamic load/store instructions.
Starting Page	230
Ending Page	240
File Size	1080253
Page Count	11
File Format	PDF
ISBN	0818674482
DOI	10.1109/RTTAS.1996.509540
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-06-10
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer aided software engineering Timing Data analysis Reduced instruction set computing Real time systems Computer aided instruction Scheduling algorithm Processor scheduling Computer languages Dynamic programming
Content Type	Text
Resource Type	Article

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

Worst case timing analysis of RISC processors: R3000/R3010 case study

An accurate worst case timing analysis for RISC processors

Satisfying real-time constraints with custom instructions

Worst case timing analysis for real-time programs

Improving the Worst-Case Execution Time Accuracy by Inter-Task Instruction Cache Analysis

Instruction-Set Customization for Real-Time Embedded Systems

A worst case timing analysis technique for multiple-issue machines

Improving Real-Time Software Quality by Direct Specification of Timing Requirements

A fast algorithm for scheduling instructions with deadline constraints on RISC machines

Efficient worst case timing analysis of data caching

Similar Documents

Worst case timing analysis of RISC processors: R3000/R3010 case study

An accurate worst case timing analysis for RISC processors

Satisfying real-time constraints with custom instructions

Worst case timing analysis for real-time programs

Improving the Worst-Case Execution Time Accuracy by Inter-Task Instruction Cache Analysis

Instruction-Set Customization for Real-Time Embedded Systems

A worst case timing analysis technique for multiple-issue machines

Improving Real-Time Software Quality by Direct Specification of Timing Requirements

A fast algorithm for scheduling instructions with deadline constraints on RISC machines

Efficient worst case timing analysis of data caching