Access Restriction

Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2002
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Clusters ♦ Contrary behavior ♦ Distributed servers ♦ Fairness ♦ Heavy-tailed workloads ♦ High variance ♦ Job scheduling ♦ Load balancing ♦ Load sharing ♦ Supercomputing ♦ Task assignment
Abstract We consider a distributed server system and ask which policy should be used for assigning jobs (tasks) to hosts. In our server, jobs are $\textit{not}$ preemptible. Also, the job's service demand is $\textit{not}$ known a priori. We are particularly concerned with the case where the workload is heavy-tailed, as is characteristic of many empirically measured computer workloads. We analyze several natural task assignment policies and propose a new one TAGS (Task Assignment based on Guessing Size). The TAGS algorithm is counterintuitive in many respects, including load $\textit{un}balancing,$ $\textit{non}-work-conserving,$ and $\textit{fairness}.$ We find that under heavy-tailed workloads, TAGS can outperform all task assignment policies known to us by several orders of magnitude with respect to both mean response time and mean slowdown, provided the system load is not too high. We also introduce a new practical performance metric for distributed servers called server expansion. Under the server expansion metric, TAGS significantly outperforms all other task assignment policies, regardless of system load.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2002-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 49
Issue Number 2
Page Count 29
Starting Page 260
Ending Page 288

Open content in new tab

   Open content in new tab
Source: ACM Digital Library