Real-time object detection is critical for the decision-making process for many real-world applications, such as collision avoidance and path planning in autonomous driving. This work presents an innovative real-time streaming perception method, Transtreaming, which addresses the challenge of real-time object detection with dynamic computational delays. The core innovation of Transtreaming lies in its adaptive delay-aware transformer, which can concurrently predict multiple future frames and select the output that best matches the real-world present time, compensating for any system-induced computational delays. The proposed model outperforms existing state-of-the-art methods, even in single-frame detection scenarios, by leveraging a transformer-based methodology. It demonstrates robust performance across a range of devices, from powerful V100 to modest 2080Ti, achieving the highest level of perceptual accuracy on all platforms. Unlike most state-of-the-art methods that struggle to complete computation within a single frame on less powerful devices, Transtreaming meets the stringent real-time processing requirements on all kinds of devices. The experimental results emphasize the system's adaptability and its potential to significantly improve the safety and reliability of many real-world systems, such as autonomous driving.

This work studies the challenge of scheduling real-time control commands in Networked Control Systems (NCS), where control actions rely on the freshness of data collected from multiple sources. In dynamic environments, ensuring that control commands in an NCS are accurate and frequent is essential for maintaining the system responsiveness. For this aim, we introduce a new metric, Age of Result (AoR), which quantifies the time elapsed since the last control command was generated and executed. This metric reflects the system’s capability to adapt to real-time changes in the operational environment by considering both data freshness and control command frequency. We conduct a detailed analysis of AoR in NCS, paying special attention to the dependencies between sensing and computing phases. We first address computation-intensive and network-intensive scenarios, proposing random sampling (RS)-based approximate algorithms for each case. Subsequently, we develop another RS-based algorithm and a heuristic approach for the general model. Simulation results demonstrate that our approach can effectively minimize AoR and significantly enhance the system performance and real-time adaptability compared to existing strategies.

Unmanned aerial vehicles (UAVs) play a critical role in disaster response, swiftly gathering information from various points-of-interest (PoIs) across extensive areas. The freshness of this information is measured by the age of information (AoI), representing the time since the latest information acquisition of a specific PoI. However, devising AoI-minimizing routes for UAVs in obstructed post-disaster environments poses unique challenges that have yet to be fully overcome. Obstacles, like post-disaster barriers, can impede direct flight paths between PoIs, and limited battery life requires energy-conscious route planning. Additionally, existing solutions fail to universally minimize varying data freshness requirements. This research addresses the AoI-driven UAV travel problem, seeking to establish periodic routes that optimize AoI metrics while considering energy and general graph constraints. We develop a learning-based algorithm to enhance the current route iteratively, utilizing guidance from a deep reinforcement learning (DRL) agent and executing a series of operations to potentially decrease AoI while adhering to topological and energy constraints. The algorithm is validated on real post-disaster datasets, demonstrating significant improvements in various AoI metrics compared to other learning-based approaches. Furthermore, our algorithm outperforms approximation algorithms and can approach the global optimum when tailored to existing AoI-minimizing problems.

Metaverse has been viewed as the next generation of human-computer interaction, which requires collecting information from both the physical and virtual world. One potential way is to employ virtual service providers (VSPs) to finish collection tasks by designing posted-pricing mechanisms via the crowdsensing platform. As VSPs’ costs and values are usually unknown, learning the optimal posted-pricing policy under uncertainty is undoubtedly critical to utilize the budget efficiently. However, existing posted-pricing learning algorithms assume that agents provide services without blocking and agents’ attributes follow an independent identical distribution, both of which are unrealistic in Metaverse, e.g., VSPs should continuously sense the physical world to make provided services realistic, which makes the long working VSP unavailable/blocked for a certain period of time. In this paper, we address the budgeted pricing problem under uncertainty by considering blocking constraints and unknown non-identical VSPs’ attributes. The problem is modeled as a Budgeted-pricing Blocking Bandit (B2-bandit) problem, which remains unaddressed even for the oracle case with known VSPs’ information. We thus first propose a pricing policy for the oracle case with an instance-dependent approximation ratio to the global optimum. For the general B2-bandit problem with unknown information, we propose an online learning algorithm satisfying blocking constraints and incurring an accumulated regret up to$O(MK\log B)$as compared to the oracle approximation algorithm, where$M,K,B$are the number of VSPs, candidate prices and the budget, respectively. Experiments on real datasets validate that the proposed algorithm improves more than 172% accumulated value compared to baseline pricing algorithms.

