Self-powered vehicles that interact with the physical world, such as spacecraft, require computing platforms with predictable timing behavior and a low energy demand. Energy consumption can be reduced by choosing energy-efficient designs for both hardware and software components of the platform. We leverage the state-of-the-art in energy-efficient hardware design by adopting Heterogeneous Multi-core Processors with support for Dynamic Voltage and Frequency Scaling and Dynamic Power Management. We address the problem of allocating real-time software components onto heterogeneous cores such that total energy is minimized. Our approach is to start from an analytically justified target load distribution and find a task assignment heuristic that approximates it. Our analysis shows that neither balancing the load nor assigning all load to the “cheapest” core is the best load distribution strategy, unless the cores are extremely alike or extremely different. The optimal load distribution is then formulated as a solution to a convex optimization problem. A heuristic that approximates this load distribution and an alternative method that leverages the solution explicitly are proposed as viable task assignment methods. The proposed methods are compared to state-of-the-art on simulated problem instances and in a case study of a soft-real-time application on an off-the-shelf ARM big.LITTLE heterogeneous processor.

Many modern multi-core processors sport a large shared cache with the primary goal of enhancing the statistic performance of computing workloads. However, due to resulting cache interference among tasks, the uncontrolled use of such a shared cache can significantly hamper the predictability and analyzability of multi-core real-time systems. Software cache partitioning has been considered as an attractive approach to address this issue because it does not require any hardware support beyond that available on many modern processors. However, the state-of-the-art software cache partitioning techniques face two challenges: (1) the memory co-partitioning problem, which results in page swapping or waste of memory, and (2) the availability of a limited number of cache partitions, which causes degraded performance. These are major impediments to the practical adoption of software cache partitioning. In this paper, we propose a practical OS-level cache management scheme for multi-core real-time systems. Our scheme provides predictable cache performance, addresses the aforementioned problems of existing software cache partitioning, and efficiently allocates cache partitions to schedule a given task set. We have implemented and evaluated our scheme in Linux/RK running on the Intel Core i7 quad-core processor. Experimental results indicate that, compared to the traditional approaches, our scheme is up to 39% more memory space efficient and consumes up to 25% less cache partitions while maintaining cache predictability. Our scheme also yields a significant utilization benefit that increases with the number of tasks.

Extensive research is underway to build chips with potentially hundreds of cores. In this paper, we consider the problem of scheduling periodic real-time tasks on multi-core processors. We develop a task partitioning algorithm called Period-Compatible-Allocation and Task-Splitting (pCOMPATS) for fixed-priority scheduling of preemptive hard real-time tasks where the utilization of each of the tasks is less than 50%. pCOMPATS clusters compatible tasks together with task splitting to improve the achievable utilization. We show that as the number of cores increases, the least upper bound on schedulable utilization achieved using pCOMPATS approaches 100% per core. To the best of our knowledge, this is the first result that shows that the utilization bound improves as the number of processing cores in the system increases. We refer to tasks having utilization greater than or equal to 50% as heavy tasks and provide a task-partitioning algorithm called pCOMPATS-HT for allocating such tasks. We show that the upper bound on schedulable utilization when tasks are scheduled using pCOMPATS-HT is at most 72%. We also evaluate the performance of pCOMPATS and other well-known partitioning techniques, and show that using pCOMPATS provides much better schedulable utilization in the average case. We characterize the overhead of pCOMPATS using measurements on an Intel Core i7 processor running Linux/RK. The overheads are seen to be low on the platform, making pCOMPATS to be practical. Our results are especially useful in the context of future many-core processors with dozens to hundreds of cores per processor.

Current spacecraft systems generally have monolithic structures, but a "fractionated" architecture is being considered for next generation spacecrafts. A fractionated spacecraft system is a cluster of independent modules that communicate wirelessly to maintain cluster flight formations and realize the functions usually performed by a monolithic satellite. The envisioned benefits of the fractionated approach include enhanced responsiveness, greater flexibility, robustness and co-existence of multiple missions from different sources with varying degree of trust. The fractionated architecture, however, introduces significant new challenges from the perspective of resource allocation and management. The mobile nature of the clusters and the modules within the cluster implies that the network topology is highly time-varying. A cluster with multiple missions can require messages to be transmitted across the network with varying degrees of QoS requirements such as timeliness and data delivery reliability. The system must determine the appropriate and timely resource allocation for these missions. In this paper, we address these resource allocation challenges by introducing an abstraction of dynamic graphs, and extending the QoS based Resource Allocation Model (Q-RAM) to operate on these dynamic graphs. We develop a mechanism to decompose a dynamic graph into multiple static sub-graphs using which the resource allocation problem is partitioned into multiple sub-problems within each of these static sub-graphs. We have experimentally evaluated our solution by building a simulation framework called SatSim, which can handle a variety of satellite configurations and mobility models. The proposed solution is shown to achieve a near-optimal solution for the resource allocation problem in time-varying networks, while reducing time complexity significantly.

