Modern DNN workloads are increasingly diverse in operation types, tensor shapes, and execution dependencies, making it difficult for customized accelerators to sustain high hardware efficiency across models. We propose DORA, an instruction-based overlay architecture as well as a compilation framework that explicitly describes dataflow via a proposed ISA, enabling fine-grained control of data movement, computation, and synchronization at the layer level.

As deep neural networks develop significantly more diverse and complex, achieving high performance and efficiency on complicated DNN models faces pressing challenges. Modern DNN workloads are increasingly diverse in operation types, tensor shapes, and execution dependencies, making it difficult to sustain high hardware efficiency across models. In addition, a generic accelerator often incurs substantial overhead when executing diverse workloads.

Video object detection stands as a pivotal element within the burgeoning landscape of autonomous driving systems. The exigency to fulfill stringent real-time requisites, while upholding both precision and efficiency in detection, underscores its significance. Although extant methodologies enhance either accuracy or efficiency through the exploitation of spatio-temporal inter-dependencies within the video context, their propensity to conduct detection on discrete frames begets superfluous computations and curbed real-time efficacy. This paper introduces a pioneering approach, called Real-Batch, tailored explicitly to redress this quandary. Real-Batch ingeniously processes batches of video frames uniformly, effectually winnowing out repetitive object detection occurrences. Our methodology is rigorously evaluated on the real-word datasets, scrutinizing four key metrics: accuracy, efficiency, informational value, and adherence to timing constraints. The comprehensive findings substantiate that Real-Batch yields an unparalleled maximal surge in accuracy and efficiency, increasing of 4.2%-13.2% and 24.7%-43.9%, respectively, offering promising advancements for autonomous driving systems.

Deep neural network (DNN) models are increasingly deployed in real-time, safety-critical systems such as autonomous vehicles, driving the need for specialized AI accelerators. However, most existing accelerators support only non-preemptive execution or limited preemptive scheduling at the coarse granularity of DNN layers. This restriction leads to frequent priority inversion due to the scarcity of preemption points, resulting in unpredictable execution behavior and, ultimately, system failure. To address these limitations and improve the real-time performance of AI accelerators, we propose DERCA, a novel accelerator architecture that supports fine-grained, intra-layer flexible preemptive scheduling with cycle-level determinism. DERCA incorporates an on-chip Earliest Deadline First (EDF) scheduler to reduce both scheduling latency and variance, along with a customized dataflow design that enables intralayer preemption points (PPs) while minimizing the overhead associated with preemption. Leveraging the limited preemptive task model, we perform a comprehensive predictability analysis of DERCA, enabling formal schedulability analysis and optimized placement of preemption points within the constraints of limited preemptive scheduling. We implement DERCA on the AMD ACAP VCK190 reconfigurable platform. Experimental results show that DERCA outperforms state-of-the-art designs using non-preemptive and layer-wise preemptive dataflows, with less than 5 % overhead in worst-case execution time (WCET) and only 6% additional resource utilization. DERCA is open-sourced on GitHub: https://github.com/arc-research-lab/DERCA

With the growing demand for software-defined vehicles (SDVs), deep learning-based perception models have become increasingly important in intelligent transportation systems. However, these models face significant challenges in enabling real-time and efficient SDV solutions due to their substantial computational requirements, which are often unavailable in resource-constrained vehicles. As a result, these models typically suffer from low throughput, high latency, and excessive GPU/memory usage, making them impractical for real-time SDV applications. To address these challenges, our research focuses on optimizing model and workflow performance through the integration of pruning and quantization techniques across various computational environments, utilizing frameworks, such as PyTorch, open neural network exchange (ONNX), ONNX Runtime, and TensorRT. We systematically explore and evaluate three distinct pruning methods in combination with multiprecision quantization workflows (FP32, FP16, and INT8) and present the results based on four evaluation metrics: 1) inference throughput; 2) latency; 3) GPU/memory usage; and 4) accuracy. Our designed techniques, including pruning and quantization, along with optimized workflows, can achieve up to$18\times $faster inference speed and$16.5\times $higher throughput, while reducing GPU/memory usage by up to 30%, all with minimal impact on accuracy. Our work suggests using the Torch-ONNX-TensorRT workflow quantized with 16-bit floating point precision (FP16) precision and group pruning as the optimal strategy for maximizing inference performance. It demonstrates great potential in optimizing real-time, efficient perception workflows in SDVs, contributing to the enhanced application of deep learning models in resource-constrained environments.

Mobile applications based on machine learning (ML) are increasingly relying on offloading to the edge devices for low-latency, resource-efficient computation. Applying serverless computing for these ML applications on the edge offers a promising solution for handling dynamic workloads while meeting user-specified latency service-level objectives (SLOs). However, existing serverless frameworks, with their coarse-grained data parallelism and rigid model partitioning, are inadequate for ML inference on widely adopted edge System-on-Chip (SoC) devices. This paper presents FluidEdge, an edge-native serverless inference framework. FluidEdge identifies bottleneck operators in ML models and addresses them through a novel fine-grained intra-function latency-sensitive auto-scaling approach that dynamically scales inference bottlenecks during online serving. Additionally, it employs inter-function scaling to further prevent latency SLO violations and leverages the unified memory of edge SoCs for efficient data sharing during inference. Experimental results demonstrate that FluidEdge achieves a 37.4% latency improvement and 67.3%-87.6% SLO violation reduction compared to best-performed state-of-the-art serverless inference frameworks.

One of the most important tasks in ride-hailing is order dispatching, i.e., assigning unserved orders to available drivers. Recent order dispatching has achieved a significant improvement due to the advance of reinforcement learning, which has been approved to be able to effectively address sequential decision-making problems like order dispatching. However, most existing reinforcement learning methods require agents to learn the optimal policy by interacting with environments online, which is challenging or impractical for real-world deployment due to high costs or safety concerns. For example, due to the spatiotemporally unbalanced supply and demand, online reinforcement learning-based order dispatching may significantly impact the revenue of the ride-hailing platform and passenger experience during the policy learning period. Hence, in this work, we develop an offline deep reinforcement learning framework called NondBREM for large-scale order dispatching, which learns policy from only the accumulated logged data to avoid costly and unsafe interactions with the environment. In NondBREM, a Nondeterministic Batch-Constrained Q-learning (NondBCQ) module is developed to reduce the algorithm extrapolation error and a Random Ensemble Mixture (REM) module that integrates multiple value networks with multi-head networks is utilized to improve the model generalization and robustness. Extensive experiments on large-scale real-world ride-hailing datasets show the superiority of our design.

Neural Network Inference (NNI) has become a critical element in mobile and autonomous systems, particularly for time-sensitive operations like obstacle detection and avoidance. Alongside execution time, energy consumption holds significant importance in such workloads, given that power is a limited resource in these systems. Modern System-on-Chips (SoCs) in mobile and autonomous devices are equipped with a diverse range of accelerators, each characterized by distinct power and performance features. Adapting to dynamically changing physical conditions, the execution flow of these crucial workloads can be optimized to utilize multiple accelerators, allowing for a flexible trade-off between performance and energy consumption. In this study, we leverage multiple accelerators within an SoC to execute NNI using NVIDIA TensorRT. Our primary goal is to enable an energy-performance trade-off by intelligently distributing layers of a neural network between accelerators that prioritize performance and those that emphasize power efficiency. Initially, we analyze the execution time and energy characteristics of neural network layer execution on various accelerators. Subsequently, we examine various factors influencing layer execution. Finally, we propose two algorithms to determine the mapping of layers to accelerators, minimizing energy consumption while adhering to a predetermined target NN inference execution time. We evaluate our approaches on the NVIDIA AGX Orin SoC using the commonly used ResNetSO model. According to the experiment results, we suggest adopting a coarse-grained layer grouping strategy. For applications with stringent real-time requirements, it is recommended to utilize the proposed LTN approach to better achieve the target execution time. Alternatively, in other scenarios, the Knapsack approach may be chosen for potential improvements in energy consumption.

With the worldwide mobility electrification initiative to reduce air pollution and energy security, more and more for-hire vehicles are being replaced with electric ones. A key difference between gas for-hire vehicles and electric for-hire vehicles (EFHV) is their energy replenishment mechanisms, i.e., refueling or charging, which is reflected in two aspects: (i) much longer charging processes vs. much shorter refueling processes and (ii) time-varying electricity prices vs. time-invariant gasoline prices during a day. The complicated charging issues (e.g., long charging time and dynamic charging pricing) potentially reduce the daily operation time and profits of EFHVs, and also cause overcrowded charging stations during some off-peak charging pricing periods. Motivated by a set of findings obtained from a data-driven investigation and field studies, in this paper, we design a fairness-aware vehicle displacement system calledFairMoveto jointly optimize the overall profit efficiency and profit fairness of EFHV drivers by considering both the passenger travel demand and vehicle charging demand. We first formulate the EFHV displacement problem as a Markov decision problem, and then we present a fairness-aware multi-agent actor-critic approach to tackle this problem. More importantly, we implement and evaluateFairMovewith real-world streaming data from the Chinese city Shenzhen, including GPS data and transaction data from over 20,100 EFHVs, coupled with the data of 123 charging stations, which constitute, to our knowledge, the largest EFHV network in the world. Extensive experimental results show that our fairness-awareFairMoveeffectively improves the profit efficiency and profit fairness of the EFHV fleet by 26.9% and 54.8%, respectively. It also improves the charging station utilization fairness by 38.4%.

Shared autonomous electric mobility has attracted significant interest in recent years due to its potential to save energy consumption, enhance mobility accessibility, reduce air pollution, mitigate traffic congestion, etc. Although providing convenient, low-cost, and environmentally-friendly mobility, there are still some roadblocks to achieve efficient shared autonomous electric mobility, e.g., how to enable the accessibility of shared autonomous electric vehicles in time. To overcome these roadblocks, in this article, we designSafari, an efficientSharedAutonomous electric vehicleFleet mAnagement system with jointRepositioning and chargIng based on dynamic deadlines to improve both user experience and operating profits. OurSafariconsiders not only the highly dynamic user demand forvehicle repositioning(i.e., where to relocate) but also many practical factors like the time-varying charging pricing forcharging scheduling(i.e., where to charge). To perform the two tasks efficiently, inSafari, we design a dynamic deadline-based deep reinforcement learning algorithm, which generates dynamic deadlines via usage prediction combined with an error compensation mechanism to adaptively learn the optimal decisions for satisfying highly dynamic and unbalanced user demand in real time. More importantly, we implement and evaluate theSafarisystem with 10-month real-world shared electric vehicle data, and the extensive experimental results show that ourSafariachieves 100% of accessibility and effectively reduces 26.2% of charging costs and reduces 31.8% of vehicle movements for energy saving with a small runtime overhead at the same time. Furthermore, the results also showSafarihas a great potential to achieve efficient and accessible shared autonomous electric mobility during its long-term expansion and evolution process.

Following the trend of increasing autonomy in real-time systems, multi-core System-on-Chips (SoCs) have enabled devices to better handle the large streams of data and intensive computation required by such autonomous systems. In modern multi-core SoCs, each L1 cache is designed to be tied to an individual processor, and a processor can only access its own L1 cache. This design method ensures the system's average throughput, but also limits the possibility of parallelism, significantly reducing the system's real-time schedulability. To overcome this problem, we present a new system framework for highly-parallel multi-core systems,Hopscotch.Hopscotchintroduces re-sizable L1 cache which is shared between processors in the same computing cluster. At execution,Hopscotchdynamically allocates L1 cache capacity to the tasks executed by the processors, unblocking the available parallelism in the system. Based on the new hardware architecture, we also present a new theoretical model and schedulability analysis providing cache size selection methods and corresponding timing guarantees for the system. As demonstrated in the evaluations,Hopscotcheffectively improves system-level schedulability with negligible extra overhead.

In modern real-time heterogeneous System-on-Chips, ensuring real-time performance is increasingly important. However, with ever-increasing hardware and architectural complexity, satisfying such timing requirements becomes very challenging due to both hardware heterogeneity and the complicated access paths induced by the on-chip accelerators. In this paper, inspired by an interesting observation from accelerable real-time task scheduling, we propose a new core-accelerator interface, BlueFace, which is integrated into the memory access stage of the CPU pipeline, effectively avoiding the complicated HA access paths. The BlueFace design constructs a priority queue to schedule the HA operations at the hardware level, ensuring simultaneous throughput and real-time performance. The evaluation demonstrates the performance benefits and gives the overhead of BlueFace.

