Scheduling parallel tasks with energy and time constraints on multiple manycore processors in a cloud computing environment

When multiple manycore processors in a data center for cloud computing are shared by a large number parallel tasks simultaneously, we are facing the problem of allocating the cores to the tasks and scheduling the tasks, such that the system performance is optimized or the energy consumption is minimized. Furthermore, such core allocation and task scheduling should be conducted with energy constraints or performance constraints. The problems of energy and time constrained scheduling of precedence constrained parallel tasks on multiple manycore processors in a cloud computing environment are defined as optimization problems. Lower bounds for optimal solutions are generalized from a single parallel computing system to multiple parallel computing systems. Our approach in this paper is to design and analyze the performance of heuristic algorithms that employ the equal-speed method. Pre-power-determination algorithms and post-power-determination algorithms are developed for both energy and time constrained scheduling of precedence constrained parallel tasks on multiple manycore processors with continuous or discrete speed levels. The performance of these algorithms are evaluated analytically and experimentally. Our main strategy is to embed the equal-speed method into our algorithms, which not only makes our analysis possible, but also yields good performance of our algorithms.