In recommender systems based on low-rank factorization of a partially observed user-item matrix, a common phenomenon that plagues many otherwise effective models is the interleaving of good and spurious recommendations in the top-K results. A single spurious recommendation can dramatically impact the perceived quality of a recommender system. Spurious recommendations do not result in serendipitous discoveries but rather cognitive dissonance. In this work, we investigate folding, a major contributing factor to spurious recommendations. Folding refers to the unintentional overlap of disparate groups of users and items in the low-rank embedding vector space, induced by improper handling of missing data. We formally define a metric that quantifies the severity of folding in a trained system, to assist in diagnosing its potential to make inappropriate recommendations. The folding metric complements existing information retrieval metrics that focus on the number of good recommendations and their ranks but ignore the impact of undesired recommendations. We motivate the folding metric definition on synthetic data and evaluate its effectiveness on both synthetic and real world datasets. In studying the relationship between the folding metric and other characteristics of recommender systems, we observe that optimizing for goodness metrics can lead to high folding and thus more spurious recommendations.

Noisy, high-dimensional time series observations can often be described by a set of low-dimensional latent variables. Commonly used methods to extract these latent variables typically assume instantaneous relationships between the latent and observed variables. In many physical systems, changes in the latent variables manifest as changes in the observed variables after time delays. Techniques that do not account for these delays can recover a larger number of latent variables than are present in the system, thereby making the latent representation more difficult to interpret. In this work, we introduce a novel probabilistic technique, time-delay gaussian-process factor analysis (TD-GPFA), that performs dimensionality reduction in the presence of a different time delay between each pair of latent and observed variables. We demonstrate how using a gaussian process to model the evolution of each latent variable allows us to tractably learn these delays over a continuous domain. Additionally, we show how TD-GPFA combines temporal smoothing and dimensionality reduction into a common probabilistic framework. We present an expectation/conditional maximization either (ECME) algorithm to learn the model parameters. Our simulations demonstrate that when time delays are present, TD-GPFA is able to correctly identify these delays and recover the latent space. We then applied TD-GPFA to the activity of tens of neurons recorded simultaneously in the macaque motor cortex during a reaching task. TD-GPFA is able to better describe the neural activity using a more parsimonious latent space than GPFA, a method that has been used to interpret motor cortex data but does not account for time delays. More broadly, TD-GPFA can help to unravel the mechanisms underlying high-dimensional time series data by taking into account physical delays in the system.

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.

Cyber-physical systems are an emerging class of applications that require tightly coupled interaction between the computational and physical worlds. These systems are typically realized using sensor/actuator interfaces connected with processing backbones. Safety is a primary concern in cyber-physical systems since the actuators directly influence the physical world. However, unexpected or unusual conditions in the physical world can manifest themselves as increased workload demands being offered to the computational infrastructure of a cyber-physical system. Guaranteeing system safety under overload conditions is therefore a prime concern in developing and deploying cyber-physical systems. In this work, we study this problem in the context of a radar surveillance system, where tasks have different levels of criticality or influence on system safety . In the face of overloads, we observe that the desirable property in such systems is that the more critical tasks continue to meet their timing requirements. We capture this mixed-criticality overload requirement using a formal overload-tolerance metric called ductility . Using this overload-tolerance metric, we first develop our solution in the context of uniprocessor systems, where we show that Zero-Slack scheduling (ZS) algorithms can be used to improve the overload behavior in mixed-criticality cyber-physical systems compared to existing fixed-priority scheduling algorithms like Rate-Monotonic Scheduling (RMS) and Criticality-As-Priority-Assignment (CAPA). Leveraging these results, we then develop a criticality-aware task allocation algorithm called Compress-on-Overload Packing (COP) for dealing with multiprocessor cyber-physical systems. Evaluation results show that COP achieves up to five times better ductility than traditional load balancing bin-packing algorithms like Worst-Fit Decreasing (WFD). Finally, we apply ZS and COP to the radar surveillance system to demonstrate the resulting improvement in system overload behavior. Our implementation of the Zero-Slack scheduler is available as a part of the Linux/RK project, which provides resource kernel extensions for Linux.

