Recently, several parallel frameworks have emerged to utilize the increasing computational capacity of multiprocessors. Parallel tasks are distinguished from traditional sequential tasks in that the subtasks contained in a single parallel task can simultaneously execute on multiple processors. In this study, we consider the scheduling problem of minimizing the number of processors on which the parallel real-time tasks feasibly run. In particular, we focus on scheduling sporadic parallel real-time tasks, in which precedence constraints between subtasks of each parallel task are expressed using a directed acyclic graph (DAG). To address the problem, we formulate an optimization problem that aims to minimize the maximum processing capacity for executing the given tasks. We then suggest a polynomial solution consisting of three steps: (1) transform each parallel real-time task into a series of multithreaded segments, while respecting the precedence constraints of the DAG; (2) selectively extend the segment lengths; and (3) interpret the problem as a flow network to balance the flows on the terminal edges. We also provide the schedulability bound of the proposed solution: it has acapacity augmentation boundof 2. Our experimental results show that the proposed approach yields higher performance than one developed in a recent study.

We present TwohandsMusic, a new real-time system for recognizing egocentric piano-playing gestures on planar objects by using a depth camera. Existing methods have usually recognized single tap gestures of one hand using a sensor installed in front of or under the user's hand. In contrast, we consider recognizing multi-tap gestures of both hands using a depth camera installed near the user's head. Our approach consists of two steps: hand detection and gesture recognition. At the hand detection step, we detect both hands using a 2DCNN (Convolutional Neural Network), called SegNet, and generate cropped hand images, which is to be used in the next step. In the gesture recognition step, we estimate 3D hand poses and classify multi-tap gestures simultaneously using a 3DCNN with multitask learning, called MusicNet. For training and validating of our system, we collect 85K dataset including tapping chords and show improved results over state-of-the-art methods.

Current virtual keyboards are known to be slower and less convenient than physical QWERTY keyboards because they simply imitate the traditional QWERTY keyboards on touchscreens. In order to improve virtual keyboards, we consider two reasonable assumptions based on the observation of skilled typists. First, the keys are already assigned to each finger for typing. Based on this assumption, we suggest restricting each finger to entering pre-allocated keys only. Second, non-touching fingers move in correlation with the touching finger because of the intrinsic structure of human hands. To verify of our assumptions, we conducted two experiments with skilled typists. In the first experiment, we statistically verified the second assumption. We then suggest a novel virtual keyboard using our observations. In the second experiment, we show that our suggested keyboard outperforms existing virtual keyboards.

A surveillance system, which tracks mobile targets, is one of the most important applications of wireless sensor networks. When nodes operate in a duty cycling mode, tracking performance can be improved if the target motion can be predicted and nodes along the trajectory can be proactively awakened. However, this will negatively influence the energy efficiency and constrain the benefits of duty cycling. In this paper, we present a Probability-based Prediction and Sleep Scheduling protocol (PPSS) to improve energy efficiency of proactive wake up. We start with designing a target prediction method based on both kinematics and probability. Based on the prediction results, PPSS then precisely selects the nodes to awaken and reduces their active time, so as to enhance energy efficiency with limited tracking performance loss. We evaluated the efficiency of PPSS with both simulation-based and implementation-based experiments. The experimental results show that compared to MCTA algorithm, PPSS improves energy efficiency by 25-45 percent (simulation based) and 16.9 percent (implementation based), only at the expense of an increase of 5-15 percent on the detection delay (simulation based) and 4.1 percent on the escape distance percentage (implementation based), respectively.

We present a guaranteed real-time scheduling algorithm for multiple real-time tasks subject to (m,k)-firm deadlines on homogeneous multiprocessors. The scheduling objective of the proposed algorithm is to provide guaranteed performance by bounding the probability of missing (m,k)-firm deadline constraints while improving the probability of deadline satisfactions as much as possible. This goal is established to satisfy the minimum requirements expressed by (m,k)-firm deadlines and simultaneously provide the best possible quality of service. We analytically establish that the proposed algorithm provides assurance on the bounded probability of missing (m,k)-firm constraints. Experimental studies validate our analytical results and confirm the effectiveness and superiority of the proposed scheme in achieving our scheduling objective.

We present heterogenous quorum-based asynchronous wake-up scheduling schemes for wireless sensor networks. The schemes can ensure that two nodes that adopt different quorum systems as their wake-up schedules can hear each other at least once in bounded time intervals. We propose two such schemes: cyclic quorum system pair (cqs-pair) and grid quorum system pair (gqs-pair). The cqs-pair which contains two cyclic quorum systems provides an optimal solution, in terms of energy saving ratio, for asynchronous wake-up scheduling. To quickly assemble a cqs-pair, we present a fast construction scheme which is based on the multiplier theorem and the (N,k,M, l)-difference pair defined by us. Regarding the gqs-pair, we prove that any two grid quorum systems will automatically form a gqs-pair. We further analyze the performance of both designs, in terms of average discovery delay, quorum ratio, and energy saving ratio. We show that our designs achieve better trade-off between the average discovery delay and quorum ratio (and thus energy consumption) for different cycle lengths. We implemented the proposed designs in a wireless sensor network platform of Telosb motes. Our implementation-based measurements further validate the analytically-established performance trade-off of our designs.

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger “adversary” than most traditional arrival models. We derive an upper bound on lock-free retries under the UAM with utility accrual scheduling—the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities' accrued timeliness utility is greater under lock-free than lock-based, and the consequent lower and upper bound on the total accrued utility that is possible with lock-free and lock-based sharing. We confirm our analytical results with a POSIX RTOS implementation.

