Application loading times can be reduced by prefetching disk blocks into the buffer cache. Existing prefetching schemes for general workloads suffer from significant overheads and low accuracy. ClusterFetch is a lightweight prefetcher that identifies continuous sequences of I/O requests and identifies the files that trigger them. The next time that the same files are opened, the corresponding disk blocks are prefetched. In experiments, ClusterFetch reduced the launch time, by which we refer to the latency that first occurs when a program runs, by 15.2 to 30.9%, and loading times, meaning the delays that are incurred while additional data is loaded from the disk during program execution, by 15.9%.

Application launch time is an important performance metric to user experience in desktop environment. The launch time mostly depends on the performance of secondary storage. There is a cost-performance trade-off in using hard disk drive (HDD) or solid-state drive (SSD). Thus, application launch times can be reduced by utilizing SSDs as caches for slow HDDs. We propose a new SSD caching scheme which migrates data blocks from HDDs to SSDs. Since our scheme operates entirely in the file system level and does not require an extra layer for mapping SSD-cached data, which is essential in most other schemes, our scheme does not incur mapping overheads that cause significant burdens on main memory, CPU, and SSD cache itself. Experimental results demonstrate our scheme yields 56% of performance gain in application launch.

Active storage devices further improve their performance by executing “intelligence functions,” such as prefetching and data deduplication, in addition to handling the usual I/O requests they receive. Significant research has been carried out to develop effective intelligence functions for the active storage devices. However, laborious and time-consuming efforts are usually required to set up a suitable experimental platform to evaluate each new intelligence function. Moreover, it is difficult to make such prototypes available to other researchers and users to gain valuable experience and feedback. To overcome these difficulties, we propose$\tt {IOLab}$, a virtual machine (VM)-based platform for evaluating intelligence functions of active storage devices. The VM-based structure of$\tt {IOLab}$enables the evaluation of new (and existing) intelligence functions for different types of OSes and active storage devices with little additional effort.$\tt {IOLab}$also supports real-time execution of intelligence functions, providing users opportunities to experience latest intelligence functions without waiting for their deployment in commercial products. Using a set of interesting case studies, we demonstrate the utility of$\tt {IOLab}$with negligible performance overhead except for the VM’s virtualization overhead.

Quality of service (QoS), and in particular reliability and low latency, are essential qualities of safety-critical wireless systems for medical applications. However, wireless links are typically prone to bursts of errors, with characteristics which vary over time. We propose a wireless system suitable for real-time remote patient monitoring in which both the necessary reliability and a bounded end-to-end delay are achieved by an efficient error control scheme. We have paired an example electrocardiography (ECG) application to this wireless system. We also developed a tool chain to assess various combinations of system parameters: we can determine the QoS in terms of the packet-delivery ratio and the end-to-end latency, and also the size of jitter buffer required for seamless ECG monitoring services. A realistic assessment, based on data from the MIT-BIT arrhythmia database, shows that the proposed wireless system can achieve an appropriate level of QoS for real-time ECG monitoring if link-level error control is appropriately implemented.

This paper proposes a reliable wildfire monitoring system based on a wireless sensor network (WSN) sparsely deployed in adverse conditions. The physical environment under consideration is characterized by asymmetric, irregular, and unreliable wireless links, inadequate Fresnel zone clearance, and routing problems, to name a few. We use reliable communication schemes on a fault-tolerant network topology, where sensory data are guaranteed to reach the base station with organized data storage and real-time visualization. Our approach has been validated experimentally for the case of peat-forest wildfire in southern Borneo where the fire breaks out frequently.

Recent standardization efforts in the 3rd Generation Partnership Project (3GPP) have made the Long Term Evolution (LTE) system a very attractive radio access technology for various types of devices and applications. However, the system has not yet been optimized to support diverse traffic profiles. In this paper, we propose a group-based communication scheme to alleviate inefficiencies in the radio access network. The proposed scheme groups multiple connections triggered by different User Equipments (UEs). For the efficient grouping of the UEs, the location information of the Machine-Type Communication (MTC) devices is utilized to identify each group. A four-phase system model is presented to analyze each segment of the connection establishment procedure in the access network. We found that the random access procedure is the main variable factor for the communication delay, and we, therefore, carefully design the procedure with details. Simulations are conducted on our LTE testbeds, and the results show that the proposed scheme is very effective in ensuring the system performance of legacy services and in utilizing radio resources within a given delay bound.

