First and second order diffusive methods for rapid, coarse, distributed load balancing

Bhaskar Ghosh; S. Muthukrishnan; Martin H. Schultz

First and second order diffusive methods for rapid, coarse, distributed load balancing

Bhaskar Ghosh, S. Muthukrishnan, Martin H. Schultz

Research output: Contribution to conference › Paper › peer-review

Abstract

The problem of modeling load balancing is considered in a variety of distributed settings. A new direction in diffusive schedules was introduced by considering schedules that are modeled as: w¹ = Mw⁰; w^t+1 = βMw^t+(1-β)w^t-1 for some appropriate β, called the second order schedules. In the idealized setting of weights being real numbers, results indicate that β can be chosen because the second order schedule is significantly faster than the first order method. Consequently, an algorithm that performs coarse load balancing rapidly and can be used in a number of applications is produced.

Original language	English (US)
Pages	72-81
Number of pages	10
State	Published - 1996
Event	Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures - Padua, Italy Duration: Jun 24 1996 → Jun 26 1996

Other

Other	Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures
City	Padua, Italy
Period	6/24/96 → 6/26/96

ASJC Scopus subject areas

Software
Safety, Risk, Reliability and Quality

Cite this

@conference{46ad4d09ddcd4c9dad40d30d3ea0ebe9,

title = "First and second order diffusive methods for rapid, coarse, distributed load balancing",

abstract = "The problem of modeling load balancing is considered in a variety of distributed settings. A new direction in diffusive schedules was introduced by considering schedules that are modeled as: w1 = Mw0; wt+1 = βMwt+(1-β)wt-1 for some appropriate β, called the second order schedules. In the idealized setting of weights being real numbers, results indicate that β can be chosen because the second order schedule is significantly faster than the first order method. Consequently, an algorithm that performs coarse load balancing rapidly and can be used in a number of applications is produced.",

author = "Bhaskar Ghosh and S. Muthukrishnan and Schultz, {Martin H.}",

year = "1996",

language = "English (US)",

pages = "72--81",

note = "Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures ; Conference date: 24-06-1996 Through 26-06-1996",

}

TY - CONF

T1 - First and second order diffusive methods for rapid, coarse, distributed load balancing

AU - Ghosh, Bhaskar

AU - Muthukrishnan, S.

AU - Schultz, Martin H.

PY - 1996

Y1 - 1996

N2 - The problem of modeling load balancing is considered in a variety of distributed settings. A new direction in diffusive schedules was introduced by considering schedules that are modeled as: w1 = Mw0; wt+1 = βMwt+(1-β)wt-1 for some appropriate β, called the second order schedules. In the idealized setting of weights being real numbers, results indicate that β can be chosen because the second order schedule is significantly faster than the first order method. Consequently, an algorithm that performs coarse load balancing rapidly and can be used in a number of applications is produced.

AB - The problem of modeling load balancing is considered in a variety of distributed settings. A new direction in diffusive schedules was introduced by considering schedules that are modeled as: w1 = Mw0; wt+1 = βMwt+(1-β)wt-1 for some appropriate β, called the second order schedules. In the idealized setting of weights being real numbers, results indicate that β can be chosen because the second order schedule is significantly faster than the first order method. Consequently, an algorithm that performs coarse load balancing rapidly and can be used in a number of applications is produced.

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

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

M3 - Paper

AN - SCOPUS:0030397010

SP - 72

EP - 81

T2 - Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures

Y2 - 24 June 1996 through 26 June 1996

ER -

First and second order diffusive methods for rapid, coarse, distributed load balancing

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this