首页> 外文期刊>IEEE/ACM Transactions on Networking >Randomized Algorithms for Scheduling Multi-Resource Jobs in the Cloud
【24h】

Randomized Algorithms for Scheduling Multi-Resource Jobs in the Cloud

机译:云中调度多资源作业的随机算法

获取原文
获取原文并翻译 | 示例

摘要

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.
机译:我们考虑在并行服务器和云计算应用程序的推动下,在分布式服务器平台中调度具有多资源需求(CPU,内存和磁盘)的作业的问题。作业会随时间动态到达,并且在服务期间需要一定数量的多种资源。作业到达时,将其排队,然后由具有足够剩余资源来为其提供服务的服务器之一为其提供服务。作业的调度受到两个约束:1)打包约束:如果单个作业的累积资源需求不超过服务器的容量,则可以由一个服务器同时处理多个作业,以及2)非抢占:避免昂贵的抢占,一旦在服务器中计划了作业,就不能中断其服务或将其迁移到另一台服务器。先前的调度算法依赖于具有低复杂度但吞吐量不佳的bin打包启发式算法,或可以实现最大吞吐量但随着时间的推移反复需要解决或逼近硬组合问题(背包)的MaxWeight解决方案。在本文中,我们提出了一种用于在服务器中放置作业的随机调度算法,该算法可以在不降低复杂度的情况下实现最大吞吐量。该算法是自然分布的,每个队列和每个服务器仅需要在每个时间单位执行恒定数量的操作。提出了使用综合流量跟踪和实际流量跟踪的广泛仿真结果,以评估吞吐量和延迟性能(与现有算法相比)。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号