In this paper, we propose parallelization and optimization techniques of the H.264 decoder for the Cell BE processor. We exploit both frame-level parallelism and macroblock pipelining. The major bottleneck in achieving the real-time performance is the entropy decoding stage, CABAC. Our decoder eliminates this bottleneck by exploiting the frame-level parallelism available in the entropy decoding stage. A macroblock software cache and a prefetching technique for the cache are used to facilitate macroblock pipelining. In addition, an asynchronous macroblock buffering technique is used to eliminate the effect of load imbalance between pipeline stages. We evaluate the effectiveness of our approach by implementing a parallel H.264 decoder on an IBM Cell blade server. The evaluation results indicate that our parallel H.264 decoder (with CABAC entropy decoding) on a single Cell BE processor meets the real-time requirement of the full HD standard at level 4.0. Moreover, our decoder also satisfies the real-time requirement at level 4.1 when an additional Cell BE processor is used.

Wireless video sensor networks (WVSNs) require video data from sensor nodes to be delivered efficiently. Cameras in adjacent video nodes tend to have correlated fields of view (FoVs) or overlapping part when a sufficient number of video sensors are deployed. This paper proposes a data aggregation technique for WVSNs to remove the spatial redundancy, thereby reducing energy consumption and response time. Our approach exploits the correlation between discrete cosine transform (DCT) coefficients pairs of two intra-coded images from cameras with overlapping FoVs. Experiments show that an intermediate node en route to the base station achieves bit-rate savings up to 18.9%. This scheme is less complicated than other video and image coding techniques that exploit correlated FoV, allowing resource-constrained video sensors to operate more reliably and longer.

We propose a code scratchpad memory (SPM) management technique with demand paging for embedded systems that have no memory management unit. Based on profiling information, a postpass optimizer analyzes and optimizes application binaries in a fully automated process. It classifies the code of the application including libraries into three classes based on a mixed integer linear programming formulation: External code is executed directly from the external memory. Pinned code is loaded into the SPM when the application starts and stays in the SPM. Paged code is loaded into/unloaded from the SPM on demand. We evaluate the proposed technique by running 14 embedded applications both on a cycle-accurate ARM processor simulator and an ARM1136JF-S core. On the simulator, the reference case, a four-way set-associative cache, is compared to a direct-mapped cache and an SPM of comparable die area. On average, we observe an improvement of 12 percent in runtime performance and a 21 percent reduction in energy consumption. On the ARM11 board, the reference case run on the 16-KB four-way set-associative cache is compared to the demand paging solution on the 16-KB SPM, optionally supported by the cache. The measured results show both a runtime performance improvement and a reduction of the energy consumption by 23 percent, on average.

There have been various broadcast schemes based either on mobile users' data access frequencies or on the semantic relations of data.In this paper, we present a data broadcast scheme based both on the semantic relationship and the access probabilities. The broadcast scheme we propose generates a broadcast sequence according to the semantic relationship and replicates popular data items several times according to the data access probabilities. We show our broadcast scheme is efficient through performance evaluations.

This paper presents a dynamic scratchpad memory (SPM) code allocation technique for embedded systems running an operating system with preemptive multitasking. Existing SPM allocation schemes do not support multiple tasks or only a fixed number of processes that are known at compile time. These schemes rely on algorithms that select code depending on the size of the SPM. In contemporary portable devices, however, processes are created and terminated on demand and the SPM is shared among them. We introduce a dynamic scratchpad memory code alloca-tion technique for code that supports dynamically created processes. At runtime, an SPM manager (SPMM) loads code pages of the running applications into the SPM on de-mand. It supports different sharing strategies that deter-mine how the SPM is distributed among the running pro-cesses. We analyze several sharing strategies with regard to several preferable properties of multiprocess SPM allocation schemes. We evaluate the proposed multiprocess SPM allocation techniques and compare them to a fully-cached reference system by running several multiprocess benchmarks. The benchmarks comprise of multiple embedded applications such as H.264, MP3, MPEG-4, and PGP. On average, we achieve a 47 % improvement in throughput and a 32 % re-duction in energy consumption. A comparison with the un-achievable lower bound shows that the best SPM sharing strategy exploits 87 % of the runtime improvements and 89% of the energy savings possible.