This work studies the Age-of-Information (AoI) optimization problem in the information-gathering wireless network systems, where time-sensitive data updates are collected from multiple information sources, and each source is equipped with a battery and harvests energy from ambient energy, such as solar, wind, etc. The arrival of the harvested energy can be modeled as the stochastic process, and an information source can deliver its data update only when 1) there is energy in the battery, and 2) this source is selected to transmit its data update based on the transmission policy. This work analyzes how the energy arrival pattern of each source and the transmission policy jointly influence the average AoI among multiple sources. To the best of our knowledge, this is the first work that formally develops the closed-form expression of average AoI in the Stationary Randomized Sampling (SRS) policy space and proposes approximation schemes with constant ratios in multi-source systems under a stochastic energy harvesting model. More specifically, under the perfect wireless channel, the closed-form expression of AoI under the SRS policy space with arbitrary finite battery size is developed. Based on the result, we propose the Max Energy-Aware Weight (MEAW) policy, which is proven to achieve 2-approximation in the full policy space. Under the uncertain wireless channel, we develop the closed-form expression of Whittle’s index to address the target problem. Based on the result, we propose the Energy-aware Whittle’s index policy (EWIP) and prove its approximate performance by using the Lyapunov optimization techniques. Experimental results show that MEAW under the perfect channel setting and EWIP under the uncertain channel setting both perform close to the theoretical lower bound and outperform the state-of-the-art schemes.

Mobile devices have been increasingly deployed in large-scale cyber-physical systems (CPS) to traverse the field and retrieve various data measurements from designated physical entities with stringent performance requirements. This work studies the Availability-constrained real-time Fresh Data Retrieval problem in CPS with a Speed Adjustable mobile device (AFDR-SA). The goal is to maintain the temporal validity of the real-time data with different priorities to be retrieved in the system while meeting the data availability constraints imposed by the communication range between the mobile device and the physical entities. The general case of the AFDR-SA problem is proved to be NP-hard. A dynamic programming (DP)-based optimal algorithm is proposed for a special scenario where the retrieval times of individual data items with the same priority are of the same length. For the general case where data items can have arbitrary retrieval times and different priorities, another different DP-based scheme is proposed, which is proved to be optimal given the retrieval order. A fast heuristic with low complexity is also proposed for the general problem to improve the computational efficiency. The experimental results show that the proposed schemes for the general case outperform the state-of-the-art methods and have close performance compared to the optimal solution while incurring much less computational overhead.

In many IoT applications, information needs to be gathered from multiple heterogeneous sources to the base station for real-time processing and follow-up actions. Undoubtedly, information freshness, measured by age of information (AoI), is critical in taking responsive actions. Recent studies have taken AoI into the consideration of transmission scheduling over wireless channels. However, existing studies on guaranteeing AoI either assume error-free wireless channels or priorly known link reliability, which is unrealistic. In this paper, we tackle the AoI-guaranteed transmission scheduling problem over an unreliable channel with the aim of throughput maximization, which is modelled as an AoI-Guaranteed Multi-Armed Bandit (AG-MAB) problem. Since the problem has not been studied in the literature even for the oracle case with given link reliability, we first propose an optimal stationary randomized sampling (SRS) policy for the oracle case. For the AG-MAB problem with unknown link reliability, we propose learning algorithms that meet the AoI requirements with probability 1 and incur sublinear regret compared to Oracle SRS, which can also detect the unsatisfiability of the AoI constraint and switch to the fallback policy promptly with guaranteed accuracy. Numerical results show that our algorithm outperforms the AoI-constraint-aware baselines on throughput with per-source AoI requirement guaranteed.

Unmanned Aerial Vehicle (UAV) swarm offers extended coverage and is a vital solution for many applications. A key issue in UAV swarm control is to cover all targets while maintaining connectivity among UAVs, referred to as a multi-target coverage problem. With existing dynamic routing protocols, the flying ad hoc network suffers outdated and incorrect route information due to frequent topology changes. This might lead to failures of time-critical tasks. One mitigation solution is to keep the physical topology unchanged, thus maintaining a fixed communication topology and enabling static routing. However, keeping physical topology unchanged may sacrifice the coverage. In this article, we propose to maintain a fixed communication topology among UAVs, which allows certain changes in physical topology, so that to maximize the coverage. We develop a distributed motion planning algorithm for the online multi-target coverage problem with the constraint of keeping communication topology intact. As the communication topology needs to be timely updated when UAVs leave or arrive at the swarm, we further design a topology-management protocol. Experimental results from the ns-3 simulator show that under our algorithms, UAV swarms of different sizes achieve significantly improved delay and loss ratio, efficient coverage, and rapid topology update.

This work studies the non-uniform multi-source data update problem for real-time monitoring systems, where a set of heterogeneous data sources transmit their updates to a Base Station (BS) through wire or wireless channel(s). The performance metric called Age of Information (AoI) - which measures the time elapsed since the last data update of each source received by the BS - is commonly used to quantify the freshness of the data updates. However, most existing work on minimizing AoI of multi-source data updates assume that all sources have a uniform size of data updates which unnecessarily reduces their applicability. This work explores a more general model where individual sources can have non-uniform sizes of data updates, and provides thorough analysis to optimize both peak and average AoI of the target system. Based on these analysis, an optimal scheme to minimize the peak AoI is first developed by guaranteeing the delivery frequency of each source proportional to the function determined by its data size. A$(2+\delta)$-approximation algorithm based on random sampling (RS) and a heuristic called Ratio-driven Maximum Age First (RMAF) are further proposed to minimize the average AoI. Our extensive experiments validate the bound of RS, and show that RMAF can achieve close performance to the lower bound of the minimum time-average AoI and outperforms the state-of-the-art schemes.

Maintaining real-time data freshness plays a critical role in ensuring system correctness and optimizing the system performance in networked embedded systems (NESs). To quantitatively measure the freshness of the collected real-time data, the concept of Age of Information (AoI) has been extensively studied in recent years. This article explores how to minimize the worst case AoI of real-time data in radio-frequency (RF)-powered NESs. In such systems, one hybrid access point (HAP) transfers wireless power to a set of distributed sensor nodes, and in the meantime, receives the information from these sensor nodes. We utilize the metric of AoI to measure the data freshness and present a comprehensive analysis of the worst case AoI of the real-time data in the target system. Based on the analysis, an optimal energy schedule solution is designed to judiciously determine individual sensor nodes’ energy and time allocation to minimize the worst case AoI. Considering the varying importance of different information and sensor nodes in the target system, we further propose the optimal time and energy allocation scheme for minimizing the weighted worst case AoI. A multinode RF-powered NES testbed is implemented to validate the functional correctness of our solutions. The results show that our solutions significantly outperform the state-of-the-art solutions, reducing the worst case AoI and weighted worst case AoI by 69.3% and 75.1% on average, respectively.

In a crowdsensing platform, users are invited to provide data services, and multiple requesters compete for desired services. Due to users' costs of providing services, it is critical to design incentive mechanisms to incentivize users with (monetary) rewards. Meanwhile, requesters may have individual budgets and compete for services with different procurement abilities. Such a setting falls into the budget-feasible mechanism design. However, most of the existing budget-feasible mechanisms focus on one-sided markets with a single requester rather than the two-sided markets with multiple requesters having different procurement abilities. Moreover, requesters and users can be selfish and strategic with their private information, which requires preventing information manipulation on both requesters' and users' sides. In this paper, we investigate budget-feasible mechanisms in two-sided crowdsensing markets where multiple strategic requesters come with private budgets to obtain services from the strategic users. We also consider the fairness on the requesters' side,i.e., a requester with more budget should obtain more service. We propose budget-feasible mechanisms for two models by distinguishing the types of services,i.e., the homogeneous or heterogeneous services. All proposed mechanisms satisfy fairness, budget feasibility, truthfulness on both users' and requesters' sides, and the constant approximation ratio. Numerical experiment results further demonstrate the efficiency of our proposed mechanisms.

