We consider the problem of redistributing data on homogeneous and heterogeneous rings
of processors. The problem arises in several applications, after each invocation of
a load-balancing mechanism (but we do not discuss the load-balancing mechanism
itself). We provide algorithms that aim at optimizing the data redistribution, both
for unidirectional and bidirectional rings. One major contribution of the paper is
that we are able to prove the optimality of the proposed algorithms in all cases
except that of a bidirectional heterogeneous ring, for which the problem remains open.
Barbosa, J.
,
Tavares, J.
, and
Padilha, A. J.
2000.
Linear algebra algorithms in a heterogeneous cluster of personal computers
. Proceedings of the 9th Heterogeneous Computing Workshop (HCW
2000), Cancun, Mexico, May 1, IEEE
Computer Society Press, Los Alamitos, CA, pp.
147–159
.
2.
Beaumont, O.
,
Boudet, V.
,
Petitet, A.
,
Rastello, F.
, and
Robert, Y.2001a.
A proposal for a heterogeneous cluster ScaLAPACK (dense linear solvers)
. IEEE Transactions on Computers50(10):
1052–1070
.
3.
Beaumont, O.
,
Boudet, V.
,
Rastello, F.
, and
Robert, Y.2001b.
Matrix multiplication on heterogeneous platforms
. IEEE Transactions on Parallel and Distributed Systems12(10):
1033–1051
.
4.
Bevilacqua, A.1999.
A dynamic load balancing method on a heterogeneous cluster of workstations
. Informatica23(1):
49–56
.
5.
Blackford, L. S.
,
Choi, J.
,
Cleary, A.
,
D’Azevedo, E.
,
Demmel, J.
,
Dhillon, I.
,
Dongarra, J.
,
Hammarling, S.
,
Henry, G.
,
Petitet, A.
,
Stanley, K.
,
Walker, D.
, and
Whaley, R. C.1997. ScaLAPACK Users’ Guide,
SIAM, Philadelphia
.
6.
Bourgeade, A.
and
Nkonga, B.2004.
Dynamic load balancing computation of pulses propagating in a nonlinear medium
. Journal of Supercomputing28(3):
279–294
.
7.
Brunie, L.
,
Flory, A.
, and
Kosch, H.
1995.
New static scheduling and elastic load balancing methods for parallel query processing
. of the Basque International Workshop on Information Technology
(BIWIT),San Sebastian, Spain,
July, IEEE Computer Society Press, Los Alamitos, CA.
8.
Buyya, R.1999. High Performance Cluster Computing. Volume 1: Architecture and
Systems,
Prentice-Hall, Upper Saddle River, NJ
.
9.
Crandall, P. E.
and
Quinn, M. J.
1993.
Block data decomposition for data-parallel programming on a heterogeneous
workstation network
. Proceedings of the IEEE International Symposium on High
Performance Distributed Computing (HPDC),Spokane,
WA, July 20–23, IEEE Computer Society
Press, Los Alamitos, CA, pp.
42–49
.
10.
Deelman, E.
and
Szymanski, B.
1998.
Dynamic load balancing in parallel discrete event simulation for spatially
explicit problems
. Proceedings of the Workshop on Parallel and Distributed
Simulation (PADS),Banff, Alberta, Canada,
May 26–29, IEEE Computer Society Press, Los
Alamitos, CA, pp.
46–53
.
11.
Desprez, F.
,
Dongarra, J.
,
Petitet, A.
,
Randriamaro, C.
, and
Robert, Y.1998.
Scheduling block-cyclic array redistribution
. IEEE Transactions on Parallel and Distributed Systems9(2):
192–205
.
12.
Flaherty, J. E.
,
Loy, R. M.
,
özturan, C.
,
Shephard, M. S.
,
Szymanski, B. K.
,
Teresco, J. D.
, and
Ziantz, L. H.1997a.
Parallel structures and dynamic load balancing for adaptive finite element computation
. Applied Numerical Mathematics26(1–2):
241–263
.
13.
Flaherty, J. E.
,
Loy, R. M.
,
Shephard, M. S.
,
Szymanski, B. K.
,
Teresco, J. D.
, and
Ziantz, L. H.1997b.
Adaptive local refinement with octree load balancing for the parallel
solution of three-dimensional conservation laws
. Journal of Parallel and Distributed Computing47(2):
139–152
.
14.
Garcia, J.
,
Ayguadé, E.
, and
Labarta, J.2001.
A framework for integrating data alignment, distribution, and
redistribution in distributed memory multiprocessors
. IEEE Transactions on Parallel and Distributed Systems12(4):
416–431
.
15.
Hamdi, M.
and
Lee, C.
1995.
Dynamic load balancing of data parallel applications on a distributed network
. Proceedings of ICS’95,ACM, New
York, pp.
170–179
.
16.
Hsu, C.
,
Chung, Y.
,
Yang, D.
, and
Dow, C.2001.
A generalized processor mapping technique for array redistribution
. IEEE Transactions on Parallel and Distributed Systems12(7):
743–757
.
17.
Hu, Y.
and
Blake, R.1999.
Load balancing for unstructured mesh applications
. Parallel and Distributed Computing Practices2(3).
18.
Kaddoura, M.
,
Ranka, S.
, and
Wang, A.1996.
Array decomposition for nonuniform computational environments
. Journal of Parallel and Distributed Computing36:
91–105
.
19.
Kalns, E. T.
and
Ni, L. M.1995.
Processor mapping techniques towards efficient data redistribution
. IEEE Transactions on Parallel and Distributed Systems6(12):
1234–1247
.
20.
Knoop, J.
and
Mehofer, E.2002.
Distribution assignment placement: effective optimization of redistribution costs
. IEEE Transactions on Parallel and Distributed Systems13(6):
628–647
.
21.
Koelbel, C. H.
,
Loveman, D. B.
,
Schreiber, R. S.
,
Steele, G. L. Jr.
, and
Zosel, M. E.1994. The High Performance Fortran Handbook,
MIT Press, Cambridge, MA
.
22.
Kremer, U.
1993.
NP-completeness of dynamic remapping
. Proceedings of the 4th Workshop on Compilers for Parallel
Computers, Delft, the Netherlands. Also available as
Rice Technical Report CRPC-TR93330-S.
23.
Lan, Z.
,
Taylor, V.
, and
Bryan, G.
2001.
Dynamic load balancing of samr applications on distributed systems
. Proceedings of the ACM/IEEE conference on
Supercomputing, Denver, CO, November
10–16, IEEE Computer Society Press, Los Alamitos, CA.
24.
Lee, C.
and
Hamdi, M.1995.
Parallel image processing applications on a network of workstations
. Parallel Computing21:
137–160
.
25.
Miguet, S.
and
Robert, Y.
1992.
Elastic load balancing for image processing algorithms
. Parallel Computation, Lecture Notes in Computer
ScienceVol. 591,
H. Zima
, editor, Springer-Verlag, Berlin, pp.
438–451
.
26.
Nicol, D.
and
Reynolds, J. P. F.1990.
Optimal dynamic remapping of data parallel computations
. IEEE Transactions on Computers39(2):
206–219
.
27.
Nicol, D.
and
Saltz, J.1988.
Dynamic remapping of parallel computations with varying resource demands
. IEEE Transactions on Computers37(9):
1073–1087
.
28.
Park, N.
,
Prasanna, V.
, and
Raghavendra, C.1999.
A framework for integrating data alignment, distribution, and
redistribution in distributed memory multiprocessors
. IEEE Transactions on Parallel and Distributed Systems10(12):
1217–1240
.
29.
Prylli, L.
and
Tourancheau, B.1997.
Fast runtime block-cyclic data redistribution on multiprocessors
. Journal of Parallel Distributed Computing45:
63–72
.
30.
Renard, H.
,
Robert, Y.
, and
Vivien, F.2004a. Data redistribution algorithms for homogeneous and
heterogeneous processor rings. Research Report 5207, INRIA, May.
31.
Renard, H.
,
Robert, Y.
, and
Vivien, F.
2004b.
Data redistribution algorithms for homogeneous and heterogeneous processor rings
. Proceedings of High Performance Computing (HiPC 2004),
Bangalore, India, December
19–22, Lecture Notes in Computer ScienceVol. 3296,
Springer-Verlag, Berlin, pp.
123–132
.
32.
Sarrut, D.
and
Miguet, S.
1999.
ARAMIS: a remote access medical imaging system
. Proceedings of the International Symposium on Computing in
Object-Oriented Parallel Environments (ISCOPE 99), San
Francisco, CA, December 8–10, Lecture
Notes in Computer ScienceVol. 1732, Springer-Verlag, Berlin.
33.
Schloegel, K.
,
Karypis, G.
, and
Kumar, V.1997.
Multilevel diffusion schemes for repartitioning of adaptive meshes
. Journal of Parallel and Distributed Computing47:
109–124
.
34.
Schloegel, K.
,
Karypis, G.
, and
Kumar, V.
2000.
A unified algorithm for load-balancing adaptive scientific simulations
.Proceedings of Supercomputing 2000, Dallas,
TX, November 4–10, IEEE Computer Society
Press, Los Alamitos, CA.
35.
Shirazi, B. A.
,
Hurson, A. R.
, and
Kavi, K. M.1995. Scheduling and Load Balancing in Parallel and Distributed
Systems,
IEEE Computer Society Press, Los Alamitos, CA
.
36.
Thakur, R.
,
Choudhary, A.
, and
Ramanujam, J.1996.
Efficient algorithms for array redistribution
. IEEE Transactions on Parallel and Distributed Systems7(6):
587–594
.
37.
Watts, J.
and
Taylor, S.1998.
A practical approach to dynamic load balancing
. IEEE Transactions on Parallel and Distributed Systems9(93):
235–248
.
38.
Wu, M-Y.1997.
On runtime parallel scheduling for processor load balancing
. IEEE Transactions on Parallel and Distributed Systems8(2):
173–186
.