We propose a luminance scalable video coding scheme (LSC) that uses the scalable video coding (SVC) extension of H.264/AVC to reduce the power consumption of mobile devices. The insufficient battery life of mobile hand-held devices is the main obstacle for mobile video applications. In particular, liquid crystal displays consume a large portion of the system power. Building on previous power reduction schemes, such as dynamic backlight luminance scaling, we exploit SVC which is used to adapt a video stream to the preferences of users, different mobile capabilities, and varying network conditions. Our video coding scheme can reduce the power consumed by an LCD display by more than 20%, even though it has a lower overhead than previous schemes and does not require any modification of the decoders.

In this work, we present a dynamic memory allocation technique for a novel, horizontally partitioned memory subsystem targeting contemporary embedded processors with a memory management unit (MMU). We propose to replace the on-chip instruction cache with a scratchpad memory (SPM) and a small minicache. Serializing the address translation with the actual memory access enables the memory system to access either only the SPM or the minicache. Independent of the SPM size and based solely on profiling information, a postpass optimizer classifies the code of an application binary into a pageable and a cacheable code region. The latter is placed at a fixed location in the external memory and cached by the minicache. The former, the pageable code region, is copied on demand to the SPM before execution. Both the pageable code region and the SPM are logically divided into pages the size of an MMU memory page. Using the MMU's pagefault exception mechanism, a runtime scratchpad memory manager (SPMM) tracks page accesses and copies frequently executed code pages to the SPM before they get executed. In order to minimize the number of page transfers from the external memory to the SPM, good code placement techniques become more important with increasing sizes of the MMU pages. We discuss code-grouping techniques and provide an analysis of the effect of the MMU's page size on execution time, energy consumption, and external memory accesses. We show that by using the data cache as a victim buffer for the SPM, significant energy savings are possible. We evaluate our SPM allocation strategy with fifteen applications, including H.264, MP3, MPEG-4, and PGP. The proposed memory system requires 8% less die are compared to a fully-cached configuration. On average, we achieve a 31% improvement in runtime performance and a 35% reduction in energy consumption with an MMU page size of 256 bytes.

The requirement of agile adaptation to varying resource constraints in mobile systems motivates the use of a service-oriented architecture (SOA), which can support the composition of two or more services to form a complex service. In this paper, we propose SOA-based middleware to support QoS control of mobile applications and to configure an energy-efficient service composition graph. We categorize services into two layers: functionality-centric services, which are connected to create a complex service to meet the user's intentions, and resource-centric services, which undertake distributed functionality-centric services in a way that increases the success rate of service composition while reducing contention at specific service nodes. We also present a service routing algorithm to balance the resource consumption of service providers on a service-overlay network. Through simulation of power-aware service composition using a realistic model based on ns-2 and traced data, we demonstrate that our approach can help both the mobile devices and the servers in a service-overlay network to reduce energy consumption without an increase in response time.

In CDMA2000 1xEV-DO broadcast and multicast services (BCMCS), Reed-Solomon (RS) coding is applied to the layers above the turbo code, which is effective in correcting long bursts of errors when an additional block interleaving mechanism is used to increase the time diversity. This is controlled by changing the width of the error control block (ECB), which converts error bursts into random patterns. We propose and evaluate an energy model of the RS decoding process under varying conditions of Rayleigh fading on the broadcast channel, with different levels of block interleaving within those permitted by the BCMCS specification. Simulation results show that our model accurately predicts the energy consumption of the RS decoding process, and is thus able to contribute to the development of energy-efficient broadcast services.

Recent advances in communication and mobile computing have made it possible for cellular networks and digital broadcasting systems to converge on the basis of their common multimedia applications. We analyze the real-time characteristics of a cdma2000 1xEV-DO broadcast and multicast service (BCMCS) system, and propose a system architecture to provide seamless multimedia services. We found that jitter in the processing time of the Reed-Solomon decoder can lead to a discontinuity in multimedia streaming, and we therefore estimated the Reed-Solomon decoding time on a common mobile platform for a given bit error-rate or fading margin in the channel. Next we evaluated the jitter bound and the best cache size for real-time applications in BCMCS. This analysis allows us to suggest a system architecture based on the jitter-EDD model to ensure the continuity of real-time services for multimedia applications over a 3G cellular broadcast network, and to provide a better quality of service.

