Name
Abstract | ||
|---|---|---|
We discuss iterative nearest neighbor load balancing schemes on processor networks which are represented by a cartesian product of graphs like e.g. tori or hypercubes. By the use of the Alternating-Direction Loadbalancing scheme, the number of load balance iterations decreases by a factor of 2 for this type of graphs. The resulting flow is analyzed theoretically and it can be very high for certain cases. Therefore, we furthermore present the Mixed-Direction scheme which needs the same number of iterations but results in a much smaller flow.Apart from that, we present a simple optimal diffusion scheme for general graphs which calculates a minimal balancing flow in the l2 norm. The scheme is based on the spectrum of the graph representing the network and needs only m-1 iterations in order to balance the load with m being the number of distinct eigenvalues. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/3-540-48311-X_36 | Euro-Par |
Keywords | Field | DocType |
certain case,simple optimal diffusion scheme,nearest neighbor load,mixed-direction scheme,smaller flow,resulting flow,minimal balancing flow,load balance iterations decrease,alternating-direction loadbalancing scheme,cartesian product,load balance,nearest neighbor | k-nearest neighbors algorithm,Load balancing (computing),Computer science,Scheduling (computing),Cartesian product of graphs,Parallel computing,Multiprocessing,Norm (mathematics),Hypercube,Eigenvalues and eigenvectors,Distributed computing | Conference |
Volume | ISSN | ISBN |
1685 | 0302-9743 | 3-540-66443-2 |
Citations | PageRank | References |
15 | 1.11 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Elsässer | 1 | 63 | 6.54 |
| Andreas Frommer | 2 | 25 | 1.91 |
| Burkhard Monien | 3 | 2199 | 279.35 |
| Robert Preis | 4 | 336 | 25.95 |