TY - JOUR

T1 - On the price of heterogeneity in parallel systems

AU - Godfrey, P. Brighten

AU - Karp, Richard M.

N1 - Funding Information:
Acknowledgements The authors thank the anonymous reviewers for useful corrections and suggestions, and Christos Papadimitriou, Satish Rao, Scott Shenker, Ion Stoica, David Molnar, and Lakshminarayanan Subramanian for helpful comments. This paper is based upon work supported under a National Science Foundation Graduate Research Fellowship.

PY - 2009/8

Y1 - 2009/8

N2 - 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 makespan of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity α when for any workload, cost cannot increase by more than a factor α if node capacities become arbitrarily more heterogeneous. The price of heterogeneity also upper bounds the "value of parallelism": the maximum benefit obtained by increasing parallelism at the expense of decreasing processor speed. We give constant or logarithmic bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that in many cases, increasing heterogeneity can never be much of a disadvantage.

AB - 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 makespan of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity α when for any workload, cost cannot increase by more than a factor α if node capacities become arbitrarily more heterogeneous. The price of heterogeneity also upper bounds the "value of parallelism": the maximum benefit obtained by increasing parallelism at the expense of decreasing processor speed. We give constant or logarithmic bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that in many cases, increasing heterogeneity can never be much of a disadvantage.

KW - Heterogeneity

KW - Makespan

KW - Parallel systems

KW - Precedence constrained scheduling

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=67449156319&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67449156319&partnerID=8YFLogxK

U2 - 10.1007/s00224-008-9102-5

DO - 10.1007/s00224-008-9102-5

M3 - Article

AN - SCOPUS:67449156319

VL - 45

SP - 280

EP - 301

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -