Embedded systems are often constrained in terms of both code size and execution time, because of a limited amount of available memory and real-time nature of applications. A dual instruction set processor, which supports a reduced instruction set (16 bits/instruction), in addition to a full instruction set (32 bits/instruction), allows an opportunity for a tradeoff between these two design criteria. Specifically, while the reduced instruction set can be used to reduce code size by providing smaller instructions, a program compiled into the reduced instruction set typically runs slower than the same program compiled into the full instruction set. Motivated by this observation, we propose a code generation technique that exploits this tradeoff relationship by selectively using the two instruction sets for different sections in the program. The proposed technique, called selective code transformation, not only provides a mechanism to enable a flexible tradeoff between a program's code size and its execution time, but also facilitates program optimization toward enhancing its worst case performance. The results from our experiments show that our proposed technique can be effectively used to fine-tune an application program on a spectrum of code size and execution performance, which, in turn, enables a system-wide optimization on memory space and execution speed involving multiple applications.

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in realtime computing systems where predictability is of utmost importance. We propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues.

We propose a technique for analyzing cache-related preemption delays of tasks that cause unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. The proposed technique consists of two steps. The first step performs a per-task analysis to estimate cache-related preemption cost for each execution point in a given task. The second step computes the worst case response time of each task that includes the cache-related preemption delay using a response time equation and a linear programming technique. This step takes as its input the preemption cost information of tasks obtained in the first step. This paper also compares the proposed approach with previous approaches. The results show that the proposed approach gives a prediction of the worst case cache-related preemption delay that is up to 60 percent tighter than those obtained from the previous approaches.

We propose an enhanced technique for analyzing, and thus bounding cache related preemption delay in fixed priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache related preemption delay. Second, the technique considers phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache related preemption delay. The paper also compares the proposed technique with previous techniques. The results show that the proposed technique gives up to 60% tighter prediction of the worst case response time than the previous techniques.

We propose a technique for analyzing cache-related preemption delays of tasks that cause unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. The proposed technique consists of two steps. The first step performs a per-task analysis to estimate cache-related preemption cost for each execution point in a given task from the number of useful cache blocks at the execution point. The second step computes the worst case response time of each task using a response time equation and a linear programming technique which takes as its input the preemption cost information of tasks obtained in the first step. Our experimental results show that the proposed technique gives a prediction of the worst case cache-related preemption delay that is up to 60% tighter than that obtained from previous approaches.

This paper presents a case study of worst case timing analysis for a RISC processor. The target machine consists of the R3000 CPU and R3010 FPA (Floating Point Accelerator). This target machine is typical of a RISC system with pipelined execution units and cache memories. Our methodology is an extension of the existing timing schema. The extended timing schema provides means to reason about the execution time variation of a program construct by surrounding program constructs due to pipelined execution and cache memories of RISC processors. The main focus of this paper is on explaining the necessary steps for performing timing analysis of a given target machine within the extended timing schema framework. This paper also gives results from experiments using a timing tool for the target machine that is built based on the extended timing schema approach.

An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each program construct is a simple time bound. In our approach, associated with each program construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. The paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach.>

An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real-time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, this paper proposes extensions of the original timing schema (Shaw, 1989) where the timing information associated with each program construct is a simple time-bound. We associate with each program construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time-bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. This paper also reports on preliminary results of WCET analyses for a pipelined processor. Our results show that up to 50% tighter WCET bounds can be obtained by using the revised timing schema.>

One of the obstacles to using RISC processors in a hard real-time environment is the unpredictability of caches. This unpredictability stems from basing them on a design that tries to optimize the average case execution time. We propose a dual mode instruction prefetch scheme as an alternative to instruction caching schemes. In the proposed scheme, a thread is associated with each instruction block. The thread indicates the instruction block that is to be prefetched once the block containing it is accessed by the processor. The proposed scheme operates in two different modes: real-time and non real-time modes. In the real-time mode, the prefetching of instruction blocks is made in the direction that improves the worst case execution time. For this purpose, the thread is generated by the compiler through an analysis of the worst case execution path. In the non real-time mode, the thread is dynamically updated so that it indicates the instruction block that is most likely to be accessed next is the block that was previously accessed after the present block. Therefore, the thread is made to point to such a block in the non real-time mode. The above tailoring of thread information is on a task basis and, therefore, each task in the system can choose its own mode depending on its needs. Typically real-time tasks choose the real-time mode for an improved worst case execution time whereas non time critical tasks choose the non real-time mode for an improved average case execution time. This paper shows, through analysis using a timing tool, that the proposed scheme significantly (up to 45%) improves the predicted worst case execution time in the real-time mode as compared with no prefetching scheme.>

A timing tool has been implemented for a subset of C as an initial experiment in validating a methodology for predicting the deterministic execution times of programs. The tool is based on formal timing schema that are defined for each source level construct (procedures, statements, expressions). The tool accepts a program and bounds for each loop, and produces predictions for best and worst case execution times. Two versions of the tool were written, using two extremes of granularity for the atomic elements of the timing schema. Within the constraints of the target architecture and compiler, measured execution times for a variety of simple constructs and programs agree with times predicted by the tool. The implementation decomposes naturally into a system-independent part, which is believed to be determined by the 'timing semantics' of the language, and a lower-level system-dependent portion. The experiments validate the general timing schema approach but also point out a number of problems and possible refinements.>