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

School of Arts and Sciences, Computer Science

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

32 Scopus citations

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

All Science Journal Classification (ASJC) codes

Software
Safety, Risk, Reliability and Quality

Cite this

@conference{69ff410b16b241dbb8652ad997caec92,

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

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this