Many real-time systems process and react to external events by a chain of tasks, and have constraints on the maximum reaction time which describes how long it takes to respond to an external event. While a processing chain typically starts with a sampling task periodically triggered to sample the sensor data, other tasks in the chain could be triggered in two different ways: event-triggered or time-triggered, which have their own pros and cons. In this paper, we propose the third option to trigger the processing tasks in a chain, namely, the event-triggered with data refreshing approach, which combines the benefits of the event-triggered or time-triggered approaches. As the main technical contribution, we develop techniques to formally upper-bound its maximum reaction time and analytically compare it with the existing approaches. Experiments with synthetic workload are conducted to show the performance improvement by our proposed techniques.

In automotive systems, an important timing requirement is that the time disparity (the maximum difference among the timestamps of all raw data produced by sensors that an output originates from) must be bounded in a certain range, so that information from different sensors can be correctly synchronized and fused. In this paper, we study the problem of analyzing the worst-case time disparity in cause-effect chains. In particular, we present two bounds, where the first one assumes all chains are independent from each other and the second one takes the fork-join structures into consideration to perform more precise analysis. Moreover, we propose a solution to cut down the worst-case time disparity for a task by designing buffers with proper sizes. Experiments are conducted to show the correctness and effectiveness of both our analysis and optimization methods.

Multi-sensor data fusion is crucial for modern autonomous systems to accurately perceive their surrounding environments and make intelligent decisions. However, as different sensor sources may have significant time disparity, it is necessary to synchronize their data before sending them to the fusion algorithm, in order to control such differences and get meaningful fusion results. This paper discusses the message synchronization policy in ROS, a popular framework for robotic systems. The ROS message synchronization policy has proven to be highly effective in reducing the time disparity, but it introduces a certain level of latency. Therefore, to use it for real-time systems, it is essential to establish an upper bound for the worst-case latency that may occur. Specifically, we analyze two key latency metrics of the ROS message synchronization policy, the passing latency and reaction latency, which are needed to analyze the end-to-end delay and reaction time on the system level. We conduct experiments under different settings to evaluate the precision of our proposed latency upper bounds against the maximum observed latency in real execution.

In modern real-time heterogeneous System-on-Chips (SoCs), ensuring the predictability of interconnects is becoming increasingly important. Most of the existing interconnects are mainly designed to achieve high throughput, with their micro-architectures usually based on FIFO queues. The FIFO-based design prevents transaction prioritization based on importance and leads to occurrences of physical priority inversion. Such problems lead to difficulties in ensuring transaction predictability, especially when the system scales to a large number of elements. In this paper, we introduce AXI-Interconnect^{rt} (AXI-IC^{rt}, for short) -- a real-time AXI interconnect for heterogeneous SoCs, which redefines the micro-architecture of interconnects by enabling random accesses of buffered transactions and organizing transactions through compositional scheduling. This hardware-software co-design approach provides predictable and scalable real-time performance for highly integrated SoCs.

In safety-critical computing systems, the I/O virtualization must simultaneously satisfy different requirements, including time-predictability, performance, and energy-efficiency. However, these requirements are challenging to achieve due to complex I/O access path and resource management at the system level, lack of support from preemptive scheduling at I/O hardware level, and missing an effective energy management method. In this paper, we propose a new framework, I/O-GUARD, which reconstructs the system architecture of I/O virtualization, bringing a dedicated hardware hypervisor to handle resource management throughout the system. The hypervisor improves system real-time performance by enabling preemptive scheduling in I/O virtualization with both analytical and experimental real-time guarantees. Furthermore, we also present a dedicated energy management unit to adjustI/O-GUARD's dynamic energy using frequency scaling. Associated with that, a frequency identification algorithm is proposed to find the appropriate executing frequency at run-time. As shown in experiments,I/O-GUARDsimultaneously improves the predictability, performance and energy-efficiency compared to the state-of-the-art I/O virtualization.

Vehicle tracking, a core application to smart city video analytics, is becoming more widely deployed than ever before thanks to the increasing number of traffic cameras and recent advances in computer vision and machine-learning. Due to the constraints of bandwidth, latency, and privacy concerns, tracking tasks are more preferable to run on edge devices sitting close to the cameras. However, edge devices are provisioned with a fixed amount of computing budget, making them incompetent to adapt to time-varying and imbalanced tracking workloads caused by traffic dynamics. In coping with this challenge, we propose WatchDog, a real-time vehicle tracking system that fully utilizes edge nodes across the road network. WatchDog leverages computer vision tasks with different resource-accuracy tradeoffs, and decomposes and schedules tracking tasks judiciously across edge devices based on the current workload to maximize the number of tasks while ensuring a provable response time-bound at each edge device. Extensive evaluations have been conducted using real-world city-wide vehicle trajectory datasets, achieving exceptional tracking performance with a real-time guarantee.

In real-time embedded computing, time-predictability and performance are required simultaneously by memory transactions. However, with increasingly more elements being integrated into hardware, memory interconnects become a critical stumbling block to satisfying timing correctness, due to lack of hardware and scheduling scalability. In this paper, we propose a new hierarchically distributed memory interconnect, BlueScale, managing memory transactions using identical Scale Elements, which ensures hardware scalability. The Scale Element introduces two nested priority queues, achieving iterative compositional scheduling for memory transactions, guaranteeing transaction tasks' scheduling schedulability. Associated with the new architecture, a theoretical model is established to improve BlueScale's real-time performance.

