Paper Info
Title
Heterogeneity In Computing: Insights From A Worksharing Scheduling Problem
Abstract
Heterogeneity complicates the use of multicomputer platforms. Can it also enhance their performance? How can one measure the power of a heterogeneous assemblage of computers ("cluster"), in absolute terms (how powerful is this cluster) and relative terms (which cluster is more powerful)? Is a cluster that has one super-fast computer and the rest of "average" speed more/less powerful than one all of whose computers are "moderately" fast? If you can replace just one computer in a cluster with a faster one, should you replace the fastest? the slowest? A result concerning "worksharing" in heterogeneous clusters provides a highly idealized, yet algorithmically meaningful, framework for studying such questions in a way that admits rigorous analysis and formal proof. We encounter some surprises as we answer the preceding questions (perforce, within the idealized framework). Highlights: (1) If one can replace only one computer in a cluster by a faster one, it is (almost) always most advantageous to replace the fastest one. (2) If the computers in two clusters have the same mean speed, then the cluster with the larger variance in speed is (almost) always more productive (verified analytically for small clusters and empirically for large ones.) (3) Heterogeneity can actually enhance a cluster's computing power.
Year
DOI
Venue
2011
10.1142/S0129054111008829
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
Heterogeneous multicomputer systems, cluster computing, divisible load scheduling, worksharing
Cluster (physics),Job shop scheduling,Computer science,Parallel computing,Relative term,Theoretical computer science,Computer cluster,Formal proof
Journal
Volume
Issue
ISSN
22
6
0129-0541
Citations 
PageRank 
References 
0
0.34
25
Authors
2
Name
Order
Citations
PageRank
Arnold L. Rosenberg12107640.21
Ron Chi-Lung Chiang21085.44