While multi-core architectures, by exploring the thread/process level parallelism, help to lower down the power/thermal barrier for single core architectures, power/thermal issues are still the primary limiting factors to achieve high computing performance. In this paper, we study the problem of how to maximize the computing performance of multi-core platforms without violating their peak temperature constraint. As different cores may exhibit different thermal behaviors, we propose to run each core with different working frequencies and develop a schedule based on two novel concepts, i.e. the step-up schedule and the m-Oscillating schedule, for multi-core platforms. We formally prove that the proposed schedule can guarantee the peak temperature constraint for a given multi-core platform. Compared with the traditional exhaustive search-based approach, our approach can reduce the computation time by orders of magnitude and improve the throughput up to 89%, with an average improvement of 11%.

Multicore platforms are becoming the primary choice to achieve high performance in today's embedded system design. However, under the current IC technology, the dramatic increase in power density has made the thermal issue a critical concern in design of multicore systems. In this paper, we study the problem on how to determine if a periodic dynamic voltage and frequency scaling (DVFS) schedule for a multicore platform is thermally feasible in satisfying a given peak temperature constraint. To solve this problem, we first develop a novel analytic method to quickly calculate the temperature at an arbitrary time instant, which can achieve orders-of-magnitude speedups over the HotSpot simulator. We then present an approach to pinpoint the peak temperature of a given periodic multicore DVFS schedule. Finally, we develop three methods to check the thermal feasibility of an arbitrary schedule. We formally prove the fundamental principles and validity of our proposed methods and use simulation results to demonstrate their effectiveness.

Web applications grow tremendously in both scale and scope, the application patterns turn to be more and more sophisticated. It is important but challenging for service providers to lower the operational costs without degrading user experiences, especially in the case where a service provider's profit is closely related to the user experience (e.g. response time.) In this paper, we study the problem of efficiently scheduling multi-tier time sensitive applications on distributed computing platforms with respect to the user's Quality of Service (QoS) requirements. The efficiency refers to the QoS satisfaction with low average response times. The service provider must ensures that service requests be served successfully before end-to-end deadlines with certain probabilities. To solve this problem, we propose an approach to judiciously assign a deadline for each service tier. An application request is dropped if any one of its services misses its deadline. Our simulation results demonstrate that our approach can statistically guarantee the required QoS more efficiently than the other widely applied methods (e.g. acceptance control, first-come-first-serve, deterministic sub deadline assignment, etc.) irrespective of whether the resources are shared or not by multiple different applications.

This paper presents a new semipartitioned approach to schedule sporadic tasks on multicore platforms based on the Rate Monotonic Scheduling policy. To improve the schedulability, our approach exploits the fact that the utilization bound of a task set increases as task periods become closer to harmonic on single processor platforms. The challenge for our approach, however, is how to take advantage of this fact to assign and split appropriate tasks on different processors in the semipartitioned approach, and how to guarantee the schedulability of real-time tasks. We formally prove that our scheduling approach can successfully schedule any task set with a system utilization bounded by Liu&Layland's bound for N tasks, that is, N(21/N- 1). Our extensive experimental results demonstrate that the proposed algorithm can significantly improve the scheduling performance compared with the previous work.

Energy minimization is a critical issue and challenge when considering the cyclic dependency of leakage power and temperature as IC technology reaches deep sub-micron level. In this paper, we present an analytical method to calculate the energy consumption efficiently and effectively for a given voltage schedule on a multi-core platform, with the leakage/temperature dependency taken into consideration. Our experiments show that the proposed method can achieve a speedup of 15 times compared with the numerical method, with a relative error of no more than 1.5%.

Relentless technology scaling not only dramatically increased the energy consumption of modern processors, it also makes processors less reliable. In this paper, we study the energy minimization problem for real-time applications on multi-processor platforms while tolerating K transient faults using checkpointing. We first introduce an efficient method to determine the checkpointing scheme that minimizes the worst-case response time for a task set that shares the reserved recoveries on a single processor. We then present a fault-tolerant task assignment algorithm to minimize the overall energy. Experimental results show that the proposed algorithm significantly outperforms other related approaches in energy savings.

As the semiconductor technology proceeds into the deep sub-micron era, leakage and its dependency with the temperature become critical in dealing with the power/energy minimization problem. In this paper, we develop an analytical method to estimate energy consumption on-line with the leakage/temperature dependency taken into consideration. Based on this method, we develop an on-line scheduling algorithm to reduce the overall energy consumption for a hard real-time system scheduled according to the Earliest Deadline First (EDF) policy. Our experimental results show that the proposed energy estimation method can achieve up to 210X speedup compared with an existing approach while still maintaining high accuracy. In addition, with a large number of different test cases, the proposed energy saving scheduling method consistently outperforms two closely related researches in average by 10% and 14% respectively.

This paper presents a new semi-partitioned approach to schedule sporadic tasks on multi-core platform based on the Rate Monotonic Scheduling (RMS) policy. Our approach exploits the well known fact that harmonic tasks have better schedulablility than non-harmonic ones on a single processor. The challenge for our approach, however, is how to take advantage of this fact to assign and split appropriate tasks on different processors in the semi-partitioned approach. We formally prove that our scheduling approach can successfully schedule any task sets with system utilizations bounded by the Liu&Layland's bound. Our extensive experiment results demonstrate that the proposed algorithm can significantly improve the scheduling performance compared with the previous work.

With the high integration density and complexity of the modern multi-core platform, thermal problems become more and more significant for both the manufacture and system designer. Dynamic thermal management technique is one effective and efficient way to mitigate and avoid thermal emergences. In this paper, we propose a novel predictive dynamic thermal management algorithm to maximize the multi-core system throughput while satisfying the peak temperature constraints. Different from the conventional approaches, we found that it is not necessarily always a good choice to migrate a hot task to the core with the lowest temperature. Instead, in our algorithm, we develop a new temperature prediction technique and migration scheme that take the local temperature of a core as well as the impacts from neighboring cores into considerations. According to our experiment results on a practical Intel desktop platform, the proposed algorithm can significantly improve the throughput compared with the conventional approach.

One common approach for partitioned multiprocessor scheduling problem is to transform this problem into a traditional bin-packing problem, with the utilization of a task being the "size" of the object and the utilization bound of a processor being the "capacity" of the bin. However, this approach ignores the fact that some implicit relations among tasks may significantly affect the feasibility of the tasks allocated to a processor. In this paper, we present a novel multiprocessor partitioned scheduling algorithm for fixed-priority sporadic real-time tasks based on the Rate Monotonic Scheduling (RMS) policy. Our approach takes advantage of the fact that harmonic tasks can achieve a much higher processor utilization than that defined by a utilization bound. As demonstrated in our experiment results, when taking the task period relationship into consideration, our algorithm can achieve a significant improvement over previous work.