Multi-objective scheduling of many tasks in cloud platforms |
| |
| Affiliation: | 1. Kavli Institute for Astrophysics and Space Research, Massachusetts Institute of Technology, Cambridge, MA 02139, USA;2. Research Institute of Information Technology, Tsinghua University, Beijing, 100084, China;3. Department of Computer Science, State University of New York, New Paltz, NY 12561, USA;4. Department of Electrical and Computer Engineering, North Dakota State University, Fargo, ND 58108-6050, USA;5. Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089-2562, USA;1. College of Materials Science and Engineering, Nanjing Tech University, Nanjing 210009, China;2. Nanjing Sanle Electronic Information Industry Group Co., Ltd., Nanjing 211800, China;3. State Key Laboratory of High Performance Ceramics and Superfine Microstructures, Shanghai Institute of Ceramics, Chinese Academy of Sciences, Shanghai 200050, China;1. Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran;2. Department of Industrial Engineering, Faculty of Engineering, Tarbiat Modares University, Tehran, Iran |
| |
| Abstract: | The scheduling of a many-task workflow in a distributed computing platform is a well known NP-hard problem. The problem is even more complex and challenging when the virtualized clusters are used to execute a large number of tasks in a cloud computing platform. The difficulty lies in satisfying multiple objectives that may be of conflicting nature. For instance, it is difficult to minimize the makespan of many tasks, while reducing the resource cost and preserving the fault tolerance and/or the quality of service (QoS) at the same time. These conflicting requirements and goals are difficult to optimize due to the unknown runtime conditions, such as the availability of the resources and random workload distributions. Instead of taking a very long time to generate an optimal schedule, we propose a new method to generate suboptimal or sufficiently good schedules for smooth multitask workflows on cloud platforms.Our new multi-objective scheduling (MOS) scheme is specially tailored for clouds and based on the ordinal optimization (OO) method that was originally developed by the automation community for the design optimization of very complex dynamic systems. We extend the OO scheme to meet the special demands from cloud platforms that apply to virtual clusters of servers from multiple data centers. We prove the suboptimality through mathematical analysis. The major advantage of our MOS method lies in the significantly reduced scheduling overhead time and yet a close to optimal performance. Extensive experiments were carried out on virtual clusters with 16 to 128 virtual machines. The multitasking workflow is obtained from a real scientific LIGO workload for earth gravitational wave analysis. The experimental results show that our proposed algorithm rapidly and effectively generates a small set of semi-optimal scheduling solutions. On a 128-node virtual cluster, the method results in a thousand times of reduction in the search time for semi-optimal workflow schedules compared with the use of the Monte Carlo and the Blind Pick methods for the same purpose. |
| |
| Keywords: | Cloud computing Many-task computing Ordinal optimization Performance evaluation Virtual machines Workflow scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
