The hybrid memory architecture that contains both on-chip cache and scratchpad memory (SPM) has been widely used in embedded systems. In this article, we explore this hybrid memory architecture by jointly optimizing time performance and temperature for embedded systems with loops. Our basic idea is to adaptively adjust the workload distribution between cache and SPM based on the current temperature. For a problem in which the workload can be estimated a priori, we present a nonlinear programming formulation to optimally minimize the total execution time of a loop under the constraints of SPM size and temperature. To solve a problem in which the workload is not known a priori, we propose a temperature-aware adaptive loop scheduling algorithm called TALS to dynamically allocate data to cache and SPM at runtime. The experimental results show that our algorithms can effectively achieve both performance and temperature optimization for embedded systems with cache and SPM.

SUMMARY Memory accesses introduce big‐time overhead and power consumption because of the performance gap between processors and main memory. This paper describes and evaluates a technique, loop scheduling with memory access reduction (LSMAR), that replaces hidden redundant load operations with register operations in loop kernels and performs partial scheduling for newly generated register operations subject to register constraints. By exploiting data dependence of memory access operations, the LSMAR technique can effectively reduce the number of memory accesses of loop kernels, thereby improving timing performance. The technique has been implemented into the Trimaran compiler and evaluated using a set of benchmarks from DSPstone and MiBench on the cycle‐accurate simulator of the Trimaran infrastructure. The experimental results show that when the LSMAR technique is applied, the number of memory accesses can be reduced by 18.47% on average over the benchmarks when it is not applied. The measurements also indicate that the optimizations only lead to an average 1.41% increase in code size. With such small code size expansion, the technique is more suitable for embedded systems compared with prior work.Copyright © 2013 John Wiley & Sons, Ltd.

In this paper, we propose to implement hybrid operating systems based on two-level hardware interrupts. We analyze and model the worst-case real-time interrupt latency for RTAI and identify the key component for its optimization. Then, we propose our methodology to implement hybrid operating systems with two-level hardware interrupts by combining the real-time kernel and the time sharing OS (Operating System) kernel. Based on the methodology, we discuss the important issues for the implementation. Finally, we implement a hybrid system called RTLinux-THIN (Real-Time LINUX with Two-level Hardware INterrupts) on the ARM architecture by combining ARM Linux kernel 2.6.9 and μC/OS-II. We conduct experiments on a set of real application programs including mplayer, Bonnie, and iperf, and compare the interrupt latency and interrupt task distributions for RTLinux-THIN (with and without cache locking), RTAI, Linux, and Linux with RT patch on a hardware platform based on Intel PXA270 processor. The results show that our scheme not only provides an easy method for implementing hybrid systems but also achieves the performance improvement for both the time sharing and real-time subsystems.

In this paper, we propose a hybrid-level flash translation layer (FTL) called RNFTL (Reuse-Aware NFTL) to improve the endurance and space utilization of NAND flash memory. Our basic idea is to prevent a primary block with many free pages from being erased in a merge operation. The preserved primary blocks are further reused as replacement blocks. In such a way, the space utilization and the number of erase counts for each block in NAND flash can be enhanced. To the best of our knowledge, this is the first work to employ a reuse-aware strategy in FTL for improving the space utilization and endurance of NAND flash. We conduct experiments on a set of traces that collected from real workload in daily life. The experimental results show that our technique has significant improvement on space utilization, block lifetime and wear-leveling compared with the previous work.

In this paper, we jointly optimize computation and communication task scheduling for streaming applications on MPSoC. The objective is to minimize schedule length by totally removing inter-core communication overhead. By minimizing schedule length, the system performance can be improved by adopting a smaller period or exploring the slacks generated for energy reduction with DVS. To guarantee the schedulability of communication tasks, we perform the schedulability analysis, and theoretically obtain the upper bound of the times needed to reschedule each computation task. Based on the analysis, we formulate the scheduling problem as an ILP (Integer Linear Programming) formulation and obtain an optimal solution. We evaluate our technique with a set of benchmarks from both real-life streaming applications and synthetic task graphs. The simulation results show that our technique can achieve a 27.72% reduction in schedule length and a 13.38% reduction in energy consumption on average compared with the previous work.

