The proposed scheduling scheme minimizes the mean energy consumption of a real-time parallel task, where the task has the probabilistic computation amount and can be executed concurrently on multiple cores. The scheme determines a pertinent number of cores allocated to the task execution and the instant frequency supplied to the allocated cores. Evaluation shows that the scheme saves manifest amount of the energy consumed by the previous method minimizing the mean energy consumption on a single core.

Parameter variations reveal themselves as different frequency and leakage powers per instances of the same MPSoC. By the increasing variation with technology scaling, worst-case-based scheduling algorithms result in either increasingly less optimal schedules or otherwise more lost yield. To address this problem, this paper introduces a variation-aware task and communication scheduling algorithm for multiprocessor system-on-chip (MPSoC). We consider both delay and leakage power variations during the process of finding the best schedule so that leakier processors are less utilized and can be more frequently put in sleep mode to reduce power. Our algorithm takes advantage of event tables to accelerate the statistical timing and power analysis. We use genetic algorithm to find the best schedule that maximizes power-yield under a performance-yield constraint. Experimental results on real world benchmarks show that our proposed algorithm achieves 16.6% power-yield improvement on average over deterministic worst-case-based scheduling.

Heterogeneous multi-core processors are attracted by the media processing applications due to their capability of drawing strengths of different cores to improve the overall performance. However, the data transfer bottlenecks and limitations in the task allocation due to the accelerator-incompatible operations prevents us from gaining full potential of the heterogeneous multi-core processors. This paper presents a task allocation method based on algorithm transformation to increase the freedom of task allocation. We use approximation methods such as CORDIC algorithms to map the accelerator-incompatible operations to accelerator cores. According to the experimental results using HOG descriptor computation, the proposed task allocation method reduces the data transfer time by more than 82% and the total processing time by more than 79% compared to the conventional task allocation method.

Power-aware scheduling problem has been a recent issue in cluster systems not only for operational cost due to electricity cost, but also for system reliability. In this paper, we provide SLA-based scheduling algorithms for bag-of-tasks applications with deadline constraints on power-aware cluster systems. The scheduling objective is to minimize power consumption as long as the system provides the service levels of users. A bag-of-tasks application should finish all the sub-tasks before the deadline as the service level. We provide the power-aware scheduling algorithms for both time-shared and space-shared resource sharing policies. The simulation results show that the proposed algorithms reduce much power consumption compared to static voltage schemes.

In an embedded control system, control performances of each job depend on its latency and a control algorithm implemented in it. In order to adapt a job set to optimize control performances subject to schedulability, we design several types of control software for each job, which will be called versions, and select one version from them when the job is released. A real-time system where each job has several versions is called a multiversion real-time system. A benefit and a CPU utilization of a job depend on the versions. So, it is an important problem to select a version of each job so as to maximize the total benefit of the system subject to a schedulability condition. Such a problem will be called an optimal configuration problem. In this paper, we assume that each version is specified by the relative deadline, the execution time, and the benefit. We show that the optimal configuration problem is transformed to a maximum path length problem. We propose an optimal algorithm based on the forward dynamic programming. Moreover, we propose sub-optimal algorithms to reduce computation times. The efficiencies of the proposed algorithms are illustrated by simulations.

Three experiments were conducted in this study to investigate the human ability to control pen pressure and pen tilt input, by coupling this control with cursor position, angle and scale. Comparisons between pen pressure input and pen tilt input have been made in the three experiments. Experimental results show that decreasing pressure input resulted in very poor performance and was not a good input technique for any of the three experiments. In "Experiment 1-Coupling to Cursor Position", the tilt input technique performed relatively better than the increasing pressure input technique in terms of time, even though the tilt technique had a slightly higher error rate. In "Experiment 2-Coupling to Cursor Angle", the tilt input performed a little better than the increasing pressure input in terms of time, but the gap between them is not so apparent as Experiment 1. In "Experiment 3-Coupling to Cursor Scale", tilt input performed a little better than increasing pressure input in terms of adjustment time. Based on the results of our experiments, we have inferred several design implications and guidelines.

A task that suspends itself to wait for an I/O completion or to wait for an event from another node in distributed environments is called an I/O blocking task. Conventional hard real-time scheduling theories use framework of rate monotonic analysis (RMA) to schedule such I/O blocking tasks. However, most of them are pessimistic. In this paper, we propose effective algorithms that can schedule a task set which has I/O blocking tasks under dynamic priority assignment. We present a new critical instant theorem for the multi-frame task set under dynamic priority assignment. The schedulability is analyzed under the new critical instant theorem. For the schedulability analysis, this paper presents saturation summation which is used to calculate the maximum interference function (MIF). With saturation summation, the schedulability of a task set having I/O blocking tasks can be analyzed more accurately. We propose an algorithm which is called Frame Laxity Monotonic Scheduling (FLMS). A genetic algorithm (GA) is also applied. From our experiments, we can conclude that FLMS can significantly reduce the calculation time, and GA can improve task schedulability ratio more than is possible with FLMS.