Energy management is becoming an increasingly important problem in application domains ranging from embedded devices to data centers. In many such systems, multi-core processors are projected as a promising technology to achieve improved performance with a lower power envelope. Managing the application power consumption under timing constraints poses significant challenges in these emerging platforms. In this paper, we study the energy-efficient scheduling of periodic real time tasks with implicit deadlines on chip multi-core processors (CMPs). We specifically consider processors with a single voltage and clock frequency domain, such as the state-of-the-art embedded multi-core NVIDIA Tegra 2processor and enterprise-class processors such as Intel'sItanium 2, i5, i7 and IBM's Power 6 and Power 7series. The major contributions of this work are (i)we prove that Worst-Fit-Decreasing (WFD) task partitioning when Rate-Monotonic Scheduling (RMS) is used has an approximation ratio of 1.71 for the problem of minimizing the schedulable operating frequency with partitioned fixed-priority scheduling, (ii) we illustrate the major shortcoming of WFD with RMS resulting from not considering task periods during allocation, and(iii) we propose a Single-clock domain multi-processor Frequency Assignment Algorithm (SFAA) that determines a globally energy-efficient frequency while including task period relationships. Our evaluation results show that SFAA provides significant energy gains when compared to WFD. In fact SFAA is shown to save up to 55% more power compared to WFD for an octa-core processor.

Mobile sensor nodes can be used for a wide variety of applications such as social networks and location tracking. An important requirement for all such applications is that the mobile nodes need to actively discover their neighbors with minimal energy and latency. Nodes in mobile networks are not necessarily synchronized with each other, making the neighbor discovery problem all the more challenging. In this paper, we propose a neighbor discovery protocol called U-Connect, which achieves neighbor discovery at minimal and predictable energy costs while allowing nodes to pick dissimilar duty-cycles. We provide a theoretical formulation of this asynchronous neighbor discovery problem, and evaluate it using the power-latency product metric. We analytically establish that U-Connect is an 1.5-approximation algorithm for the symmetric asynchronous neighbor discovery problem, whereas existing protocols like Quorum and Disco are 2-approximation algorithms. We evaluate the performance of U-Connect and compare the performance of U-Connect with that of existing neighbor discovery protocols. We have implemented U-Connect on our custom portable FireFly Badge hardware platform. A key aspect of our implementation is that it uses a slot duration of only 250μs, and achieves orders of magnitude lower latency for a given duty cycle compared to existing schemes for wireless sensor networks. We provide experimental results from our implementation on a network of around 20 sensor nodes. Finally, we also describe a Friend-Finder application that uses the neighbor discovery service provided by U-Connect.

In recent years, there has been an increase in video surveillance systems in public and private environments due to a heightened sense of security. The next generation of surveillance systems will be able to annotate video and locally coordinate the tracking of objects while multiplexing hundreds of video streams in real-time. In this paper, we present OmniEye, a wireless distributed real-time surveillance system composed of wireless smart cameras. OmniEye is comprised of custom-designed smart camera nodes called DSPcams that communicate using an IEEE 802.11 mesh network. These cameras provide wide-area coverage and local processing with the ability to direct a sparse number of high-resolution pan, tilt and zoom (PTZ) cameras that can home onto targets of interest. Each DSPcam performs local processing to help classify events and pro-actively draw an operator's attention when necessary. In video-streaming applications, maintaining high network utilization is required in order to maximize image quality as well as the number of cameras. Our experiments show that by using the standard 802.11 DCF MAC protocol for communication, the system does not scale beyond 5-6 cameras while each camera is streaming at 1 Mbps. Also, we see high levels of jitter in video transmissions. This performance degrades further for multi-hop scenarios due to the presence of hidden nodes. In order to improve the system's scalability and reliability, we propose a Time-Synchronized Application- level MAC protocol (TSAM) capable of operating on top of existing 802.11 protocols using commodity off-the-shelf hardware. Through analysis and experimental validation, we show how TSAM is able to improve throughput and provide bounded delay. Unlike traditional CSMA-based systems, TSAM gracefully degrades in a fair manner so that existing streams can still deliver data.