Blind area has plagued drivers’ safety ever since the dawn of automobiles. Thanks to the fast-growing vision-based perception technologies, autonomous driving systems can monitor the driving circumstance through a 360-degree view, and hence most blind areas can be avoided. However, in the left turn scenario at an intersection, the opposite road may be blocked by another vehicle parking at the same intersection (see Fig. 1), and in this case, the blind area cannot be observed by the onboard perception module of the autonomous vehicle. A potential fatal collision may occur if the autonomous vehicle turns left while a vehicle is running through the blind area. In this paper, we propose Safecross, a framework that oversees an intersection and delivers blind area warnings to the left-turn vehicles at the intersection if running vehicles are detected in the blind area. In order to provide accurate and reliable real-time warnings in all possible weather conditions, the architecture of Safecross has four major components: video pre-processing (VP) module, video classification (VC) module, few-shot learning (FL) module, and model switching (MS) module. Especially, the VP and VC modules will train a basic model to identify the blind area when a blocking vehicle appears at the intersection. Since the range of the blind area varies in different weather conditions, the FL and MS modules can adapt the basic model to the new condition in real-time to make the blind area identification more accurate. Intuitively, if the blind area is identified timely and accurately, the left-turn throughput of the intersection can be maximized. We have conducted extensive experiments to evaluate our proposed framework. The experiments are performed on a total of 2855 video segments with a time span of 180 days, including sunny, rainy, and snowy weather conditions. Experimental results show how Safecross can guarantee the vehicle’s safety while increasing the left-turn traffic throughput by 50%.

Real-time Vehicle-of-Interest (VoI) detection is becoming a core application to smart cities, especially in areas with high accident rates. With the increasing number of surveillance cameras and the advanced developments in edge computing, video tasks prefer to run on edge devices close to cameras due to the constraints of bandwidth, latency, and privacy concerns. However, resource-constrained edge devices are not competent for dynamic traffic loads with resource-intensive video analysis models. To address this challenge, we propose RT-VeD, a real-time VoI detection system based on the limited resources of edge nodes. RT-VeD utilizes multi-granularity computer vision models with different resource-accuracy trade-offs. It schedules vehicle tasks based on a traffic-aware actor-critic framework to maximize the accuracy of VoI detection while ensuring an inference time-bound. To evaluate the proposed RT-VeD, we conduct extensive experiments based on a real-world vehicle dataset. The experiment results demonstrate that our model outperforms other competitive methods.

Real-time gang task scheduling has received much recent attention due to the emerging trend of applying highly parallel accelerators (e.g., GPU) and parallel programming models (e.g., OpenMP) in many real-time computing domains. However, existing works on gang task scheduling mainly focus on the preemptive scheduling case, which contradicts a bit with the non-preemptive executing nature of applying gang scheduling techniques in practice. In this paper, we present a set of non-trivial techniques that can analyze the schedulability of scheduling a hard real-time sporadic gang task system under non-preemptive GEDF on multiprocessors. A utilization-based schedulability test (first-of-its-kind) is derived, which is shown to be rather effective via experiments. Rather interestingly, for a special case where each gang task becomes an ordinary sporadic task, our developed test is shown by experiments that it improves schedulability by 75% on average upon a state-of-the-art utilization-based test designed for non-preemptive scheduling of ordinary sporadic tasks on multiprocessors.

Multi-sensor data fusion is essential in autonomous systems to support accurate perception and intelligent decisions. To perform meaningful data fusion, input data from different sensors must be sampled at time points in close propinquity to each other, otherwise the result cannot accurately reflect the status of the physical environment. ROS (Robotic Operating System), a popular software framework for autonomous systems, provides message synchronization mechanisms to address the above problem, by buffering messages carrying data from different sensors and grouping those with similar timestamps. Although message synchronization is widely used in applications developed based on ROS, little knowledge is known about its actual behavior and performance, so it is hard to guarantee the quality of data fusion. In this paper, we model the message synchronization policy in ROS and formally analyze its worst-case time disparity (maximal difference among the timestamps of the messages grouped into the same output set). We conduct experiments to evaluate the precision of the proposed time disparity upper bound against the maximal observed time disparity in real execution, and compare it with the synchronization policy in Apollo Cyber RT, another popular software framework for autonomous driving systems. Experiment results show that our analysis has good precision and ROS outperforms Apollo Cyber RT in terms of both observed worst-case time disparity and the theoretical bound.

We have witnessed the broad adoption of Deep Neu-ral Networks (DNNs) in autonomous vehicles (AV). As a safety-critical system, deadline-based scheduling is used to guarantee the predictability of the AV system. However, non-negligible time variations exist for most DNN models in an AV system, even when the whole system is just running one model. The fact that multiple DNNs are running on the same platform makes the time variations issue even more severe. However, none of the existing works have thoroughly studied the root cause of the time variation issue. In the first part of the paper, we conducted a comprehensive empirical study. We found that the inference time variations for a single DNN model are mainly caused by the DNN's multi-stage/multi-branch structure, which has a dynamic number of proposals or raw points. In addition, we found that the uncoordinated contention and cooperation are the roots of the time variations for multi-tenant DNNs inference. Second, based on these insights, we proposed the Prophet system that addresses the time variations in the AV perception system in two steps. The first step is to predict the time variations based on the intermediate results like proposals and raw points. The second step is coordinating the multi-tenant DNNs to ensure the execution progress is close to each other. From the evaluation results on the KITTI dataset, the time prediction of a single model all achieve higher than 91% accuracy for Faster R-CNN, LaneNet, and PINet. Besides, the perception fusion delay is bounded to 150ms, and the fusion drop ratio is reduced from 5.4% to less than 1 percent.

The real-time coscheduling problem, where tasks may have multiple phases executing on different types of processors, is known to be hard. The (already hard) self-suspending task scheduling simplifies the coscheduling problem by assuming that the latency a task may experience on the other type of processors is naturally bounded, which is unfortunately not true in practice. In this article, we present a novel analysis technique, namely, the vertical view analysis, for analyzing the schedulability of coscheduling sporadic tasks under global earliest-deadline-first (GEDF) on a heterogeneous multiprocessor consisting of two types of processors. We derive both hard (no deadline miss) and soft (bounded response times) real-time utilization-based tests. To the best of our knowledge, these results are the first-of-its-kind for the coscheduling problem and may allow real-time schedulability analysis to be carried out on more practical scenarios under heterogeneous computing.

For safety-critical| computer systems, time-predictability and performance are usually required simultaneously in I/O virtualization. However, both requirements are challenging to achieve due to complex I/O access path and resource management at system level and lack of support from preemptive scheduling at I/O hardware level. In this paper, we propose a new framework, I/O-GUARD, which reconstructs the system architecture of I/O virtualization, bringing a dedicated hardware hypervisor to handle resource management throughout the system. The hypervisor improves system real-time performance by enabling preemptive scheduling in I/O virtualization with both analytical and experimental real-time guarantees. Specifically, I/O-GUARD is a First-of-Its-Kind framework for multi-/many-core I/O virtualization.

