TY - GEN

T1 - On the price of heterogeneity in parallel systems

AU - Brighten Godfrey, P.

AU - Karp, Richard M.

PY - 2006/10/16

Y1 - 2006/10/16

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 completion time 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. 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 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.

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 completion time 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. 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 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.

KW - Heterogeneity

KW - Majorization

KW - Scheduling

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

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

M3 - Conference contribution

AN - SCOPUS:33749551301

SN - 1595934529

SN - 9781595934529

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 84

EP - 92

BT - SPAA 2006

T2 - SPAA 2006: 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures

Y2 - 30 July 2006 through 2 August 2006

ER -