Energy harvesting techniques have been increasingly employed in both consumer and industrial applications to provide clean energy supply. Among the many available energy harvesting techniques, ambient energy harvesting (AEH) is a promising one as it harvests free energy from the environment and, thus, is economically efficient. AEH techniques, however, heavily depend on the dynamic environment and are thus uncontrollable and unstable. More recently, the wireless power transfer (WPT) technique has attracted significant attentions due to its highly controllable feature when powering low-cost devices. Unfortunately, WPT faces strict regulatory limitations to provide high power density and requires charging infrastructures installed to perform effective wireless energy transfer. The pros and cons of the two techniques motivate this work to design a hybrid energy harvesting method by charging a device using a combination of AEH and WPT to maximize the throughput of a wireless system. Specifically, this work first proposes an optimal offline charging scheme to maximize the point-to-point data throughput of a wireless system by fully utilizing the ambient energy and providing extra power supply through WPT to determine the transmission rates. An online heuristic algorithm is further proposed to improve the computational efficiency for practical scenarios when the system has the estimation of future AEH patterns. Our experimental results show that the proposed approaches are effective in maximizing the data throughput when compared to the state of the art.

Mobile devices have been increasingly deployed in large-scale cyber-physical systems (CPS) to traverse the field and retrieve data measurements from designated physical entities with stringent performance requirements. This work studies the availability-constrained real-time data retrieval problem in CPS with a speed adjustable mobile device (AFDR-SA). The goal is to maintain the temporal validity of the real-time data to be retrieved in the system while meeting the data availability constraints imposed by the communication range between the mobile device and the physical entities. A dynamic programming (DP)-based optimal algorithm is proposed for a special but commonly presented scenario where the retrieval times of individual data items are of the same length. Based on this optimal algorithm, an effective heuristic method is further developed for the general case where data items can have arbitrary retrieval times. The effectiveness of the proposed methods are validated through extensive experiments. Our results demonstrate the optimality of the DP-based algorithm, and show that the heuristic method outperforms the state-of-the-art schemes and performs close to the optimal solution obtained by the exhaustive search with much less computational overhead.

Real-time end-to-end task scheduling in networked control systems (NCSs) requires the joint consideration of both network and computing resources to guarantee the desired quality of service (QoS). This paper introduces a new model for composite resource scheduling (CRS) in real-time networked control systems, which considers a strict execution order of sensing, computing, and actuating segments based on the control loop of the target NCS. We prove that the general CRS problem is NP-hard and study two special cases of the CRS problem. The first case restricts the computing and actuating segments to have unit-size execution time while the second case assumes that both sensing and actuating segments have unit-size execution time. We propose an optimal algorithm to solve the first case by checking the intervals with 100% network resource utilization and modify the deadlines of the tasks within those intervals to prune the search. For the second case, we propose another optimal algorithm based on a novel backtracking strategy to check the time intervals with the network resource utilization larger than 100% and modify the timing parameters of tasks based on these intervals. For the general case, we design a greedy strategy to modify the timing parameters of both network segments and computing segments within the time intervals that have network and computing resource utilization larger than 100%, respectively. The correctness and effectiveness of the proposed algorithms are verified through extensive experiments.

Read-ahead schemes have been widely used in page cache to improve read performance of Linux systems. As the Android system inherits the Linux kernel, the traditional read-ahead scheme is directly transplanted to mobile devices. However, request sizes and page cache sizes on mobile devices are much smaller, which may degrade read-ahead efficiency and therefore hurt user experience. This article first observes that many pages pre-fetched by read-ahead are unused, which causes frequent page cache eviction. And these evict operations could induce extra access latency, especially when write-back is conducting. Then, this article proposes a new analysis model to characterize the factors that closely relate to the access latency. It is found that there exists a trade-off between read-ahead size and access latency. Finally, this article proposes two optimized read-ahead schemes to exploit this trade-off under different situations. Size-tuning scheme aims to find the proper maximum size of read-ahead according to the characteristics of mobile devices. While MobiRA scheme improves the read-ahead efficiency by dynamically tuning read-ahead size and stop-settings. Experimental results on real mobile devices show that the proposed schemes can increase the efficiency of read-ahead scheme and improve the overall performance of mobile devices.