We are witnessing a rapid taxi electrification process due to the ever-increasing concern about urban air quality and energy security. A key difference between conventional gas taxis and electric taxis is their energy replenishment mechanisms, i.e., refueling or charging, which is reflected in two aspects: (i) much longer charging processes vs. short refueling processes and (ii) time-varying electricity prices vs. time-invariant gasoline prices during a day. The complicated charging issues (e.g., long charging time and dynamic charging pricing) potentially reduce electric taxis' daily operation time and profits, and also cause overcrowded charging stations during some off-peak charging pricing periods. Motivated by a set of findings obtained from a data-driven investigation, in this paper, we design a fairness-aware vehicle displacement system called FairMove to improve the overall profit efficiency and profit fairness of electric taxi fleets by considering both the passenger travel demand and taxi charging demand. We first formulate the electric taxi displacement problem as multi-agent deep reinforcement learning, and then we propose a centralized multi-agent actor-critic approach to tackle this problem. More importantly, we implement and evaluate FairMove with real-world streaming data from the Chinese city Shenzhen, including GPS data and transaction data from more than 20,100 electric taxis, coupled with the data of 123 charging stations, which constitute, to our knowledge, the largest all-electric taxi network in the world. The extensive experimental results show that our fairness-aware FairMove effectively improves the profit efficiency and profit fairness of the Shenzhen electric taxi fleet by 25.2% and 54.7%, respectively.

Electric carsharing, i.e., electric vehicle sharing, as an emerging mobility-on-demand service, has been proliferating worldwide recently. Though providing convenient, low-cost, and environmentally-friendly mobility, there are also some potential roadblocks in electric carsharing services due to existing inefficient fleet management strategies, which relocate the vehicles using predefined periodic schedules without self-adapting to the highly dynamic user demand, and many practical factors like time-variant charging pricing also have not been fully considered. To remedy these problems, in this paper, we design Record, an effective fleet management system with joint Repositioning and Charging for electric carsharing based on dynamic deadlines to improve its operating profits and also satisfy users' real-time pickup and return demand. Record considers not only the highly dynamic user demand for vehicle repositioning (i.e., where to relocate) but also the time-varying charging pricing for charging scheduling (i.e., where to charge). To perform the two tasks efficiently, in Record, we design a dynamic deadline-based distributed deep reinforcement learning algorithm, which generates dynamic deadlines via usage prediction combined with an error compensation mechanism to adaptively search and learn the optimal locations for satisfying highly dynamic and unbalanced user demand in real time. We implement and evaluate the Record system with 10-month real-world electric carsharing data, and the extensive experimental results show that our Record effectively reduces 25.8% of charging costs and reduces 30.2% of vehicle movements by workers, and it also satisfies user demand and achieves a small runtime overhead at the same time.

In modern, real-time heterogeneous systems, ensuring the predictability of interconnects is becoming increasingly important. Existing interconnects are mainly designed to achieve high throughput, with their micro-architectures usually based on FIFO queues. This FIFO-based design prevents prioritization of transactions based on their importance, leading to difficulties in ensuring transaction predictability, especially in a system with a large number of system components. In this paper, we introduce AXI-InterconnectRT, a real-time AXI interconnect for heterogeneous SoCs, which redefines the micro-architecture of interconnects by enabling random accesses of buffered transactions and organizing transactions using dedicated hardware units. With the new micro-architecture, AXI-InterconnectRTcan manage transactions based on their importance, guaranteeing their predictability.

The well-known influence maximization problem (IM) aims at maximizing the influence of one information cascade in a social network by selecting appropriate seed users prior to the diffusion process. In its adaptive version, additional seed users can be selected after observing certain diffusion results. On the other hand, social computing tasks are often time-critical, and therefore, only the influence resulted in the early period is worthwhile, which can be naturally modeled by enforcing a time constraint. In this article, we present an analysis of the time-constrained adaptive IM problem. On the theory side, we provide the hardness results of computing the optimal policy and a lower bound on the adaptive gap, which measures the superiority of adaptive policies over the nonadaptive policies. For practical solutions, from basic to advanced, we design a series of seeding policies for achieving high efficacy and scalability. Finally, we investigate the proposed solutions through extensive simulations based on real-world data sets.

Accurate and pervasive device-free indoor localization with meter-level resolution is critical for large cruise and passenger ships due to safety-critical rescue and evacuation requirements when accidents occur. However, existing localization techniques would severely suffer on ships because of their unique mobility characteristics. In this paper, we take the first attempt to build a ubiquitous passive localization system using WiFi fingerprints for the mobile ship environment. By conducting extensive experiments and measurements during several cruise trips, we identified a major influence factor on the fingerprints in the mobile environment: varying the ship speeds may significantly change the patterns of fingerprints at runtime. Since it may be too expensive to identify the fingerprints associated with different speeds, we propose an efficient localization method, namely SWIM, which calibrates the fingerprints from only a single-speed scenario to multiple-speed scenarios using a signal reconstruction analysis. SWIM is designed to learn the predictive fingerprint variation introduced by environmental speed changes and reconstruct the original fingerprints to adapt to the runtime speed scenarios. We have implemented and extensively evaluated SWIM on actual cruise ships. Experimental results demonstrate that SWIM improves localization accuracy from 63.2 to 82.9 percent, while reducing the overall system deployment cost by 87 percent.

Following the trend of increasing autonomy in cyber-physical systems, parallel embedded architectures have enabled devices to better handle the large streams of data and intensive computation required by such autonomous systems. However, while the explosion of highly-parallel platforms has seen a proportional growth in the number of applications/devices that utilize these platforms, the embedded systems community's understanding of how to build time-predictable, safety-critical systems with parallel platforms has not kept pace. As a well-motivated but challenging parallel scheduling model, gang scheduling requires all parallel threads of each parallel task to simultaneously execute in unison, which is in contrast to traditional, multi-threaded parallel scheduling, where a parallel task may spawn multiple threads, and each thread will be scheduled independently of other threads of the same task. While increasing research efforts on hard real-time (HRT) gang scheduling have recently been seen, the problem of gang scheduling in the context of soft real-time (SRT) systems, where provably bounded deadline tardiness can be tolerated, has hardly been studied yet. In this article, we derive and prove the first tardiness bounds for sporadic gang task systems under preemptive GEDF scheduling. A total utilization bound for SRT-schedulability is required for ensuring such tardiness bounds but it is shown to be tight with respect to the platform capacity and maximum parallelism-induced idleness. Furthermore, we also empirically evaluate the effects of different degrees of task parallelism upon the SRT-schedulability.