1xEV-DO is the first wireless standard to support the delivery of broadcast and multicast services (BCMCS). Complementing unicast, which sends content to subscribers individually (e.g. video-on-demand), BCMCS transmits multimedia content from a single source to multiple users simultaneously. In BCMCS, Reed-Solomon coding is applied to the layers above the turbo code, and is particularly effective in correcting long bursts of errors. An additional block interleaving mechanism improves the performance of RS coding by converting the error bursts into a random pattern by increasing the width of the error control block (ECB) to increase the time diversity. We propose and evaluate a performance model of RS coding for varying conditions of Rayleigh fading on the broadcast channel with the maximum amount of block interleaving that the BCMCS specification allows. The fitness of the proposed performance model is verified by comparing the results from the analytic model with a simulation. Our evaluation will allow a service provider to exploit the most efficient RS code for their target service quality.

In this paper, we propose a dynamic scratchpad memory (SPM)management technique for a horizontally-partitioned memory subsystem with an MMU. The memory subsystem consists of a relatively cheap direct-mapped data cache and SPM. Our technique loads required global data and stack pages into the SPM on demand when a function is called. A scratchpad memory managerloads/unloads the data pages and maintains a page table for the MMU. Our approach is based on post-pass analysis and optimization techniques, and it handles the whole program including libraries. The data page mapping is determined by solving an integer linear programming (ILP) formulation that approximates our demand paging technique. The ILP model uses a dynamic call graph annotated with the number of memory accesses and/or cache misses obtained by profiling. We evaluate our technique on thirteen embedded applications. We compare the results to a reference system with a 4-way set associative data cache and the ideal case with the same 4-way cache and SPM, where all global and stack data is placed in the SPM. On average, our approach reduces the total system energy consumption by 8.1% with no performance degradation. This is equivalent to exploiting 60% of the room available in energy reduction between the reference case and the ideal case.

Abstract The error‐prone nature of the radio channel is the major challenge in servicing video streams over cdma2000 broadcast networks. The MAC protocol for broadcast and multicast services (BCMCS) in cdma2000 specifies forward error correction using Reed–Solomon coding, which is effective in recovering from bursts of errors. However, its performance degrades significantly when channel conditions are bad, a frequent occurrence at the edge of the coverage area, reducing the availability of high‐speed broadcasts. We propose an error recovery scheme and a scheduling algorithm based on the use of slots saved by changing to a Reed–Solomon code with a lower parity overhead. Within the fixed transmission budget thus created, corrupted packets are retransmitted in a priority order determined by a utility function that is derived from the map of the error control block at each mobile, and which also considers the number of mobiles that did not receive each lost packet. Simulation results show the effectiveness of the proposed scheme in improving the quality of high‐data‐rate MPEG‐4 video streams over a range of channel conditions. Copyright © 2007 John Wiley & Sons, Ltd.

Multimedia services over a CDMA2000 broadcast network face a challenge from the unreliable and error-prone nature of the radio channel. Reed–Solomon (RS) coding, integrated with the MAC protocol, is used to cope with this problem. However, performance analysis of RS coding under varying channel conditions shows that it is not always effective, especially for slow-moving nodes which experience relatively long error bursts. Therefore a more efficient scheme is proposed that uses a RS code with reduced parity overhead, and freeing bandwidth can be used flexibly for retransmission. The packets to be retransmitted are prioritised by a utility function derived from the map of the error control block at each mobile node and the number of mobile nodes that require the lost packet. Simulation results show that the gain of retransmission exceeds the loss incurred by reducing the parity, leading to an improvement in the playback quality of MPEG-4 video streams. As a result, service area for high-quality multimedia can be expanded.

The error-prone nature of the radio channel is the major challenge in servicing video streams over cdma2000 1/spl times/EV-DO broadcast networks. Forward error correction is commonly used when broadcasting a video stream over a lossy network: in BCMCS, the MAC protocol uses Reed-Solomon coding. We analyze the performance of Reed-Solomon error recovery with various parameter settings, and prove the correctness of our analysis through experiment. We also propose a hybrid-ARQ scheme to improve error recovery capacity in the BCMCS environment. Simulation results show a significant reduction in packet loss while quantitatively validating our approach.

We analyze the execution time of MAC-layer Reed-Solomon decoding in cdma2000 1xEV-DO broadcast and multicast services (BCMCS), using different cache sizes and a simulated air channel. MPEG-4 video is widely used for wireless multimedia services; however, it requires successive frames within a specific time interval, which can be missed by a MAC-layer Reed-Solomon decoder due to its computation time. We propose static and dynamic proactive Reed-Solomon bypass (PRSB) schemes to alleviate this problem in mobile nodes. Our first scheme bypasses the Reed-Solomon decoding process to satisfy the MPEG-4 time constraint statically, despite varying channel conditions. The second, dynamic scheme corrects errors in a best-effort manner within this same time constraint, leading to a further quality improvement. Extensive simulation results show a dramatic quality improvement in video quality

