Engineering diffusive load balancing algorithms using experiments

Ralf Diekmann, S. Muthukrishnan, Madhu V. Nayakkankuppam

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We study a distributed load balancing problem on arbitrary graphs. First Order (F0) and Second Order (SD) schemes are popular local diffusive schedules for this problem. To use them, several parameters have to be chosen carefully. Determining the "optimal" parameters analytically is difficult, and on a practical level, despite the widespread use of these schemes, little is known on how relevant parameters must be set. We employ systematic experiments to engineer the choice of relevant parameters in first and second order schemes. We present a centralized polynomial time algorithm for choosing the "optimal" F0 scheme based on sere[definite programming. Based on the empirical evidence from our implementation of this algorithm, we pose conjectures on the closed-form solution of optimal F0 schemes for various graphs. We also present a heuristic algorithm to locally estimate relevant parameters in the F0 and S0 schemes; our estimates are fairly accurate compared to those based on expensive global communication. Finally, we show that the F0 and S0 schemes that use approximate values rather than the optimal parameters, can be improved using a new iterative scheme that we introduce here; this scheme is of independent interest. The software we have developed for our implementations is available freely, and can serve as a platform for experimental research in this area. Our methods are being included in Paderborn, the Paderborn Finite Element Library [1].

    Original languageEnglish (US)
    Title of host publicationSolving Irregularly Structured Problems in Parallel - 4th International Symposium, IRREGULAR 1997, Proceedings
    EditorsGianfranco Bilardi, Gianfranco Bilardi, Afonso Ferreira, Reinhard Luling, Jose Rolim
    PublisherSpringer Verlag
    Pages111-122
    Number of pages12
    ISBN (Print)3540631380, 9783540631385
    DOIs
    StatePublished - 1997
    Event4th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1997 - Paderborn, Germany
    Duration: Jun 12 1997Jun 13 1997

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1253
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference4th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1997
    CountryGermany
    CityPaderborn
    Period6/12/976/13/97

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Engineering diffusive load balancing algorithms using experiments'. Together they form a unique fingerprint.

    Cite this