Recent windowing systems allow graphics applications to directly access the graphics processing unit (GPU) for fast rendering. However, application tasks that render frames on the GPU contend heavily with the windowing server that also accesses the GPU to blit the rendered frames to the screen. This resource-sharing nature of direct rendering introduces core challenges of priority inversion and temporal isolation in multi-tasking environments. In this paper, we identify and address resource-sharing problems raised in GPU-accelerated windowing systems. Specifically, we propose two protocols that enable application tasks to efficiently share the GPU resource in the X Window System. The Priority Inheritance with X server (PIX) protocol eliminates priority inversion caused in accessing the GPU, and the Reserve Inheritance with X server (RIX) protocol addresses the same problem for resource-reservation systems. Our design and implementation of these protocols highlight the fact that neither the X server nor user applications need modifications to use our solutions. Our evaluation demonstrates that multiple GPU-accelerated graphics applications running concurrently in the X Window System can be correctly prioritized and isolated by the PIX and the RIX protocols.

Recent years have seen an increasing interest in the scheduling of mixed-criticality real-time systems. These systems are composed of groups of tasks with different levels of criticality deployed over the same processor(s). Such systems must be able to accommodate additional execution-time requirements that may occasionally be needed. When overload conditions develop, critical tasks must still meet their timing constraints at the expense of less critical tasks. Zero-slack scheduling algorithms are promising candidates for such systems. These algorithms guarantee that all tasks meet their deadlines when no overload occurs, and that criticality ordering is satisfied under overloads. Unfortunately, when mutually exclusive resources are shared across tasks, these guarantees are voided. Furthermore, the dual-execution modes of tasks in mixed-criticality systems violate the assumptions of traditional real-time synchronization protocols like PCP and hence the latter cannot be used directly. In this paper, we develop extensions to real-time synchronization protocols (Priority Inheritance and Priority Ceiling Protocol) that coordinate the mode changes of the zero-slack scheduler. We analyze the properties of these new protocols and the blocking terms they introduce. We maintain the deadlock avoidance property of our PCP extension, called the Priority and Criticality Ceiling Protocol (PCCP), and limit the blocking to only one critical section for each of the zero-slack scheduling execution modes. We also develop techniques to accommodate the blocking terms arising from synchronization, in calculating the zero-slack instants used by the scheduler. Finally, we conduct an experimental evaluation of PCCP. Our evaluation shows that PCCP is able to take advantage of the capacity of zero-slack schedulers to reclaim unused over-provisioning of resources that are only used in critical execution modes. This allows PCCP to accommodate larger blocking terms.

Several projects in the recent past have aimed at promoting Wireless Sensor Networks as an infrastructure technology, where several independent users can submit applications that execute concurrently across the network. Concurrent multiple applications cause significant energy-usage overhead on sensor nodes, that cannot be eliminated by traditional schemes optimized for single-application scenarios. In this paper, we outline two main optimization techniques for reducing power consumption across applications. First, we describe a compiler based approach that identifies redundant sensing requests across applications and eliminates those. Second, we cluster the radio transmissions together by concatenating packets from independent applications based on Rate-Harmonized Scheduling.

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.

General-purpose computing on graphics processing units, also known as GPGPU, is a burgeoning technique to enhance the computation of parallel programs. Applying this technique to real-time applications, however, requires additional support for timeliness of execution. In particular, the non-preemptive nature of GPGPU, associated with copying data to/from the device memory and launching code onto the device, needs to be managed in a timely manner. In this paper, we present a responsive GPGPU execution model (RGEM), which is a user-space runtime solution to protect the response times of high-priority GPGPU tasks from competing workload. RGEM splits a memory-copy transaction into multiple chunks so that preemption points appear at chunk boundaries. It also ensures that only the highest-priority GPGPU task launches code onto the device at any given time, to avoid performance interference caused by concurrent launches. A prototype implementation of an RGEM-based CUDA runtime engine is provided to evaluate the real-world impact of RGEM. Our experiments demonstrate that the response times of high-priority GPGPU tasks can be protected under RGEM, whereas their response times increase in an unbounded fashion without RGEM support, as the data sizes of competing workload increase.

