Efficient trigger-broadcasting in heterogeneous clusters

M. Adler, Y. Gong, A.L. Rosenberg, Optimal sharing of bags of tasks in heterogeneous clusters, 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’03), 2003, pp. 1–10. Alexandrov, 1997, LogGP, J. Parallel Distrib. Comput., 44, 71, 10.1006/jpdc.1997.1346 Anderson, 1995, The Cluster Team, A case for NOW (networks of workstations), IEEE Micro, 15, 54, 10.1109/40.342018 Ausiello, 1999 M. Banikazemi, V. Moorthy, D.K. Panda, Efficient collective communication on heterogeneous networks of workstations, International Conference on Parallel Processing, 1998, pp. 460–467. Bar-Noy, 2000, Message multicasting in heterogeneous networks, SIAM J. Comput., 30, 347, 10.1137/S0097539798347906 Bar-Noy, 1994, Designing broadcasting algorithms in the postal model for message-passing systems, Math. Systems Theory, 27, 431, 10.1007/BF01184933 D. Barth, P. Fraigniaud, Approximation algorithms for structured communication problems, Ninth ACM Symposium on Parallel Algorithms and Architectures, 1997, pp. 180–188. (See also: Tech. Rpt. 1239, LRI, Univ. Paris-Sud. (http://www.lri.fr/~pierre)). Bhat, 1999, Adaptive communication algorithms for distributed heterogeneous systems, J. Parallel Distrib. Comput., 59, 252, 10.1006/jpdc.1999.1571 P.B. Bhat, V.K. Prasanna, C.S. Raghavendra, Efficient collective communication in distributed heterogeneous systems, 19th IEEE International Conference on Distributed Computing and Systems, 1999, pp. 15–24. F. Cappello, P. Fraigniaud, B. Mans, A.L. Rosenberg, An algorithmic model for heterogeneous clusters: rationale and experience. Intl. J. Foundations of Computer Science, to appear. see also: HiHCoHP—toward a realistic communication model for hierarchical hyperclusters of heterogeneous processors, International Parallel and Distributed Proceedings Symposium (IPDPS’01), 2001. J. Cohen, P. Fraigniaud, J.-C. Konig, A. Raspaud, Broadcasting and multicasting in cut-through routed networks, 11th IEEE International Parallel Processing Symposium, 1997, pp. 734–738. Culler, 1996, LogP, Comm. ACM, 39, 78, 10.1145/240455.240477 Du, 1997, Coordinating parallel processes on networks of workstations, J. Parallel Distrib. Comput., 46, 125, 10.1006/jpdc.1997.1378 M. Elkin, G. Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, 34th ACM Symposium on Theory of Computing, 2002. M. Elkin, G. Kortsarz, Sublogarithmic approximation for telephone multicast: path out of jungle, 14th ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 76–85. M. Elkin, G. Kortsarz, Approximation algorithm for directed telephone multicast problem, 30th International Colloquium on Automata, Languages and Programming, 2003, pp. 212–223. P. Fraigniaud, Approximation algorithms for minimum-time broadcast under the vertex-disjoint paths mode, in: 19th European Symposium on Algorithms (ESA ’01), Lecture Notes in Computer Science, vol. 2161, Springer, Berlin, 2001, pp. 440–451. Fraigniaud, 1994, Methods and problems of communication in usual networks, Discrete Appl. Math., 53, 79, 10.1016/0166-218X(94)90180-5 Fraigniaud, 1997, Approximation algorithms for broadcasting and gossiping, J. Parallel Distrib. Comput., 43, 47, 10.1006/jpdc.1997.1318 Garey, 1979 Hall, 1998, Scheduling in broadcast networks, Networks, 32, 233, 10.1002/(SICI)1097-0037(199812)32:4<233::AID-NET1>3.0.CO;2-Z Hedetniemi, 1986, A survey of gossiping and broadcasting in communication networks, Networks, 18, 319, 10.1002/net.3230180406 Hromkovič, 1997, Dissemination of information in interconnection networks (broadcasting and gossiping), 125 Johnsson, 1989, Optimum broadcasting and personalized communication in hypercubes, IEEE Trans. Comput., 38, 1249, 10.1109/12.29465 R.M. Karp, A. Sahay, E. Santos, K.E. Schauser, Optimal broadcast and summation in the LogP model, Fifth ACM Symposium on Parallel Algorithms and Architectures, 1993, pp. 142–153. R. Kesavan, K. Bondalapati, D.K. Panda, Multicast on irregular switch-based networks with wormhole routing, Third International Symposium on High-Performance Computer Architecture, 1997, pp. 48–57. J.-S. Kim, S. Ha, C.S. Jhon, Efficient barrier synchronization mechanism for the BSP model on message-passing architectures, 12th IEEE International Parallel Processing Symposium, 1998, pp. 255–259. Kortsarz, 1995, Approximation algorithms for minimum time broadcast, SIAM J. Discrete Math., 8, 401, 10.1137/S0895480193245923 R. Libeskind-Hadas, J. Hartline, Efficient multicast in heterogeneous networks of workstations, International Conference on Parallel Proceedings, 2000, pp. 403–410. Libeskind-Hadas, 2001, On multicast algorithms for heterogeneous networks of workstations, J. Parallel Distrib. Comput., 61, 1665, 10.1006/jpdc.2001.1759 R. Libeskind-Hadas, D. Mazzoni, R. Rajagopalan, Optimal contention-free unicast-based multicasting in switch-based networks of workstations, 12th IEEE International Parallel Processing Symposium, 1998, pp. 358–364. P. Liu, T.-H. Sheng, Broadcast scheduling optimization for heterogeneous clusters systems, 12th ACM Symposium on Parallel Algorithms and Architectures, 2000, pp. 129–136. Pfister, 1995 A.L. Rosenberg, On sharing bags of tasks in heterogeneous networks of workstations: greedier is not better, Third IEEE International Conference on Cluster Computing (Cluster’01), Newport Beach, CA, 2001, pp. 124–131. A.S. Tosun, A. Agarwal, Efficient broadcast algorithms for heterogeneous networks of workstations, 13th International Conference on Parallel and Distributed Computing Systems, 2000.