We have a job with N tandem tasks each of which is executed successively until it is completed. A double modular system of error detection for the processing of each task is adopted. Either type of checkpoints such as compare-checkpoint or compare-and-store-checkpoint can be placed at the end of tasks. Three schemes for the above process of a job are considered and the mean execution time of each scheme is obtained. Three schemes are compared and the best scheme is determined numerically. As an example, a job with 4 tasks is given and 6 types of schemes are compared numerically. Finally, we consider a majority decision system as an error masking system and compute the mean execution time for three schemes.

A scheduling algorithm aims to minimize the overall execution time of the program by properly allocating and arranging the execution order of the tasks on the core processors such that the precedence constraints among the tasks are preserved. In this paper, we present a new scheduling algorithm by using geometry analysis of the Task Precedence Graph (TPG) based on A* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity and pruning techniques to produce an optimal solution for the allocation/scheduling problem of a parallel application to parallel and multiprocessor architecture. The main goal of this work is to significantly reduce the search space and achieve the optimality or near optimal solution. We implemented the algorithm on general task graph problems that are processed on most of related search work and obtain the optimal scheduling with a small number of states. The proposed algorithm reduced the exhaustive search by at least 50% of search space. The viability and potential of the proposed algorithm is demonstrated by an illustrative example.

Utilizing a heterogeneous multiprocessor system has become a popular design paradigm to build an embedded system at a cheap cost within short development time. A reliability issue for embedded systems, which is vulnerability to single event upsets (SEUs), has become a matter of concern as technology proceeds. This paper discusses reliability inherent in heterogeneous multiprocessors and proposes task scheduling for minimizing SEU vulnerability of them. This paper experimentally shows that increasing performance of a CPU core deteriorates its reliability. Based on the experimental observation, we propose task scheduling for reducing SEU vulnerability of a heterogeneous multiprocessor system. The experimental results demonstrate that our task scheduling technique can reduce much of SEU vulnerability under real-time constraints.

We propose a polynomial-time algorithm for the scheduling of real-time parallel tasks on multicore processors. The proposed algorithm always finds a feasible schedule using the minimum number of processing cores, where tasks have properties of linear speedup, flexible preemption, arbitrary deadlines and arrivals, and parallelism bound. The time complexity of the proposed algorithm is O(M3log N) for M tasks and N processors in the worst case.

This paper investigates the problem of nonpreemptively scheduling independent parallel tasks in an environment with multiple machines, which is motivated from the recent studies in scheduling tasks in a multi-machine environment. In this scheduling environment, each machine contains a number of identical processors and each parallel task can simultaneously require a number of processors for its processing in any single machine. Whenever tasks are processed in parallel in a parallel machine, message communication among processors is often inevitable. The problem of finding a shortest schedule length on scheduling independent parallel tasks with the consideration of communication overhead in a multi-machine environment is NP-hard. The aim of this paper is to propose a heuristic algorithm for this kind of problem and to analyze the performance bound of this heuristic algorithm.

Humans have a remarkable ability to flexibly control various objects such as tools. Much evidence suggests that the internal models acquired in the central nervous system (CNS) support flexible control. Internal models are neural mechanisms that mimic the input-output properties of controlled objects. In a series of functional magnetic resonance imaging (fMRI) studies, we demonstrate how the CNS acquires and switches internal models for dexterous use of many tools. In the first study, we investigated human cerebellar activity when human subjects learned how to use a novel tool (a rotated computer mouse, where the cursor appears in a rotated position) and found that activity reflecting an internal model of the novel tool increases in the lateral cerebellum after learning how to use the tool. In the second study, we investigated the internal-model activity after sufficient training in the use of two types of novel tools (the rotated mouse and a velocity mouse, where the cursor's velocity is proportional to mouse's position) and found that the cerebellar activities for the two tools were spatially segregated. In the third study, we investigated brain activity associated with the flexible switching of tools. We found that the activity related to switching internal models was in the prefrontal lobe (area 46 and the insula), the parietal lobe, and the cerebellum. These results suggest that internal models in the cerebellum represent input-output properties of the tools as modulators of continuous signals. The cerebellar abilities in adaptive modulation of signals can be used to enhance the control signals in communications between the brain and computers.

A simple extension used to assist the decomposition of task-level concurrency within C programs is presented in this paper. The concurrency decomposition is meant to be used as the point of entry for Multiprocessor System-on-Chips (MPSoC) architectures' design-flow. Our methodology allows the (re)use of readily available reference C programs and enables easy and rapid exploration for various alternatives of task partitioning strategies; a crucial task that greatly influences the overall quality of the designed MPSoC. A test case using a JPEG encoder application has been performed and the results are presented in this paper.