Wireless Sensor Networks (WSN) are being used for a number of applications involving infrastructure monitoring, building energy monitoring and industrial sensing. The difficulty of programming individual sensor nodes and the associated overhead have encouraged researchers to design macro-programming systems which can help program the network as a whole or as a combination of subnets. Most of the current macro-programming schemes do not support multiple users seamlessly deploying diverse applications on the same shared sensor network. As WSNs are becoming more common, it is important to provide such support, since it enables higher-level optimizations such as code reuse, energy savings, and traffic reduction. In this paper, we propose a macro-programming framework called Nano-CF, which, in addition to supporting in-network programming, allows multiple applications written by different programmers to be executed simultaneously on a sensor networking infrastructure. This framework enables the use of a common sensing infrastructure for a number of applications without the users being concerned about the applications already deployed on the network. The framework also supports timing constraints and resource reservations using the Nano-RK operating system. Nano-CF is efficient at improving WSN performance by (a) combining multiple user programs, (b) aggregating packets for data delivery, and (c) satisfying timing and energy specifications using Rate-Harmonized Scheduling. Using representative applications, we demonstrate that Nano-CF achieves 90% reduction in Source Lines-of-Code (SLoC) and 50% energy savings from aggregated data delivery.

Dynamic resource management is generating growing interest as a way to simplify systems deployment, react to changing operational conditions and improve efficiency in using system resources. Buttazzo et al proposed the elastic task model (ETM) that dynamically moves the tasks instantiation period around a nominal value, increasing or decreasing the bandwidth that each task uses from the resource. However such computation requires a number of iteration steps. This paper identifies the QoS-based resource distribution problem and proposes a generic framework that encompasses the ETM. An algorithm is presented for the resource distribution that computes the results in minimum time, outperforming the original ETM scheme in terms of computational complexity.

As Electronic Control Units (ECUs) and embedded software functions within an automobile keep increasing in number, the scale and complexity of automotive embedded systems is growing at a very rapid pace. Hence, the automotive industry has been developing the Automotive Open System Architecture (AUTOSAR) to harness the reusability of common interfaces to communication buses, real-time operating systems and services. These common interfaces foster ease of adoption, interoperability, maintainability, predictability, and analyzability. However, realizing such standards also requires strong support from end-to-end design tool chains. In this paper, we describe some key analytical components that together characterize the end-to-end timing properties of hierarchical bus structures composed of FlexRay, CANbus and LINbus. Our analysis shows that the practical constraints imposed by standards such as AUTOSAR can lead to higher levels of schedulable resource utilization. This reduces both the overall component count and cost, while facilitating easy enhancements. Our analytical results show (a) how a schedulable utilization of 100% can be obtained for time-triggered FlexRay static segments under AUTOSAR compliance, (b) average-case schedulable utilization of 87% for the event-triggered CAN bus, and (c) similarities between LINbus and FlexRay analyses. We generalize the analytical results from different bus technologies, by exploiting their common underlying structure to enable an integrated end-to-end timing analysis of hierarchical heterogeneous networks. These together yield an end-to-end framework to analyze heterogeneously networked AUTOSAR-compliant automotive systems.

Ethernet switches are typically found in many large-scale distributed real-time systems providing low-end transactions as well as bulk backbone routing to real-time applications. The FTT-SE protocol (Flexible Time-Triggered communication over Switched Ethernet) is a recent proposal to bypass the limitations of conventional switches in terms of real-time behavior while catering for growing requirements on dynamic reconfigurability and adaptability. For this end, this paper develops linear time-complexity and memory-efficient on-line admission control tests based on utilization bounds for Rate-Monotonic and EDF scheduling on Ethernet switches using FTT-SE, which are suited for dynamic Quality of Service (QoS) management. Our analysis also has broader applicability in general periodic task sets with bounded release delays. For FTT-SE with 100 Mbps links and 1500 bytes of maximum packet size, our sufficient schedulability condition achieves an utilization bound of 61% for RMS and 88% for EDF. Simulation results on randomly generated task sets demonstrate that such bounds are within 18% and 5% utilization of the ideal tests for RMS and EDF, respectively.

