A NETWORK FLOW MODEL FOR LOAD BALANCING IN CIRCUIT-SWITCHED MULTICOMPUTERS

被引：6
作者：
BOKHARI, SH
机构：
[1] Department of Electrical Engineering, University of Engineering and Technology, Lahore
来源：
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1993年 / 4卷 / 06期
基金：
美国国家航空航天局;
关键词：
CONTENTION; CIRCUIT-SWITCHED MACHINES; HYPERCUBES; LOAD BALANCING; MESHES; MINIMUM COST FLOW ALGORITHM; NETWORK FLOW;
D O I：
10.1109/71.242158
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 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 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 us to determine efficiently a maximum contention free matching of sources to sinks which, in turn, tells us how much of the given imbalance can be eliminated without contention.
引用
收藏
页码：649 / 657
页数：9
相关论文
共 21 条
  • [1] ILLIAC 4 COMPUTER
    BARNES, GH
    BROWN, RM
    KATO, M
    KUCK, DJ
    SLOTNICK, DL
    STOKES, RA
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1968, C 17 (08) : 746 - &
  • [2] BOKHARI SH, 1990, ICASE NASA CR182055
  • [3] Bomans L., 1989, Concurrency: Practice and Experience, V1, P3, DOI 10.1002/cpe.4330010103
  • [4] Borkar S., 1988, Proceedings. Supercomputing '88 (IEEE Cat. No.88CH2617-9), P330, DOI 10.1109/SUPERC.1988.44670
  • [5] BUSACKER RG, 1964, FINITE GRAPHS NETWOR
  • [6] BUSACKER RG, 1961, ORO15 J HOPK U OP RE
  • [7] CHITTOR S, 1989, CPS8919 MICH STAT U
  • [8] DALLY WJ, 1987, IEEE T COMPUT, V36, P547, DOI 10.1109/TC.1987.1676939
  • [9] Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
  • [10] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS
    EDMONDS, J
    KARP, RM
    [J]. JOURNAL OF THE ACM, 1972, 19 (02) : 248 - &
123