TRIM is a recommended command to deliver data invalidation information of the file system to flash storage. It is issued on both system level and device level. Since it can reduce the number of data copies during device-level garbage collection (DGC), TRIM has been widely used to improve the endurance and performance of mobile devices. Contrary to the common belief, this work identifies that the default TRIM scheme has both merit and drawback to the performance of mobile devices, especially in flash-friendly file system (F2FS), which is a commonly used file system in mobile devices. On one hand, TRIM can reduce garbage collection migration to prolong the flash lifetime as well as improving I/O throughput; On the other hand, TRIM may induce I/O contentions. This article proposes a new TRIM scheme, iTRIM, to distribute the timing overheads to system idle time. To further reduce I/O contention and improve I/O performance, the design of iTRIM considers the TRIM size, and the logical addresses' pattern of victim invalidated data. Experimental results show that iTRIM can minimize I/O contentions while retaining the benefits of the default TRIM scheme for endurance and performance.

This paper studies how to maintain real-time data freshness in the emerging wireless powered communication networks (WPCNs). In a WPCN, one or multiple hybrid access points (HAPs) with constant power supply transfer the energy and receive the status update through wireless to and from a set of distributed sensor nodes simultaneously. We utilize the concept of Age of Information (AoI) to quantitatively measure the freshness of the sensor data, and formulate the AoI optimization problem. Based on this problem formulation, we first explore the optimal time allocation method to minimize the average AoI for sensor nodes in single-hop WPCNs. This method is then extended to derive the optimal time allocation for two-hop WPCNs, where some sensor nodes may transmit status update to the HAP through relay nodes. In this more complex scenario, we apply a two-phase method to 1) identify all the two-hop node candidates and their associated relay nodes, and 2) determine the best assignment and the corresponding time allocation to optimize the average AoI. A 5-node WPCN testbed is developed to validate the functional correctness of the proposed methods. Extensive simulations are also conducted for performance evaluation under more comprehensive settings. The experimental results show that the proposed methods can reduce the average AoI by 83.4% on average compared to the state-of-the-art methods.

Merging technique is widely adopted by I/O schedulers to maximize system I/O throughput. However, I/O merging could increase the latency of individual I/O, thus incurring prolonged I/O latencies and enlarged performance variations. Even with better system throughput, higher worst-case latency experienced by some requests could block the SSD storage system, which violates the QoS (Quality of Service) requirement. In order to improve QoS performance while providing higher I/O throughput, this paper proposes a reinforcement learning based I/O merging approach. Through learning the characteristic of various I/O patterns, the proposed approach makes merging decisions adaptively based on different I/O workloads. Evaluation results show that the proposed scheme is capable of reducing the standard deviation of I/O latency by 19.1 percent on average, worst-case latency by 7.3-60.9 percent at the 99.9th percentile compared with the latest I/O merging scheme, while maximizing system throughput.

This article explores how to optimize the freshness of real-time data for energy harvesting (EH)-based networked embedded systems (NESs) with energy constraints. We introduce the concept of age of information (AoI) to quantitatively measure the data freshness and present a comprehensive analysis on the average AoI of the real-time data with stochastic update arrival and energy replenishment patterns for single-source EH-based systems. An optimal offline solution and an effective online solution are designed to select a sequence of real-time data updates (while discarding the remaining ones) and determine their corresponding transmission time to minimize the average AoI. We further extend these findings to multisource EH-based NESs, and present an optimal offline solution and an efficient online solution to schedule updates for each data source to optimize the average AoI. The correctness of the analysis and the effectiveness of the proposed solutions have been validated through extensive experiments by comparing to the state-of-the-art methods. According to the experimental results, the proposed solutions reduce the average AoI by 47.2% and 69.1% on average comparing to the state-of-the-art solutions for single-source and multisource EH-based NESs, respectively, with low harvesting rates.

This paper explores how to optimize the freshness of real-time data in energy harvesting based networked embedded systems. We introduce the concept of Age of Information (AoI) to quantitatively measure the data freshness and present a comprehensive analysis on the average AoI of the real-time data with stochastic update arrival and energy replenishment rates. Both an optimal offline solution and an effective online solution are designed to judiciously select a subset of the real-time data updates and determine their corresponding transmission times to optimize the average AoI subject to energy constraints. Our extensive experiments have validated the effectiveness of the proposed solutions, and showed that these two methods can significantly improve the average AoI by 47.2% comparing to the state-of-the-art solutions for low energy replenishment rate.