In order to mitigate the pessimism in parameter estimation in real-time systems, mixed-criticality (MC) scheduling has been proposed and studied. In light of the first MC scheduling work focusing on multiple estimates on the worst-case execution times (WCETs), a few following works also have extended this approach to other dimensions, such as periods, relative deadlines, and processor speeds. Nonetheless, in most existing work on MC scheduling, a flat-structured scheduling approach is assumed, whereas compositional real-time systems with hierarchical scheduling are of great interest, especially for large-scale real-time systems. In this work, we aim to extend the fundamental ideas and frameworks of MC scheduling to another dimension, namely the budget estimation. To illustrate this approach, we form up a specific scheduling problem in the context of a single virtual processor characterized by the periodic resource model and propose a virtual-deadline-based algorithm to solve it. Furthermore, we have developed a polynomial-time schedulability test and have proved a speed-up bound for the proposed algorithm. We have also derived a range for setting the resource period to ensure schedulability when the bandwidth and task set are given. Moreover, we have conducted schedulability studies and presented our simulation experiment results to evaluate the proposed model and algorithm.

In mixed-criticality systems, mode switch is a key strategy which dynamically provides a balance between system performance and safety. In conventional MCS frameworks, mode switch is triggered by the over-execution of a task; i.e., a task overruns the less pessimistic worst-case execution time. In cyber-physical systems, the data volume generated by I/O affects and can even dominate task computation time. With this in mind, we introduce a novel MCS architecture, termed Pythia-MCS, which predicts task execution time according to I/O run-time behaviors. With the new feature of future-prediction, the Pythia-MCS provides more timely, but still accurate, mode switch. We also present a new theoretical model (quarter-clairvoyance), which guarantees the timing predictability of the design, and a new schedulability analysis for the Pythia-MCS, which demonstrates improved schedulability compared to conventional MCS frameworks. The Pythia-MCS is the first MCS framework enabling the clairvoyance functionality.

Device-free indoor localization may play a critical role in improving passengers' safety in large vessels, particularly for scenarios without equipped radios. However, due to dynamic internal and external influences from the sailing ship such as changing sailing speed, the existing localization systems suffer huge accuracy degradation in a mobile ship environment. The challenges are mainly due to rich and arbitrary ship motions and the resulting complicated impacts on the indoor wireless channels. To address the challenges, in this article, we first propose a ship motion descriptor to extract discriminative latent representation from complex ship motions by leveraging deep-learning techniques. Based on this representation, we then design a novel fingerprint roaming model, i.e., MoLoc, to automatically learn the predictive fingerprint variation pattern and transfer the online fingerprint measurement to adapt to dynamic ship motions in real time. Furthermore, an unsupervised learning strategy is proposed to train the fingerprint roaming model using unlabeled onboard collected data which do not incur any labor costs. We have implemented and extensively evaluated MoLoc on real-world cruise ships, where experimental results demonstrate that MoLoc improves localization accuracy from 63.2% to 92.8% compared to the state-of-the-art localization methods, including Pilot, LiFS, SpotFi, and AutoFi while achieving a mean error of 0.68 m.

The scheduling and schedulability analysis of real-time directed acyclic graph (DAG) task systems have received much recent attention. The DAG model can accurately represent intra-task parallelism and precedence constraints existing in many application domains. Existing techniques show that analyzing the DAG model is fundamentally more challenging compared to the ordinary sporadic task model, due to the complex intra-DAG precedence constraints which may cause rather pessimistic schedulability loss. However, such increased loss is counter-intuitive because the DAG structure shall better exploit the hardware parallelism provided by the multiprocessor platform. Our key observation is that the intra-DAG precedence constraints, if not carefully considered by the scheduling algorithm, may cause unpredictable execution behaviors of sub-tasks in a DAG and thus pessimistic analysis. In this paper, we present a set of novel scheduling and analysis techniques for better supporting hard real-time sporadic DAG tasks on multiprocessors, through smartly defining and analyzing the execution order of subtasks in each DAG. Combined with a new DAG-specific interval analysis framework, the proposed subtask ordering technique leads to a highly efficient utilization-based schedulability test. Importantly, the developed test becomes identical to the classical density test designed for the sporadic task model, if each DAG in the system has an out-degree of one (i.e., only containing a chain of subtasks). Experiments show the efficiency of the developed test, which improves schedulability upon existing utilization-based tests by over 60% on average and is often able to guarantee schedulability with little utilization loss.

Existing works on gang task scheduling mainly focus on the preemptive scheduling case, which contradicts a bit with the non-preemptive executing nature of applying gang scheduling techniques in practice. In this paper, we present a set of non-trivial techniques that can analyze the schedulability of scheduling a hard real-time sporadic gang task system under non-preemptive GEDF on multiprocessors and a utilization-based schedulability test (first-of-its-kind) is derived.

Much recent work has been conducted on supporting soft real-time tasks on multiprocessors due to the multicore revolution. While most earlier works focus on the traditional sporadic task model with deterministic worst-case specification, several recent works investigate the stochastic nature of many workloads seen in practice, specifying task execution times using average-case provisioning instead of the worst case. Unfortunately, all the existing work on supporting soft real-time workloads ignores a simple practical fact that the job inter-arrival time (or task period) is also stochastic for many real-world applications. Adopting a fixed worst-case period to model all the arriving pattern is rather pessimistic and may result in significant capacity loss in practice. Based on these observations, we present a general soft real-time multiprocessor schedulability analysis framework in this paper for practical sporadic task systems specified by stochastic period and execution demand, following probability distributions. Our analysis can be generally applied to global tunable priority-based schedulers, which allow any job's priority to be changed dynamically at runtime within a priority window of constant length. We have extensively evaluated the analysis framework using a MPEG video decoding case study and simulation-based experiments. Experimental results demonstrate significant advantages of our analysis, which yields over 200 and 50 percent improvements compared to existing analysis assuming worst-case task periods in terms of schedulability and magnitude of the derived tardiness bound, respectively.