Large-scale distributed cyber-physical systems will have many sensors/actuators (each with local micro-controllers), and a distributed communication/computing backbone with multiple processors. Many cyber-physical applications will be safety critical and in many cases unexpected workload spikes are likely to occur due to unpredictable changes in the physical environment. In the face of such overload scenarios, the desirable property in such systems is that the most critical applications continue to meet their deadlines. In this paper, we capture this mixed-criticality property by developing a formal overload-resilience metric called ductility. The generality of ductility enables it to evaluate any scheduling algorithm from the perspective of mixed-criticality cyber-physical systems. In distributed cyber-physical systems, this ductility is the result of both the task-to-processor packing (a.k.a bin packing) and the uniprocessor scheduling algorithms used. In this paper, we present a ductility-maximization packing algorithm to complement our previous work on mixed-criticality uniprocessor scheduling. Our packing algorithm, known as Compress-on-Overload Packing (COP) is a criticality-aware greedy bin-packing algorithm that maximizes the tolerance of high-criticality tasks to overloads. We compare the ductility of COP against the Worst-Fit Decreasing (WFD) bin-packing heuristic used traditionally for load balancing in distributed systems, and show that the performance of COP dominates WFD in the average case and can reach close to five times better ductility when resources are limited. Finally, we illustrate the practical use of COP in distributed cyber-physical systems using a radar surveillance application, and provide an overview of the entire process from assigning task criticality levels to evaluating its performance

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.

Recent results have shown that the feasibility problem of scheduling periodic tasks with self-suspensions is NP-hard in the strong sense. We observe that a variation of the problem statement that includes sporadic tasks instead of periodic tasks results in a simple characterization of the critical scheduling instant. This in turn leads to an exact characterization of the critical instant for self-suspending tasks with respect to the interference (preemption) from higher-priority sporadic tasks. Using this characterization, we provide pseudo-polynomial response-time tests for analyzing the schedulability of such self-suspending tasks. Self-suspending tasks can also result in more worst-case interference to lower-priority tasks than their equivalent non-suspending counterparts with zero suspension intervals. Hence, we develop a dynamic slack enforcement scheme, which guarantees that the worst-case interference caused by suspending sporadic tasks is no more than the worst-case interference arising from equivalent non-suspending sporadic tasks without suspension intervals. The worst-case response time of self-suspending sporadic tasks themselves is also shown to be unaffected by dynamic slack enforcement, thereby making it optimal. In order to reduce the runtime complexity of slack enforcement, a static slack enforcement scheme is also developed. Empirical analysis of these schemes and the previously studied period enforcement algorithm shows that static slack enforcement achieves within 3% of the breakdown utilization of dynamic slack enforcement, while period enforcement achieves within 14% of dynamic slack enforcement. System designers can take advantage of these different execution control policies depending on their taskset utilizations and implementation constraints.

Massively multi-core processors are rapidly gaining market share with major chip vendors offering an ever increasing number of cores per processor. From a programming perspective, the sequential programming model does not scale very well for such multi-core systems. Parallel programming models such as OpenMP present promising solutions for more effectively using multiple processor cores. In this paper, we study the problem of scheduling periodic real-time tasks on multiprocessors under the fork join structure used in OpenMP. We illustrate the theoretical best-case and worst-case periodic fork-join task sets from a processor utilization perspective. Based on our observations of these task sets, we provide a partitioned preemptive fixed-priority scheduling algorithm for periodic fork-join tasks. The proposed multiprocessor scheduling algorithm is shown to have a resource augmentation bound of 3.42, which implies that any task set that is feasible on m unit speed processors can be scheduled by the proposed algorithm on m processors that are 3:42 times faster.