Hardware acceleration through field programmable gate arrays (FPGAs) has recently become a technique of growing interest for many data-intensive applications. Join query is one of the most fundamental database query types useful in relational database management systems. However, the available solutions so far have been beset by higher costs in comparison with other query types. In this paper, we develop a novel solution to accelerate the processing of sort-merge join queries with low match rates. Specifically, our solution makes use of hierarchical indexes to identify result-yielding regions in the solution space in order to take advantage of result sparseness. Further, in addition to one-dimensional equi-join query processing, our solution supports processing of multidimensional similarity join queries. Experimental results show that our solution is superior to the best existing method in a low match rate setting; the method achieves a speedup factor of 4.8 for join queries with a match rate of 5%.

Maintaining the temporal validity of real-time data in cyber-physical systems is of critical importance to ensure the correct decision making and appropriate system operation. Most existing work on real-time data retrieval assume that the real-time data under study are always available for retrieval, and the developed scheduling algorithms mainly focus on making real-time decisions while meeting the temporal validity constraints. This assumption, however does not hold in many real-time applications with intermittent data availability. In this paper, we study the Availability-constrained Fresh Data Retrieval (AFDR) problem, which aims to retrieve all required real-time data for a given set of decision tasks on time while taking both the temporal validity and data availability constraints into consideration. We formulate the AFDR problem as an ILP problem and study its complexity under different settings. Given the general case of the AFDR problem is proved to be NP-hard, we focus on the cases that data items have unit-size retrieval time. For the single decision task scenario, we propose a polynomial-time optimal data retrieval algorithm, which consists of a task finish time selection phase and an optimal retrieval schedule construction phase, to solve the AFDR problem. For the multiple decision task scenario, we propose an efficient heuristic algorithm by transforming the temporal validity constraint of a real-time data item to the availability constraint. The effectiveness of the proposed algorithms has been validated through extensive experiments. Our results show that the heuristic algorithm outputs around $1.5\times$1.5× feasible cases compared to that of the state-of-the-art scheme.

Hardware acceleration through field programmable gate arrays (FPGAs) has recently become a technique of growing interest for many data-intensive applications. Join query is one of the most fundamental database query types useful in relational database management systems. However, the available solutions so far have been beset by higher costs in comparison to other query types. In this paper, we develop a novel solution to accelerate the processing of sort-merge join queries with low match rates. Specifically, our solution makes use of hierarchical indexes to identify result-yielding regions in the solution space in order to take advantage of result sparseness. Further, in addition to one-dimensional equi-join query processing, our solution supports processing of multidimensional similarity join queries. Experimental results show that our solution is superior to the best existing method in a low match rate setting; the method achieves a speedup factor of 4.8 for join queries with a match rate of 5 percent.

Real-time task scheduling for wireless networked control systems provides guarantees for the quality of service. This paper introduces a new model for joint network and computing resource scheduling (JNCRS) in real-time wireless networked control systems. This new end-to-end real-time task model considers a strict execution order of segments including the sensing, the computing and the actuating segment based on the control loop of WNCSs. The general JNCRS problem is proved to be a NP-hard problem. After dividing the JNCRS problem into four subproblems, we propose a polynomial-time optimal algorithm to solve the first subproblem where each segment has unit execution time, by checking the intervals with 100% network resource utilization and modify the deadlines of tasks. To solve the second subproblem where the computing segment is larger than one unit execution time, we define the new timing parameters of each network segment by taking into account the scheduling of the computing segments. We propose a polynomial-time optimal algorithm to check the intervals with the network resource utilization larger than or equal to 100% and modify the timing parameters of tasks based on these intervals.

The rapid development of the Real-Time and Embedded System (RTES) has increased the requirement on the processing capabilities of sensors, mobiles and smart devices, etc. Meanwhile, energy efficiency techniques are in desperate need as most devices in RTES are battery powered. Following the above trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The problem complexity analysis for different task and system models is also presented. Experimental results show that the proposed approximation scheme performs close to the optimal solution in average.