Network capacity is a critical feature of wireless ad hoc and sensor networks. It is particularly challenging to determine network capacity when combined with other performance objectives such as timeliness. This paper investigates real-time capacity for event-driven data-gathering sensor networks w

We consider garbage collection (GC) in dynamic, multiprocessor real-time systems. We consider the time-based, concurrent GC approach and focus on real-time scheduling to obtain mutator timing assurances, despite memory allocation and garbage collection. We present a scheduling algorithm called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We establish that GCMUA probabilistically lower bounds each mutator activity's accrued utility, lower bounds the system-wide total accrued utility, and upper bounds the timing assurances' sensitivity to variations in mutator execution-time and memory demand estimates. Our simulation experiments validate our analytical results and confirm GCMUA's effectiveness.

This paper presents a target direction-based sleep scheduling algorithm (TDSS) for target tracking surveillance sensor networks. TDSS reduces the number of the proactively awakened sensor nodes and schedules their sleep pattern to enhance energy efficiency but suffer little performance loss. Both approaches are based on two probabilistic distribution models of target moving directions, normal distribution and linear distribution. We compare TDSS with the two models against the legacy circle-based proactively waking up scheme (Circle) and a working node reducing algorithm - MCTA. The evaluation result shows that TDSS achieves better energy efficiency but with less performance loss in terms of detection probability and detection delay.

In this paper, we present a reliable real-time data delivery (communication) mechanism for ad-hoc networks, called RTRD. The mechanism makes use of a proactive wireless routing protocol (DSDV) for path finding and maintenance, and timely delivers data through a priori bandwidth reservation. In addition, to be robust to network failures, or to deliver large data chunks, it simultaneously delivers data in multiple paths. The simulation results conducted by NS-2 validate RTRD's effectiveness.

We consider the rate allocation problem for data aggregation in wireless sensor networks with two objectives: 1) maximizing the lifetime of a local aggregation cluster and 2) achieving fairness among all data sources. The two objectives are generally correlated with each other and usually they cannot be maximized simultaneously. We adopt a lexicographic method to solve this multi-objective programming problem. First, we recursively induce the maximum lifetime for the local aggregation cluster. Under the given maximum lifetime, we then formulate the problem of maximizing fairness as a convex optimization problem, and derive the optimal rate allocation strategy. We also present low-complexity algorithms that a local aggregation cluster can use to determine the optimal rate allocation. Our simulation results validate our analytical results and illustrate the effectiveness of the approach.

We consider wait-free synchronization for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We present an analytical solution to the problem of determining the minimum, optimal space cost required for this problem, considering a priori knowledge of interferences $the first such result. We also show that the space costs required by previous algorithms can be obtained by our analytical solution, which subsumes them as special cases. We also present a wait-free protocol that utilizes the minimum space cost determined by our analytical solution. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel validate our analytical results

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger“adversary” than most traditional arrival models. We derive the upper bound on lock-free retries under the UAM with utility accrual scheduling—the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities’accrued timeliness utility is greater under lock-free than lock-based, and the consequent upper bound on the increase in accrued utility that is possible with lock-free. We confirm our analytical results with a POSIX RTOS implementation.

We consider garbage collection (GC) in dynamic realtime systems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mutator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and confirm the algorithm's effectiveness and superiority.

We present a garbage collector scheduling algorithm for dynamic multiprocessor real-time systems called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We prove that GCMUA probabilistically lower bounds each mutator's accrued utility, lower bounds the total accrued utility, and upper bounds the assurances' sensitivity to variations in execution-time and memory demand estimates. Our simulation results confirm our analytical results

We present an optimal real-time scheduling algorithm for multiprocessors $one that satisfies all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. The algorithm called LLREF, is designed based on a novel abstraction for reasoning about task execution behavior on multiprocessors: the time and local execution time domain plane (or T-L plane). LLREF is based on the fluid scheduling model and the fairness notion, and uses the T-L plane to describe fluid schedules without using time quanta, unlike the optimal Pfair algorithm (which uses time quanta). We show that scheduling for multiprocessors can be viewed as repeatedly occurring T-L planes, and feasibly scheduling on a single T-L plane results in the optimal schedule. We analytically establish the optimality of LLREF. Further, we establish that the algorithm has bounded overhead, and this bound is independent of time quanta (unlike Pfair). Our simulation results validate our analysis on the algorithm overhead

We present a wait-free protocol for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We analytically establish that our protocol requires lesser (or equal) number of buffers than previously best wait-free protocols for this problem. Further, we prove that our protocol is space-optimal - the first space optimality established for wait-free protocols that consider a-priori knowledge of preemptions. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel confirm the protocol's superiority and effectiveness.

Heuristic algorithms have enjoyed increasing interests and success in the context of utility accrual (UA) scheduling. However, few analytical results, such as bounds on task-level and system-level accrued utilities are known. In this paper, we propose the S-UA algorithm that can provide probabilistic bounds on task-level accrued utilities. Lower bound on system-level accrued utility ratio (AUR) is also derived and maximized by S-UA.