In this paper,we present a dynamic scratchpad memory allocation strategy targeting a horizontally partitioned memory subsystem for contemporary embedded processors. The memory subsystem is equipped with a memory management unit (MMU), and physically addressed scratchpad memory (SPM)is mapped into the virtual address space. A small minicache is added to further reduce energy consumption and improve performance.Using the MMU's page fault exception mechanism, we track page accesses and copy frequently executed code sections into the SPM before they are executed. Because the minimal transfer unit between the external memory and the SPM is a single memory page, good code placement is of great importance for the success of our method. Based on profiling information, our postpass optimizer divides the application binary into pageable, cacheable, and uncacheable regions. The latter two are placed at fixed locations in the external memory, and only pageable code is copied on demand to the SPM from the external memory. Pageable code is grouped into sections whose sizes are equal to the physical page size of the MMU. We discuss code grouping techniques and also analyze the effect of the minicache on execution time and energy consumption. We evaluate our SPM allocation strategy with twelve embedded applications, including MPEG-4. Compared to a fully-cached configuration, on average we achieve a 12% improvement in runtime performance and a 33% reduction in energy consumption by the memory system.

We analyze the performance of MAC-layer Reed-Solomon error recovery in the CDMA2000 1xEV-DO broadcast and multicast services (BCMCS) environment, with respect to the size of the error control block (ECB) and the air-channel condition, and establish the relationship between ECB size, error-recovery capacity and energy consumption. Real-time traffic, such as voice and video streaming, is very sensitive to delay, but can stand a certain level of packet loss. We therefore propose an energy-efficient size of the ECB to reduce the average energy consumption during error recovery while minimizing the reduction in service quality for real-time multimedia applications. Extensive simulation results suggest that a significant amount of energy can be saved with negligible performance degradation by selecting the appropriate ECB size for the bit error-rate of the forward traffic channel, instead of always choosing the largest possible ECB, with the sole aim of increasing error recovery performance

3GPP2 has recently introduced the Broadcast and Multicast Services (BCMCS) architecture for cdma2000 lxEV-DO wireless networks to enable service providers to broadcast multimedia content such as MPEG-4 video. For MAC-layer forward error correction the BCMCS scheme uses the Reed-Solomon (RS) decoding process, which consumes a considerable amount of energy on mobile phones. To address this problem, we first characterize the energy consumption of the decoder with respect to its components: the data decoder, error locator and erasure decoder. Based on this detailed energy characterization we propose an analytic energy model which takes account of different levels of bit error rate in the forward traffic channel. This model is then verified experimentally on an ARM microprocessor-based testbed. Our results will help design energy-efficient BCMCS systems for 3G cellular networks

We analyze the execution time of MAC-layer Reed-Solomon error recovery in cdma2000 1xEV-DO broadcast and multicast services (BCMCS), with respect to cache size and air channel condition. We observe that a deteriorating channel condition often causes an intolerable delay for real-time tasks because of the error recovery process, even when sufficient cache memory is available to increase CPU throughput. To overcome this problem, we propose proactive Reed-Solomon bypass (PRSB), which determines whether the Reed-Solomon scheme should be used to correct errors in the real-time communication environment. The proposed scheme utilizes the cache effectively, thus preventing reset of the entire decoding process and allowing real-time multimedia applications to meet their deadline constraints. Simulation results show that the PRSB greatly improves the overall playback quality of a video.

cdma2000 1/spl times/EV-DO, one of the prominent 3G mobile communication systems, provides broadcast and multicast services (BCMCS) to meet increasing demand for multimedia data services. Currently, 1/spl times/EV-DO schedules broadcast streams using a slot-based static algorithm, which fails to support dynamic environments where broadcast content is added or removed on-line. We propose a dynamic packet-scheduling algorithm that works with a retransmission scheme for the BCMCS scheduler. Integrated with earliest deadline first (EDF) real-time scheduling, the proposed algorithm not only adapts to dynamic contexts efficiently but also satisfies the real-time requirements of broadcast streams. Furthermore, by exploiting the fine granular scalable (FGS) characteristics of the MPEG-4 part 2 standard, our scheme can avoid abrupt degradation of playback quality by protecting the most important data. Extensive simulations have quantitatively validated the efficiency of our approach.