Maintaining the temporal validity of real-time data in cyber-physical systems (CPSs) is of critical importance to ensure correct decision making and appropriate system operation. Most existing work on real-time data retrieval assumes that the real-time data under study are always available, and the developed scheduling algorithms mainly focus on making real-time decisions while meeting the temporal validity (freshness) constraints. This assumption, however does not hold in many real-life CPS applications with intermittent data availability, such as in energy harvesting-based sensing systems. In this paper, we study the multi-interval availability-constrained fresh data retrieval (MAFDR) problem, which aims to retrieve all required real-time data on time for a set of decision tasks while taking both the temporal validity and data availability constraints into consideration. We present the formulation of the MAFDR problem and study its complexity under different settings. For the scenario of single decision task with unit-size data retrieval time, we propose a polynomial-time optimal data retrieval algorithm, which comprises a task finish time selection phase and an optimal retrieval schedule construction phase. For the general scenario of multiple decision tasks with nonunit-size data retrieval time, we provide an integer linear programming formulation for the MAFDR problem and propose a fast heuristic algorithm based on max flow. The effectiveness of the proposed algorithms has been validated through extensive experiments by comparing to the optimal solution and the state-of-the-art approach.

Flash Friendly File System (F2FS) is getting popular among mobile devices. However, lack of empirical and comprehensive analysis for characteristics of F2FS prohibits better application of F2FS. In this paper, we present a set of comprehensive experimental studies on mobile devices and show several counterintuitive observations on F2FS, including imprecise hot/cold data separation, unexpected trigger condition of background GC, impact of fragmentation on read performance and impact of readahead by fragments and available space. Based on these observations, we further provide several pilot solutions to improve the performance of these mobile devices. The objective is to inspire researchers and users to pay attention to F2FS characteristics, and further optimize its performance.

Wearable devices gain increasing popularity since they can collect important information for healthcare and well-being purposes. Compared with battery, energy harvesting is a better power source for these wearable devices due to many advantages. However, harvested energy is naturally unstable and program execution will be interrupted frequently. Nonvolatile processors demonstrate promising advantages to back up volatile state before the system energy is depleted. However, it also introduces non-negligible energy and area overhead. In this paper, we aim to reduce the amount of data that need to be backed up during a power failure. Based on the observation that stack size varies along program execution, we propose to analyze the application program and identify efficient backup positions, by which the stack content to back up can be significantly reduced. The evaluation results show an average of 45.7% reduction on nonvolatile stack size for stack backup, with 0.58% storage overhead. In the mean time, with the proposed schemes, the energy utilization and program forward progress can be greatly improved compared with instant backup.

Nowadays, memory energy reduction attracts significant attention as main memory consumes large amount of energy among all the energy consuming components. This paper focuses on reducing the energy consumption of the shared main memory in multicore processors by putting the memory into sleep state when all cores are idle. Based on this idea, we present systematic analysis of different models and propose a series of scheduling schemes to maximize the common idle time of all cores. The target problem is classified into two cases based on whether task migration is allowed or not among cores. Considering task migration, an optimal scheduling scheme is proposed, assuming the number of cores is unbounded. When the number of cores is bounded, an integer linear programming formulation and two efficient heuristic algorithms are proposed. When task migration is not allowed, we first prove the NP-hardness of the problem, and then propose the optimal solutions when task partitions are given in advance. The energy overhead caused by transitions between active and sleep modes of the memory is analyzed. The experimental results show that the heuristic algorithms work efficiently and can save 7.25% and 11.71% system energy, respectively, with 1-GB memory, compared with an energy-efficient multicore scheduling scheme. Larger energy reduction can be further achieved with larger size of memory.

Nonvolatile processors have manifested strong vitality in battery-less energy harvesting sensor nodes due to their characteristics of zero standby power, resilience to power failures and fast read/write operations. However, I/O and sensing operations cannot store their system states after power off, hence they are sensitive to power failures and high power switching overhead is induced during power oscillation, which significantly degrades the system performance. In this paper, we propose a novel performance-aware task scheduling technique considering power switching overhead for energy harvesting nonvolatile processors. We first give the analysis of the power switching overhead on energy harvesting sensor nodes. Then, the scheduling problem is formulated by MILP (Mixed Integer Linear Programming). Furthermore, a task splitting strategy is adopted to improve the performance and an heuristic scheduling algorithm is proposed to reduce the problem complexity. Experimental results show that the proposed scheduling approach can improve the performance by 14% on average compared to the state-of-the-art scheduling strategy. With the employment of the task splitting approach, the execution time can be further reduced by 10.6%.

The rapid development of the Internet of Things (IoT) has increased the requirement on the processing capabilities of sensors, mobile phones and smart devices. Meanwhile, energy efficiency techniques are in desperate need as most devices in the IoT systems are battery powered. Following the above two trends, this work explores the memory system energy efficiency for a general multi-core architecture. This architecture integrates a local memory in each processing core, with a large off-chip memory shared among multiple cores. Decisions need to be made on whether tasks will be executed with the shared memory or the local memory to minimize the total energy consumption within real-time constraints. This paper proposes optimal schemes as well as a polynomial-time approximation algorithm with constant ratio. The complexity analysis of the problem for different task and system models is also presented. Experimental results show that the proposed approximation algorithm performs close to the optimal solution in average.

Energy consumption of memories is always a significant issue for computing systems. Recently, hybrid PRAM and DRAM memory architectures have been proposed. It combines the advantages of DRAM and PRAM, such as low leakage power in PRAM and short write latency in DRAM. However, the leakage power in DRAM is still considerable in hybrid memories. The leakage power can only be reduced by turning DRAM into sleep state. In this paper, a novel proximity concept is proposed to guide the variable partitioning to maximize the possibility of turning DRAM into sleep mode. A novel Sleep-Aware Variable Partition Algorithm (SAVPA) is then proposed with the objective of maximizing the sleep time of DRAM while satisfying the performance and endurance constraints. The experiment results show that SAVPA reduces the energy consumption by 11.25% in average (up to 15.84%) compared to the state-of-art work with simple sleep technique.

Recently hybrid cache architecture consisting of both spin-transfer torque RAM (STT-RAM) and SRAM has been proposed for energy efficiency. In hybrid caches, migration-based techniques have been proposed. A migration technique dynamically moves write-intensive and read-intensive data between STT-RAM and SRAM to explore the advantages of hybrid cache. Meanwhile, migrations also introduce extra reads and writes during data movements. For stencil loops with read and write data dependencies, we observe that migration overhead is significant, and migrations closely correlate to the interleaved read and write memory access pattern in a memory block. This paper proposes a loop retiming framework during compilation to reduce the migration overhead by changing the interleaved memory access pattern. With the proposed loop retiming technique, the interleaved memory accesses can be significantly reduced so that migration overhead is mitigated, and energy efficiency of hybrid cache is significantly improved. The experimental results have shown that, with the proposed methods, on average, the migration number is reduced up to 27.1% and the cache dynamic energy is reduced up to 14.0%.

In hybrid cache architecture consisting of both STT-RAM and SRAM, migration based techniques have been proposed. The migration technique dynamically moves write-intensive and read-intensive data between STT-RAM and SRAM to explore the advantage of hybrid cache. Meanwhile, migrations induce extra read and write overhead during data movements. For loops with intensive data array operations, we observe that migration overhead is significant and migrations closely correlate to the interleaved read and write access pattern in a memory block. This paper proposes a loop retiming framework to reduce the migration overhead by changing the interleaved memory access pattern. The experimental results show that with the proposed method, migrations are significantly reduced without any hardware modification. As a result, energy efficiency and performance of hybrid cache can be improved.

Cache locking is a cache management technique to preclude the replacement of locked contents. Recently, instruction cache locking has been applied to improve average-case execution time (ACET). However, we observe that the prior instruction cache locking method shows very limited performance improve-ment for data cache. The main reason lies in that, data access similarity in data memory blocks is weaker than that in code memory blocks. This paper proposes a data re-allocation enabled cache locking approach which can significantly enhance locking efficiency for data cache and thus improve system performance. The experimental results show that with the proposed approach, on average, the miss rate is reduced by 9.1% and execution cycles are reduced by 9.4% across a suite of benchmarks.