This paper presents a family ofRate-Harmonized Schedulersthat can be used in reservation-based operating systems to naturally cluster task execution and lump processor idle durations. While traditional approaches to energy management have focused on reducingdynamic switching powerthrough Dynamic Voltage and Frequency Scaling (DVFS), processor technology trends predict a future in whichstatic leakage powerwill begin to dominate. To this end, most modern processors provide built-in support for sleep modes withlow leakage power. However, substantial time is required to switch in/out of such sleep modes due to mechanical oscillator stabilization delays. Significant opportunities for energy saving are potentially missed due to idle gaps between executing tasks that are shorter than the time required to enter the sleep mode. Armed with apriori workload information,reservation-basedoperating systems can potentially eliminate such wasted idle durations using Rate-Harmonized Scheduling. AnEnergy-Saving Rate-Harmonized Schedulerguarantees thateveryidle duration can be used to switch into sleep mode. This paper also provides extensions to Rate-Harmonized Scheduling to support multicore processors. Empirical evaluation results are provided from an implementation in the nano-RK operating system for wireless sensor networks. Energy-Saving Rate-Harmonized Scheduling saves 16.8% energy compared to conventional Rate-Monotonic Scheduling for the task set used inSensor Andrewproject. At low utilization levels, Energy-Saving Rate-Harmonized Scheduling can save up to 39% energy on randomly generated task sets.

Energy and thermal considerations are increasingly driving system designers to adopt multi-core processors. In this paper, we consider the problem of scheduling periodic real-time tasks on multi-core processors using fixed-priority preemptive scheduling. Specifically, we focus on the partitioned (static binding) approach, which statically allocates tasks to processing cores. The well-established 50% bound for partitioned multiprocessor scheduling [10] can be overcome by task-splitting (TS) [19], which allows a task to be split across more than one core. We prove that a utilization bound of 60% per core can be achieved by the partitioned deadline-monotonic scheduling (PDMS) class of algorithms on implicit-deadline task sets, when the highest-priority task on each processing core is allowed to be split (HPTS). Given the widespread usage of fixed-priority scheduling in commercial real-time and non real-time operating systems (e.g. VxWorks, Linux), establishing such utilization bounds is both relevant and useful. We also show that a specific instance of PDMS_ HPTS, where tasks are allocated in the decreasing order of size, called PDMS_HPTS_ DS, has a utilization bound of 65% on implicit deadline task-sets. The PDMS_ HPTS_ DS algorithm also achieves a utilization bound of 69% on lightweight implicit-deadline task-sets where no single task utilization exceeds 41.4%. The average-case behavior of PDMS_ HPTS_ DS is studied using randomly generated task-sets, and it is seen to have an average schedulable utilization of 88%. We also characterize the overhead of task-splitting using measurements on an Intel Core 2 Duo processor.

Chip-multiprocessors represent a dominant new shift in the field of processor design. Better utilization of such technology in the real-time context requires coordinated approaches to task allocation, scheduling, and synchronization. In this paper, we characterize various scheduling penalties arising from multiprocessor task synchronization, including (i) blocking delays on global critical sections, (ii) back-to-back execution due to jitter from blocking, and (iii) multiple priority inversions due to remote resource sharing. We analyze the impact of these scheduling penalties under different execution control policies (ECPs) which compensate for the scheduling penalties incurred by tasks due to remote blocking. Subsequently, we develop a synchronization-aware task allocation algorithm for explicitly accommodating these global task synchronization penalties. The key idea of our algorithm is to bundle tasks that access a common shared resource and co-locate them, thereby transforming global resource sharing into local sharing. This approach reduces the above-mentioned penalties associated with remote task synchronization. Experimental results indicate that such a coordinated approach to scheduling, allocation, and synchronization yields significant benefits (as much as 50% savings in terms of required number of processing cores). An implementation of this approach is available as a part of our RT-MAP library, which uses the pthreads implementation of Linux-2.6.22.