Video broadcast services have become increasingly popular on packet-based wireless networks, such as 1xEV-DO and HSDPA which support high data rate. In this paper we propose a resource allocation algorithm for scalable video broadcast over such wireless networks. Our algorithm allocates time slots among the video layers of a scalable video and applies adaptive modulation and coding (AMC) to each video layer to maximize the sum of utilities for heterogeneous users with varying QoS requirements. It also considers competing video sessions and allocates time slots among them according to user preferences. Additionally, its polynomial time-complexity allows for online resource allocation that is necessary for real-time video services. Simulation experiments show that our algorithm outperforms a single-layer video broadcast with fixed modulation and coding (FMC), used in broadcast and multicast services (BCMCS) in the CDMA2000 system, and produce a near-optimal allocation.

As embedded systems grow in size and complexity, an operating system has become essential to simplify the design of system software, for which more accurate analysis of its impact on memory performance is required. In this paper, we intend to investigate how the OS influences memory performance at run time by quantitatively evaluating the memory system behavior of an MPEG-4 application running on embedded Linux. Through the use of extensive simulations we have confirmed that the OS has poor memory performance with less memory locality than applications. The results of our experimental analysis are deemed useful for helping embedded system designers understand the memory performance of the OS and the application within a system, extending their capability to design a more power-aware and faster system.

In this paper we propose storage allocation schemes to minimize the buffer requirements for fault-tolerant video-on-demand (VOD) servers with disk arrays. To guarantee the high reliability of video service, the servers usually adopt parity-encoding techniques in which data blocks and their associated parity block form a parity group. For real-time video service, all the blocks in a parity group are prefetched to cope with disk failure. Buffer overhead incurred by a prefetch can be reduced by decreasing the parity group size, which demands more storage space for parity blocks. Our proposed scheme called round-level parity grouping (RPG) aims at restoring VBR video streams efficiently. Based on RPG we have developed a heuristic algorithm working towards effective buffer management. The experimental results show that our proposed schemes produce near-optimal buffer requirements.

The Java platform provides a fully fledged programming environment for graphics applications using the Abstract Window Toolkit (AWT). We present a power-aware basis profile of the Java 2 Micro Edition (J2ME) for embedded applications. The Low-Power Basis Profile (LPBP) is responsive to backlight luminance scaling in such a way that dynamic adjustment of the backlight luminance is accompanied by adaptive image compensation. The proposed scheme performs aggressive backlight dimming while maintaining the readability of screen contents based on image compensation techniques such as brightness compensation, image enhancement and context processing. Experiments show that on average the LPBP can easily achieve approximately 30% backlight system power reduction.

The paper addresses the problem of scheduling periodic messages in demand priority network standardized by IEEE 802.12 Committee. As regards the real time property of the demand priority network, unnecessary blocking time due to its round robin based MAC protocol may cause periodic messages to miss their hard deadlines and result in low schedulability of periodic messages. We propose a new message scheduling algorithm to enforce a priority based preemptive message transmission on the frame basis. Before a node transmits a periodic message, it broadcasts the priority of message for all nodes to construct a network wide ready queue in order of priority. A node can transmit a periodic message only when its message is at the head of the ready queue. We have derived sufficient and necessary conditions for both static and dynamic priority assignment in order to determine the schedulability of periodic messages. The simulation study shows that the proposed algorithm significantly improves the guarantee ratio of periodic messages.

We describe our experiments on a real-time system design, focusing on design alternatives such as scheduling jitter, sensor-to-output latency, intertask communication schemes and the system utilization. The prime objective of these experiments was to evaluate a real-time design produced using the period calibration method (Gerber et al., 1995) and thus identify the limitations of the method. We chose a computerized numerical control (CNC) machine as our target real-time system and built a realistic controller and a plant simulator. Our results were extracted from a controlled series of more than a hundred test controllers obtained by varying four test variables. This study unveils many interesting facts: average sensor-to-output latency is one of the most dominating factors in determining control quality; the effect of scheduling jitter appears only when the average sensor-to-output latency is sufficiently small; and loop processing periods are another dominating factor of performance. Based on these results, we propose a new communication scheme and a new objective function for the period calibration method.

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 memory called the Boolean Content Addressable Memory integrates the content-based address identification logic into the RAM comprising 1-bit words. This memory is suitable for on-chip VLSI implementation and compatible with the RAM for on-board implementation. Its application includes list management and graph traversal.