This paper studies the problem of scheduling a set of hard real-time sporadic tasks that may access CPU cores and a shared resource. Motivated by the observation that the CPU resource is often abundant compared to the shared resources in multi-core and many-core systems, we propose to resolve this problem from a counter-intuitive shared-resource-centric perspective, focusing on judiciously prioritizing and scheduling tasks' requests in a limited preemptive manner on the shared resource while viewing the worst-case latency a task may experience on the CPU cores as suspension delays. We develop a rather comprehensive set of task partitioning algorithms that partition tasks onto the shared resource with the objective of guaranteeing schedulability while minimizing the required size of the shared resource, which plays a critical role in reducing the overall cost and complexity of building resource-constrained embedded systems in many application domains. A GPU-based prototype case study and extensive simulation-based experiments have been conducted, which validate both our shared-resource-centric scheduling philosophy and the efficiency of our suspension-based partitioning solutions in practice.

We consider the problem of globally scheduling hard real-time sporadic DAG task systems on multiprocessors. Existing techniques show that analyzing the DAG model is fundamentally more challenging compared to the ordinary sporadic task model, due to the complex intra-DAG precedence constraints which may cause rather pessimistic schedulability loss. However, such increased loss is counterintuitive because the DAG structure shall better exploit the parallelism provided by the multiprocessor platform. In this work, we present a set of novel scheduling and analysis techniques for better supporting hard real-time sporadic DAG tasks on multiprocessors, through smartly defining and analyzing the execution order of subtasks in each DAG. Interestingly, when each DAG task only contains a single subtask, the proposed utilization-based schedulability test becomes identical to the density test.

Heterogeneous computing platforms with multiple types of computing resources have been widely used in many industrial systems to process dataflow tasks with pre-defined affinity of tasks to subgroups of resources. For many dataflow workloads with soft real-time requirements, guaranteeing fast and bounded response times is often the objective. This paper presents a new set of analysis techniques showing that a classical real-time scheduler, namely earliest-deadline first (EDF), is able to support dataflow tasks scheduled on such heterogeneous platforms with provably bounded response times while incurring no resource capacity loss, thus proving EDF to be an optimal solution for this scheduling problem. Experiments using synthetic workloads with widely varied parameters also demonstrate that the magnitude of the response time bounds yielded under the proposed analysis is reasonably small under all scenarios. Compared to the state-of-the-art soft real-time analysis techniques, our test yields a 68% reduction on response time bounds on average. This work demonstrates the potential of applying EDF into practical industrial systems containing dataflow-based workloads that desire guaranteed bounded response times.

1This paper answers several open questions of practical concerns to schedule soft real-time (SRT) tasks, to guarantee their bounded tardiness, under fixed-priority scheduling in homogeneous multiprocessor systems. We consider both cases with only SRT tasks and with mixed sets of SRT and hard real-time (HRT) tasks. For the case in which the system has only SRT tasks, we show that any fixed priority assignment policy yields a capacity augmentation factor of 2−1/M where M is the number of processors. We prove the optimality of the utilization-monotonic (UM) priority assignment (i.e., assigning higher priorities to high-utilization tasks) under our sufficient test for guaranteeing bounded tardiness. We show that UM priority assignment can yield a utilization bound of M+1/2M, which is shown asymptotically the best possible bound. For the case in which the system has mixed SRT and HRT tasks, we present two new fixed-priority assignment algorithms and their associated schedulability tests. One is a clustering-based greedy priority assignment policy and another is based on Audsley's optimal priority assignment (OPA) approach. We show that the utilization bounds, augmentation factors, and speedup factors are still maintained by the hard real-time cases. Therefore, introducing soft real-time tasks does not create additional problems (at least in those metrics) for scheduling if the priority assignments are properly done. As demonstrated by extensive experiments, these two policies yield reasonably good performance overall and much better performance than the deadline-monotonic priority assignment.

This paper studies the problem of scheduling hard real-time sporadic gang task systems under global earliest-deadline-first, where a gang application's threads need to be concurrently scheduled on distinct processors. A novel approach combining new lag-based reasoning and executing/non-executing gang interval analysis technique is introduced, which is able to characterize the parallelisminduced idleness, as a key challenge of analyzing gang task schedules. To the best of our knowledge, this approach yields the first utilization-based test for hard real-time gang task systems.

Due to the energy security concern, our society is witnessing a surge of EV fleet applications, e.g., public EV taxi fleet systems. A major issue impeding an even more widespread adoption of EVs is range anxiety, which is due to several factors including limited battery capacity, limited availability of battery charging stations, and long charging time compared to traditional gasoline vehicles. By analyzing our accessible real-world EV taxi system-wide datasets, we observe that current EV taxi drivers often suffer from unpredictable, long waiting times at charging stations, due to temporally and spatially unbalanced utilization among charging stations. This is mainly because current taxi fleet management system simply rely on taxi drivers to make charging decisions. In this paper, In this paper, we develop REC, a Real-time Ev Charging scheduling framework for EV taxi fleets, which informs each EV taxi driver at runtime when and where to charge the battery. REC is able to analytically guarantee predictable and tightly bounded waiting times for all EVs in the fleet and temporally/spatially balanced utilization among charging stations, if each driver follows the charging decision made by REC. Moreover, REC can further efficiently handle real-life issues, e.g., allowing a taxi driver to charge at its preferred charging station while still guaranteeing balanced charging station utilization.We have extensively evaluated REC using our accessible real-world EV taxi system-wide datasets. Experimental results show that REC is able to address the unpredictability and unbalancing issues existing in current EV taxi fleet systems, yielding predictable and tightly bounded waiting times, and equally important, temporally/spatially balanced charging station utilization.