Abstract In this paper, we propose an effective data pipelining technique, SPDP (Scratch‐Pad Data Pipelining), for dynamic scratch‐pad memory (SPM) management with DMA (Direct Memory Access). Our basic idea is to overlap the execution of CPU instructions and DMA operations. In SPDP, based on the iteration access patterns of arrays, we group multiple iterations into a block to improve the data locality of regular array accesses. We allocate the data of multiple iterations into different portions of the SPM. In this way, when the CPU executes instructions and accesses data from one portion of the SPM, DMA operations can be performed to transfer data between the off‐chip memory and another portion of SPM simultaneously. We perform code transformation to insert DMA instructions to achieve the data pipelining. We have implemented our SPDP technique with the IMPACT compiler, and conduct experiments using a set of loop kernels from DSPstone, Mibench, and Mediabench on the cycle‐accurate VLIW simulator of Trimaran. The experimental results show that our technique achieves performance improvement compared with the previous work. Copyright © 2010 John Wiley & Sons, Ltd.

This paper solves the open problem of extracting the maximal number of iterations from a loop that can be executed in parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum non-zero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative non-optimal algorithms using a set of benchmarks frequently used in prior work.

In this paper, we develop a compiler-assisted thermal-aware data allocation algorithm to improve the reliability of embedded systems with cache and SPM (scratch-pad memory). Our basic idea is to distribute the workload evenly between the cache and SPM in order to alleviate the temperature hot spots in the on-chip memory system. In the algorithm, considering the size of SPM, we first divide the loop iterations into two parts, and put the accessed data of the first part into SPM. Then we perform code transformation based on the partitioning of iterations. By alternatively using the data cache and SPM, the peak temperature is reduced. We implement our technique and simulate them using the Trimaran infrastructure with power models for cache and SPM, and the thermal simulator, HotSpot, on a set of benchmarks from DSPstone and MiBench. The experimental results show that our technique can significantly improve the reliability of the on-chip memory system.

In this paper, we focus on joint energy and performance optimization for streaming applications on multiprocessor systems-on-chip by combining task-level coarse-grained software pipelining with DVS (dynamic voltage scaling)and DPM (dynamic power management) techniques with the considerations of transition overhead, inter-processor communication and discrete voltage levels. We propose a two-phase approach to solve the problem. In the first phase, we propose a coarse-grained task parallelization algorithm called RDAG to transform a periodic dependent task graph into a set of independent tasks based on the retiming technique[19]. In the second phase, we propose a novel scheduling algorithm called SpringS that works like a spring by iteratively adjusting task scheduling and voltage selection by combining DVS and DPM. We conduct experiments with a set of benchmarks from E3S [10] and TGFF [27]. The experimental results show that our technique can achieve 49:8% energy saving on average compared with the approach in [20], that applied DVS and DPM without software pipelining. In addition, given a tight timing constraint, our technique can obtain a feasible solution while the approach in [20] cannot.

As MOSFETs (metal-oxide-semiconductor field effect transistor) dimensions enter the sub-micrometer region, reducing leakage power becomes a significant issue of VLSI industry. In this paper, we propose a novel prediction approach to predict idleness of functional units for leakage energy management. Using a state-based predictor, historical utilization information of functional units is exploited to adjust the state of the predictor so as to enhance the accuracy of prediction. We implement our approach based on SimpleScalar and conduct experiments with a suite of fourteen benchmarks from Trimaran. The experimental results show that our approach achieves the better results compared with the previous work.

As a distributed computing system, a CNC system needs to be operated reliably, dependably and safely. How to design reliable and dependable software and perform effective verification for CNC systems becomes an important research problem. In this paper, we propose a new modeling method called TTM/ATRTTL (Timed Transition Models/All-Time Real-Time Temporal Logics) for specifying CNCsystems. TTM/ATRTTL provides full supports for specifying hard real-time and feedback that are needed for modeling CNC systems. We also propose a verification framework with verification rules and theorems and implement it with STeP and SF2STeP. The proposed verification framework can check reliability, dependability and safety of systems specified by our TTM/ATRTTL method. We apply our modeling and verification techniques on an open architecture CNC (OAC) system and conduct comprehensive studies on modeling and verifying a logical controller that is the key part of OAC. The results show that our method can effectively model and verify CNC systems and generate CNC software that can satisfy system requirements in reliability, dependability and safety.

In networked embedded sensor systems, data fusion is a viable solution to significantly reduce energy consumption while achieving real-time guarantee. Emerging data fusion applications demand efficient task allocation and scheduling techniques. However, existing approaches can not be effectively applied concerning both network topology and wireless communications. In this paper, we formally model TATAS, the topology-aware task allocation and scheduling problem for real-time data fusion applications, and show it is NP-complete. We also propose an efficient three-phase heuristic to solve the TATAS problem. We implement our technique and conduct experiments based on a simulation environment. Experimental results show that, as compared with traditional approaches, our technique can achieve significant energy saving and effectively meet the real-time requirements as well.

In this paper, we develop a novel real-time instruction-level loop scheduling technique to reduce leakage energy consumption for applications with loops on VLIW architecture. We first prove that the scheduling problem with the minimum leakage energy consumption within a timing constraint is NP-complete. Then, LEMLS (leakage energy minimization loop scheduling) algorithm is designed to repeatedly regroup a loop based on rotation scheduling (Chao et al., 1997), and decrease leakage energy integrating with leakage power reduction mechanism. We conduct experiments on a set of DSP benchmarks based on the power model of the VLIW processors in (Liao et al., 2002). The results show that our algorithm achieves significant leakage energy saving compared with list scheduling and the algorithm in (You et al., 2006).

In this paper, we propose to implement hybrid operating systems based on two-level hardware interrupts. To separate real-time and non-real-time hardware interrupts by hardware, we show that it is easier to build up hybrid systems with better performance. We analyze and discuss the key issues for implementing a hybrid system based on this and implement a hybrid system called RTLinux-THIN (Real-Time LINUX with Two-level Hardware Interrupts) on the ARM architecture by combining ARM Linux kernel 2.6.9 and muC/OS-II. We conduct experiments on a set of real application programs including mplayer [20], Bonnie [4] and iperf [13] and compare the interrupt latency distributions for RTLinux-THIN (with and without cache locking), RTAI and Linux on a hardware platform based on Intel PXA270processor [12]. The experimental results show that RTLinux-THIN improves real-time interrupt latencies and provides better predictability.

The paper proposes a fast map learning approach for real-time map building and active exploration in unknown indoor environments. This approach includes a map model, a map update method, an exploration method, and a map postprocessing method. The map adopts a grid-based representation and uses frequency value to measure the confidence that a cell is occupied by an obstacle. The exploration method is implemented by coordinating two novel behaviors: path-exploring behavior and environment-detection behavior. Fuzzy logic is used to implement the behavior design and coordination. The fast map update and path planning (i.e. the exploration method) make our approach a candidate for real-time implementation on mobile robots. The results are demonstrated by simulated experiments based on a Pioneer robot with eight forward sonar sensors.

The most popular approach to comparing two given tropical cyclones (TCs) is to measure the distance between various contour points of the TC extracted from a satellite image. However, this measure has a very high computational cost as it involves many point-to-point calculations. Moreover, this measure does not reflect the most distinctive features of a tropical cyclone, their spiral shape. In this paper, we propose the use of angle features and time warping for TC forecast. The gradient vector flow (GVF) snake model is applied to extract the contour points of a dominant tropical cyclone from the satellite image. Dvorak templates are used as references to predict the intensity of the tropical cyclone. Given two sets of contour points, one for each tropical cyclone, we retrieve the similarity of two shapes using angle features found among the successive contour points. We adopt a time warping approach to produce a fast and accurate result. Experimental results have shown that our approach is better than other conventional comparison approaches such as Hausdorff distance measure.

One crucial application of intelligent robotic systems is remote surveillance using a security robot. A fundamental need in security is the ability to automatically verify an intruder into a secure or restricted area, to alert remote security personnel, and then to enable them to track the intruder. In this article, we propose an Internet-based security robot system. The face recognition approach possesses "invariant" recognition characteristics, including face recognition where facial expressions, viewing perspectives, three-dimensional poses, individual appearance, and lighting vary and occluding structures are present. The experiment uses a 33.6-kb/s modem Internet connection to successfully remotely control a mobile robot, proving that the streaming technology-based approach greatly improves the "sensibility" of robot teleoperation. This improvement ensures that security personnel can effectively and at low cost use the Internet to remotely control a mobile robot to track and identify a potential intruder.