In this paper, we present a novel approach to recognize motion styles and identify people using the Multi Factor Tensor (MFT) model. We apply a musical information analysis method in segmenting the motion sequence relevant to the keyposes and the musical rhythm. We define a task model by considering the repeated motion segments, where the motion is decomposed into a person-invariant factor task and a person-dependent factor style. Given the motion data set, we formulate the MFT model, factorize it efficiently in different modes, and use it in recognizing the tasks and the identities of the persons performing the tasks. We capture the motion data of different people for a few cycles, segment it using the musical analysis approach, normalize the segments using a vectorization method, and realize our MFT model. In our experiments, Japanese traditional dance sequences performed by several people are used. Provided with an unknown motion segment which is to be probed and which was performed at a different time in the time space, we first normalize the motion segment and flatten our MFT model appropriately, then recognize the task and the identity of the person. We follow two approaches in conducting our experiments. In one experiment, we recognize the tasks and the styles by maximizing a function in the tensor subdomain, and in the next experiment, we use a function value in the tensorial subdomain with a threshold for recognition. Interestingly, unlike the first experiment, we are capable of recognizing tasks and human identities that were not known beforehand. We conducted various experiments to evaluate the potential of the recognition ability of our proposed approaches, and the results demonstrate the high accuracy of our model.

This paper proposes a task scheduling approach for reliable cache architectures (RCAs) of multiprocessor systems. The RCAs dynamically switch their operation modes for reducing the usage of vulnerable SRAMs under real-time constraints. A mixed integer programming model has been built for minimizing vulnerability under real-time constraints. Experimental results have shown that our task scheduling approach achieved 47.7-99.9% less vulnerability than a conventional one.

The scheduling of real-time tasks with fault-tolerant requirements has been an important problem in multiprocessor systems. The primary-backup (PB) approach is often used as a fault-tolerant technique to guarantee the deadlines of tasks despite the presence of faults. In this paper we propose a dynamic PB-based task scheduling approach, wherein an allocation parameter is used to search the available time slots for a newly arriving task, and the previously scheduled tasks can be re-scheduled when there is no available time slot for the newly arriving task. In order to improve the schedulability we also propose an overloading strategy for PB-overloading and Backup-backup (BB) overloading. Our proposed task scheduling algorithm is compared with some existing scheduling algorithms in the literature through simulation studies. The results have shown that the task rejection ratio of our real-time task scheduling algorithm is almost 50% lower than the compared algorithms.

Development of an ASR application such as a speech-oriented guidance system for a real environment is expensive. Most of the costs are due to human labeling of newly collected speech data to construct the acoustic model for speech recognition. Employment of existing models or sharing models across multiple applications is often difficult, because the characteristics of speech depend on various factors such as possible users, their speaking style and the acoustic environment. Therefore, this paper proposes a combination of unsupervised learning and selective training to reduce the development costs. The employment of unsupervised learning alone is problematic due to the task-dependency of speech recognition and because automatic transcription of speech is error-prone. A theoretically well-defined approach to automatic selection of high quality and task-specific speech data from an unlabeled data pool is presented. Only those unlabeled data which increase the model likelihood given the labeled data are employed for unsupervised training. The effectivity of the proposed method is investigated with a simulation experiment to construct adult and child acoustic models for a speech-oriented guidance system. A completely human-labeled database which contains real-environment data collected over two years is available for the development simulation. It is shown experimentally that the employment of selective training alleviates the problems of unsupervised learning, i.e. it is possible to select speech utterances of a certain speaker group but discard noise inputs and utterances with lower recognition accuracy. The simulation experiment is carried out for several selected combinations of data collection and human transcription period. It is found empirically that the proposed method is especially effective if only relatively few of the collected data can be labeled and transcribed by humans.

In real-time systems, deadline misses of the tasks cause a degradation in the quality of their results. To improve the quality, we have to allocate CPU utilization for each task adaptively. Recently, Buttazzo et al. address a feedback scheduling algorithm, which dynamically adjusts task periods based on the current workloads by applying a linear elastic task model. In their model, the utilization allocated to each task is treated as the length of a linear spring and its flexibility is described by a constant elastic coefficient. In this paper, we first consider a nonlinear elastic task model, where the elastic coefficient depends on the utilization allocated to the task. We propose a simple iterative method for calculating the desired allocated resource and derive a sufficient condition for the convergence of the method. Next, we apply the nonlinear elastic model to an adaptive fair sharing controller. Finally, we show the effectiveness of the proposed method by computer simulation.

Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.