The functional consolidation induced by the cost reduction trends in embedded systems can force tasks of different criticality (e.g. ABS Brakes with DVD) to share a processor and interfere with each other. These systems are known as mixed criticality systems. While traditional temporal isolation techniques prevent all inter-task interference, they waste utilization because they need to reserve for the absolute worst-case execution time (WCET) for all tasks. In many mixed-criticality systems the WCET is not only rare, but at times difficult to calculate, such as the time to localize all possible objects in an obstacle avoidance algorithm. In this situation it is more appropriate to allow the execution time to grow by stealing cycles from lower-criticality tasks. Even more crucial is the fact that temporal isolation techniques can stop a high-criticality task (that was overrunning its nomimal WCET) to allow a low-criticality task to run, making the former miss its deadline. We identify this as the criticality inversion problem. In this paper, we characterize the criticality inversion problem and present a new scheduling scheme called zero-slack scheduling that implements an alternative protection scheme we refer to as asymmetric protection. This protection only prevents interference from lower-criticality to higher-criticality tasks and improves the schedulable utilization. We use an offline algorithm with two parts: a zero-slack calculation algorithm, and a slack analysis algorithm. The zero-slack calculation algorithm minimizes the utilization needed by a task set by reducing the time low-criticality tasks are preempted by high-criticality ones. This algorithm can be used with priority-based preemptive schedulers (e.g. RMS, EDF). The slack analysis algorithm is specific for each priority-based preemptive scheduler and we develop and evaluated the one for RMS. We prove that this algorithm provides the same level of protection against criticality inversion as the best known priority assignment for this purpose, criticality as priority assignment (CAPA). We also prove that zero-slack RM provides the same level of schedulable utilization as RMS when all tasks have equal criticality levels. Finally, we present our implementation of the runtime enforcement mechanisms in Linux/RK to demonstrate its practicality.

The notion of resource reservation for obtaining real-time scheduling guarantees and enforcement of resource usage has gained strong support in recent years. However, much work on resource reservation has primarily focused on single-processor systems. In this paper, we propose the distributed resource kernel frame wo rk to deploy distributed real-time applications with end-to-end timing constraints, and to efficiently enforce and monitor their usage. Modern distributed real-time systems host multiple applications, where each application can span two or more processors. Timing bugs in one distributed application can affect the timing properties of other applications in the system. Our framework introduces the abstraction of a distributed resource container as an isolated virtual operating environment for a distributed real-time application. We have implemented this framework by extending our open-source single- node Linux/RK platform (R. Rajkumar et al., 1998). A deployment and monitoring tool called dMon is also provided. We evaluate the framework's ability to provide timing guarantees by stress-testing the system using the Distributed Hartstone benchmarks. An audio processing pipeline is then used to illustrate the temporal isolation support provided by the Distributed RK framework. The distributed container abstraction can also be extended in the future to support security and fault-tolerance attributes.

Energy consumption continues to be a major concern in multiple application domains including power-hungry data centers, portable and wearable devices, mobile communication devices and wireless sensor networks. While energy-constrained, many such applications must meet timing and QoS constraints for sensing, actuation or multimedia data processing. Many modern power-aware processors and microcontrollers have built-in support for active, idle and sleep operating modes. In sleep mode, substantially more energy savings can be obtained but it requires a significant amount of time to switch into and out of that mode. Hence, a significant amount of energy is lost due to idle gaps between executing tasks that are shorter than the required time for the processor to enter the sleep mode. We present a technique called rate-harmonized scheduling that naturally clusters task execution such that processor idle times are lumped together. We next introduce the energy-saving rate-harmonized scheduler which guarantees that every idle duration on the processor can be used to put the processor into sleep mode. This property can be used to even eliminate the idle power mode in processors but nevertheless it is predictable, analyzable, and saves more energy. We finally evaluate the practical benefits of rate-harmonized scheduling implemented in the nano-RK real-time operating system [1] for wireless sensor networks.