Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Load balanced mapping of distributed objects to minimize network communication
Blekinge Tekniska Högskola, Institutionen för datavetenskap och ekonomi.
Ansvarig organisation
1996 (Engelska)Ingår i: Journal of Parallel and Distributed Computing, ISSN 0743-7315, E-ISSN 1096-0848, s. 117-136Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

This paper introduces a new load balancing and communication minimizing heuristic used in the In verse Remote Procedure Call (IRPC) system. While the paper briefly describes the IRPC system, the focus is on the new IRPC assignment heuristic. The IRPC compiler maps a distributed program to a graph that represents program objects and their dependencies (due to invocations and parameter passing) as nodes and edges, respectively. In the graph, the system preserves conditional and iterative flows, records network transmission and execution costs, and marks nodes that have to reside at specific network sites. The graph is then partitioned by the heuristic to derive a (sub)optimal node assignment to network sites minimizing load balancing and network data transport. The resulting program partition is then reflected in the physical object distribution, and remote and local object communication is transparently implemented. The compiler and run-time system use efficient implementation techniques such as type prediction, inlining, splitting and subprogram passing. The last of these allows remote code to be copied to local data, as an alternative to copying data to the remote site, whenever this will reduce network data transport. The IRPC graph partitioning heuristic operates in time O(E(log d + l + log M)), where M is the number of network sites, E is the number of communication edges, and d is the maximum degree of a node; l is a parameter of the algorithm, and can vary between 1 and N, where N is the number of communicating objects. This complexity is more nearly independent of M, and considerably better in terms of E and N, than that of previously known related algorithms, such as A*, which employs backtracking and is potentially exponential, or the max-flow/min-cut class of network flow algorithms or heuristics which tend to be at least of Omega(MN(2)E), and it can be made (by choosing l appropriately) as efficient as even such fast heuristics as heaviest-edge-first, minimal communication, and Kernighan-Lin. In an extensive quantitative evaluation, the heuristic has been demonstrated to perform very well, giving on the average 75% traffic cost reductions for over 95% of the programs when compared to random partitioning, and outperforming in cost reduction and actual execution time the three aforementioned fast heuristics, even with a large l. Thus, to the best of our knowledge, this is the first report of a well-performing assignment heuristic that is both essentially linear in the number of communication edges, and better than existing, established heuristics of no better complexity. (C) 1996 Academic Press, Inc.

Ort, förlag, år, upplaga, sidor
SAN DIEGO: ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS , 1996. s. 117-136
Nationell ämneskategori
Programvaruteknik
Identifikatorer
URN: urn:nbn:se:bth-8159ISI: A1996UP05000001Lokalt ID: oai:bth.se:forskinfo14DBCB45B4398A03C12575B000210B44OAI: oai:DiVA.org:bth-8159DiVA, id: diva2:835848
Tillgänglig från: 2012-09-18 Skapad: 2009-05-08 Senast uppdaterad: 2018-01-11Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Bosch, Jan

Sök vidare i DiVA

Av författaren/redaktören
Bosch, Jan
Av organisationen
Institutionen för datavetenskap och ekonomi
I samma tidskrift
Journal of Parallel and Distributed Computing
Programvaruteknik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 86 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf