Efficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full, In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O(log(2) n) (the time complexity of LFU), where n is the number of blocks in the buffer, Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered.

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.

AbstractÐEfficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full. In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O…log 2 n† (the time complexity of LFU), where n is the number of blocks in the buffer. Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered. Index TermsÐBuffer cache, LFU, LRU, replacement policy, trace-driven simulation. 1

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.

Write requests are written from the disk cache to the disks by the destage algorithm, and the response time of host read request dominates the performance of the disk. Since RAID is composed of multiple disks, although the performance at the disk level is important to service requests, effectively the performance at the disk array level is more important. In RAID, a host request cannot be completed until all the striped requests are completed and the response time of the host request is dependent on the response time of the disk with the heaviest load. However, existing destage algorithms do not take into consideration the overall performance of all disks in the RAID but destage write requests for optimal performance at each individual disk, and it may eventually lead to overload of a few disks. It may delay the service of some striped requests, and therefore, the response time of host request increases. The paper suggests a novel Load-Balanced Destage (LBD) algorithm adopted at the disk array level, and shows that the LBD algorithm has a higher performance than existing destage algorithms by evaluating their performance using a simulator.

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 proposes a cost-effective solution to the synonym problem. In this proposed solution, a minimal hardware addition guarantees the correctness whereas the software counterpart helps improve the performance. The key to this proposed solution is an addition of a small physically-indexed cache called U-cache. The U-cache maintains the reverse translation information of the cache blocks that belong to un-aligned virtual pages only, where aligned means that the lower bits of the virtual page number match those of the corresponding physical page number. A U-cache, even with only one entry, ensures correct handling of synonyms. A simple software optimization in the form of page alignment, helps improve the performance. Performance evaluation based on ATUM traces shows that a U-cache, with only a few entries, performs almost as well as (in some cases outperforms) a fully-configured hardware-based solution when more than 95% of the pages are aligned.>

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 ensemble of neural networks with competitive learning and consensus schemes is proposed. Conventional learning methods utilize all the dimensions of the original input patterns. However, a particular attribute of the input patterns does not necessarily contribute to classification. In this paper, we use the reduced input dimension for learning a neural network. We have developed three consensus schemes so as to judge the classification using multiple neural networks. The experimental results with remote sensing data indicate the improved performance of the networks when applying the proposed method to the conventional competitive learning algorithms.>

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.>