Randomized Algorithms for Scheduling Multi-Resource Jobs in the Cloud
Randomized Algorithms for Scheduling Multi-Resource Jobs in the Cloud
复制标题
DOI：
10.1109/tnet.2018.2863647
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Konstantinos Psychas;Javad Ghaderi
中科院分区：
文献类型：
--
作者：
Konstantinos Psychas;Javad Ghaderi
我们考虑在分布式服务器平台上调度具有多资源需求（CPU，内存和磁盘）的作业的问题，其动机是数据并行和云计算应用。作业随时间动态地到达，并且在其服务期间需要一定量的多个资源。当一个作业到达时，它被排队等待，然后由一个有足够剩余资源的服务器来服务它。作业的调度受到两个约束：1）打包约束：如果多个作业的累积资源需求不超过服务器的容量，则它们可以由一个服务器同时服务; 2）非抢占：为了避免代价高昂的抢占，一旦作业在服务器中被调度，其服务就不能被中断或迁移到另一个服务器。现有调度算法依赖于具有低复杂度但可能具有较差吞吐量的装箱算法，或者依赖于可以实现最大吞吐量但随着时间的推移反复需要求解或近似硬组合问题（背包）的实例的MaxWeight解决方案。在本文中，我们提出了一个随机调度算法放置在服务器上的作业，可以实现最大的吞吐量与低复杂度。该算法是自然分布的，每个队列和每个服务器在每个时间单位只需要执行恒定数量的操作。广泛的仿真结果，使用合成和真实的交通痕迹，提出了评估吞吐量和延迟性能相比，以前的算法。
We consider the problem of scheduling jobs with multiple-resource requirements (CPU, memory, and disk) in a distributed server platform, motivated by data-parallel and cloud computing applications. Jobs arrive dynamically over time and require certain amount of multiple resources for the duration of their service. When a job arrives, it is queued and later served by one of the servers that has sufficient remaining resources to serve it. The scheduling of jobs is subject to two constraints: 1) packing constraints: multiple jobs can be served simultaneously by a single server if their cumulative resource requirement does not exceed the capacity of the server, and 2) non-preemption: to avoid costly preemptions, once a job is scheduled in a server, its service cannot be interrupted or migrated to another server. Prior scheduling algorithms rely on either bin packing heuristics which have low complexity but can have a poor throughput, or MaxWeight solutions that can achieve maximum throughput but repeatedly require to solve or approximate instances of a hard combinatorial problem (Knapsack) over time. In this paper, we propose a randomized scheduling algorithm for placing jobs in servers that can achieve maximum throughput with low complexity. The algorithm is naturally distributed and each queue and each server needs to perform only a constant number of operations per time unit. Extensive simulation results, using both synthetic and real traffic traces, are presented to evaluate the throughput and delay performance compared to prior algorithms.