Philip Brighten Godfrey and Richard M. Karp

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-81

May 28, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-81.pdf

Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system's performance as a function of its nodes' capacities C and workload W (such as the completion time of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity \alpha when for any workload, cost cannot increase by more than a factor \alpha if node capacities become arbitrarily more heterogeneous. We give constant bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that increasing heterogeneity can never be much of a disadvantage. On the other hand, with the introduction of timing constraints such as release times or precedence constraints on the jobs, the dependence on node capacities becomes more complex, so that increasing heterogeneity may be quite detrimental.

---

BibTeX citation:

@techreport{Godfrey:EECS-2006-81,
    Author= {Godfrey, Philip Brighten and Karp, Richard M.},
    Title= {On the Price of Heterogeneity in Parallel Systems},
    Year= {2006},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-81.html},
    Number= {UCB/EECS-2006-81},
    Abstract= {Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system's performance as a function of its nodes' capacities C and workload W (such as the completion time of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity \alpha  when for any workload, cost cannot increase by more than a factor \alpha  if node capacities become arbitrarily more heterogeneous. We give constant bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that increasing heterogeneity can never be much of a disadvantage. On the other hand, with the introduction of timing constraints such as release times or precedence constraints on the jobs, the dependence on node capacities becomes more complex, so that increasing heterogeneity may be quite detrimental.},
}

EndNote citation:

%0 Report
%A Godfrey, Philip Brighten 
%A Karp, Richard M. 
%T On the Price of Heterogeneity in Parallel Systems
%I EECS Department, University of California, Berkeley
%D 2006
%8 May 28
%@ UCB/EECS-2006-81
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-81.html
%F Godfrey:EECS-2006-81