Your Search Results

Use this resource - and many more! - in your textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

A network flow model for load balancing in circuit-switched multicomputers

By: Bokhari, S.H.;

1993 / IEEE


This item was taken from the IEEE Periodical ' A network flow model for load balancing in circuit-switched multicomputers ' In multicomputers that utilize circuit switching or wormhole routing, communication overhead depends largely on link contention-the variation due to distance between nodes is negligible. This has a major impact on the load balancing problem. In this case there are some nodes with an excess load (sources) and other with a deficit load (sinks). A matching of sources to sinks is required to avoid contention. The problem is made complex by the hardwired routing on currently available machines: The user can control only which nodes communicate but not how the messages are routed. Network flow models of message flow in the mesh and the hypercube have been developed to solve this problem. The crucial property of these models is the correspondence between minimum cost flows and correctly routed messages. To solve a given load balancing problem, a minimum cost flow algorithm is applied to the network. This permits the efficient determination of a maximum contention free matching of sources to sinks that, in turn, tells how much of the given imbalance can be eliminated without contention.<>