NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
A network flow model for load balancing in circuit-switched multicomputersIn 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 excess load (sources) and others with deficit load (sinks) and it is required to find a matching of sources to sinks that avoids 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 were 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 one to determine efficiently a maximum contention free matching of sources to sinks which, in turn, tells one how much of the given imbalance can be eliminated without contention.
Document ID
19900014661
Acquisition Source
Legacy CDMS
Document Type
Preprint (Draft being sent to journal)
Authors
Bokhari, Shahid H. (University of Engineering and Technology Lahore, Pakistan)
Date Acquired
September 6, 2013
Publication Date
May 1, 1990
Subject Category
Computer Systems
Report/Patent Number
NAS 1.26:182049
ICASE-90-38
AD-A227492
NASA-CR-182049
Accession Number
90N23977
Funding Number(s)
CONTRACT_GRANT: NAS1-18605
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Related Records

There are no records associated with this record.
No Preview Available