Micro-powered wireless embedded devices are widely used in many application domains. Their efficiency in practice, however, is significantly constrained by the dual limitations of low harvesting rates and tiny energy buffer. Recent research presents a network stack that efficiently fragments a large packet into many smaller packets that can fit within the available energy in the energy buffer of limited size. While this fragmentation technique represents a major step forward in solving the minuscule energy budget problem, it also introduces a tremendous practical challenge where potentially many fragmented packets belonging to different devices may contend for the communication channel. Designing purely heuristic-based packet transmission protocol is undesirable because the resulting per-packet and end-to-end transmission delay are unknown, thus causing unpredictable system performance which is unacceptable for many applications with real-time constraints. In this paper, we first formulate this packet transmission scheduling problem considering physical properties of the charging and transmission processes. We then develop a novel packet prioritization and transmission protocol NERF that yields tight and predictable delay bounds for transmitting packets from multiple micropowered devices to a charger. We have implemented our protoco on top of the WISP 4.1 platform and the SPEEDWAY RFID READER, and conducted validation experiments. Our experiments validate the correctness of our implementation and show that NERF can reduce the total collection delay by 40% when compared to an existing protocol ALOHA. We have also performed extensive data trace-driven simulations. Simulation results demonstrate the effectiveness of our proposed protocol. On average, our protocol yields an over 30%improvement in terms of runtime transmission delay compared to existing methods, while being able to guarantee tight and provable response time bounds.

This paper studies the problem of scheduling hard real-time sporadic suspending task systems under global earliest-deadline-first. A novel selective suspension-tocomputation conversion approach has been developed, with the fundamental idea of selecting and converting a limited set of jobs' suspensions into computation to eliminate suspension-induced pessimism in the analysis. To the best of our knowledge, this approach yields the first utilization-based test for globally-scheduled suspending task systems, which analytically dominates the suspension-oblivious approach and dramatically improves schedulability upon existing tests by over 50% on average, as shown by experiments. We believe this paper closes the loop on applying the methodology of selective suspension-to-computation conversion to analyze realtime suspending task systems.

Wireless rechargeable sensor networks have recently emerged as a promising platform that can effectively solve the power constraint problem suffered by traditional battery powered systems. The problem of determining the best charging routes for maximizing charging efficiency has been studied extensively. However, the task assignment problem, which plays a crucial role in efficiently utilizing the harvested energy and thus minimize the charging delay, has received rather limited attention. In this paper, we study the problem of assigning a given set of tasks in a wireless rechargeable sensor network while maximizing the charger's velocity to minimize the charging delay. We first propose an online task assignment algorithm, namely Lower Bound assignment (LB), that yields a quantifiable lower bound on the charging velocity while guaranteeing a feasible assignment. This algorithm further enables the transformation of our considered task assignment problem into a variation of the classical multiple knapsack problem. We then present a fully polynomial-time approximation scheme with a (2+ε)-approximation ratio, namely ACT, that is built upon an existing greedy algorithm designed for the original knapsack problem. Extensive experimental results presented herein demonstrate that ACT is able to achieve near-optimal performance in most cases, and can achieve more than 15% performance improvement compared to the baseline algorithms.

We study the Relay-based Cooperative Data Exchange (RCDE) problem, where initially each client has access to a subset of a set of n original packets, referred to as their side information, and wants to retrieve all other original packets via cooperation. Unlike traditional Cooperative Data Exchange (CDE), in our proposed relay-based model, clients can only cooperate via a relay. The data exchange is completed over two phases, namely Uploading Phase and Downloading Phase. In the Uploading Phase, the clients will encode the original packets and transmit the coded packets to the relay. In the Downloading Phase, the relay will reencode the received packets and multicast the reencoded packets, each to a subgroup of clients. The coded packets in the two phases are carefully selected so that each client can retrieve all n original packets with minimum total transmission delay, based on its initial side information and on the coded packets it receives from the relay. In addition, we assume that the bandwidths between the relay and different clients are different, and that the upload/download bandwidths between the relay and the same client are also different. We establish a coding scheme that has the minimum total delay and show that it can be found in polynomial time, for sufficiently large underlying fields. We also design a heuristic algorithm that has a low complexity with binary field size. Our simulations show that the performance of the binary solution is very close to that of the optimal solution. All coding schemes considered in this work are scalar.

Smartphones and mobile devices have greatly penetrated the daily lives of many people. While participatory/pervasive sensing has gained wide adoptions by leveraging various onboard sensors on mobile devices, another powerful resource, the computational power on these mobile devices has been less frequently harnessed by researchers and practitioners. To fill this gap, we propose in this work the modeling, analysis, and implementation of participatory computing. Specifically, we propose REPC, a generic randomized task assignment framework for the participatory computing paradigm, which guarantees the overall system performance with close to minimal workload at individual participating devices. To achieve these design objectives, we model the intrinsic relationship between the workload of individual devices and the probability they complete their assigned tasks. Based on our modeling results, we analyze the maximal system capacity for any given participatory computing system and derive the minimal workload for individual participating devices to achieve the overall system performance requirement. We have fully implemented our design on the Android platform and demonstrated its performance through a representative participatory computing application. Extensive experiments and simulation results demonstrate that our design is able to achieve more than 90% task completion ratios with only 10% system overhead in practice.

We show that given n and k, for q sufficiently large, there always exists an [n, k]qMDS code that has a generator matrix G satisfying the following two conditions: (C1) Sparsest: each row of G has Hamming weight n - k + 1; (C2) Balanced: Hamming weights of the columns of G differ from each other by at most one.

Participatory Computing is a promising solution to fully utilize the wasted computation resources of mobile devices such as smartphones. In this demo abstract, we present our design and implementation of an participatory computing enhanced pervasive surveillance system. Our evaluation results show that the proposed system can effectively utilize the computation capability of mobile devices while guaranteeing the service reliability even with the intermittent nature of participatory computing.

In this paper, we consider the problem of minimizing the delay for data exchange among a group of wireless clients, where each client initially holds a subset of the packets and needs to get all the packets held by other clients. It is assumed that clients cannot communicate with each another directly, they can only exchange packets through a wireless relay. To minimize the total transmission delay during data exchange process, we need to determine at every client, which packets to be uploaded and how to encode the packets. It is also important for the relay node to decide how to encode multiple packets from different clients and select the transmission rate in the downloading process, such that every client can decode all required packets in shortest delay. We first formulate theoretically the above problem of minimizing the total transmission delay as an integer programming, and show that its complexity is NP hard. We then propose an efficient heuristic algorithm, which consists of two processes: uploading process, i.e., how to select and encode the packets from the clients to the relay, and downloading process, i.e., how the relay encode packets and select transmission rate for broadcast to all clients. For each process, theoretical formulation has been derived to minimize their transmission delay, and efficient algorithms are proposed separately. Finally, simulation results demonstrate the effectiveness of the proposed algorithm in reducing the total data exchange delay.