Scheduling Jobs with Random Resource Requirements in Computing Clusters
| Autor: | Javad Ghaderi, Konstantinos Psychas |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Networking and Internet Architecture (cs.NI)
FOS: Computer and information sciences 021103 operations research Job shop scheduling Computer science Distributed computing 0211 other engineering and technologies 020206 networking & telecommunications Throughput 02 engineering and technology Scheduling (computing) Computer Science - Networking and Internet Architecture Computer Science - Distributed Parallel and Cluster Computing Server 0202 electrical engineering electronic engineering information engineering Cluster (physics) Distributed Parallel and Cluster Computing (cs.DC) Cluster analysis |
| Zdroj: | INFOCOM |
| DOI: | 10.48550/arxiv.1901.05998 |
| Popis: | We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource requirements (e.g. memory requirements) arrive over time and must be served by a cluster of servers, each with a finite resource capacity. To improve throughput and delay, the scheduler can pack as many jobs as possible in the servers subject to their capacity constraints. Motivated by the ever-increasing complexity of workloads in shared clusters, we consider a setting where the jobs’ resource requirements belong to a very large number of diverse types or, in the extreme, even infinitely many types, e.g. when resource requirements are drawn from an unknown distribution over a continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) dimensional setting. We first characterize a fundamental limit on the maximum throughput in such setting, and then develop oblivious scheduling algorithms that have tow complexity and can achieve at least 1/2 and 2/3 of the maximum throughput, without the knowledge of traffic or resource requirement distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|