Implementacja algorytmu efektywnego rozgłoszenia i redukcji wiadomości w klastrze

• Autorzy: Pokuta Waldemar

Warianty tytułu

EN

Implementation of effective algorithm message broadcast and reduction in cluster

• Języki publikacji: PL

Abstrakty

PL

Artykuł opisuje algorytm efektywnego rozgłoszenia i redukcji wiadomości w klastrze. W celu uzyskania dużej efektywności procesy układane są w strukturze hipersześcianu poprzez odpowiednie ich ponumerowanie. Algorytm nie wymaga znajomości struktury fizycznej klastra, jest on uniwersalny dla pewnych standardów np. MPI. Omawiany algorytm posiada słabe strony, które zostały opisane w artykule. Wyprowadzona została złożoność optymistyczna i pesymistyczna rozgłoszenia dla pewnej klasy klastrów

EN

The article describes an algorithm of efficient message reduction and broadcast in a computer cluster. In order to achieve high efficiency processes are placed in the structure of the hypercube through their appropriate numbering. The algorithm does not require knowledge of the physical structure of the cluster, it is universal for certain standards, for example MPI. The present algorithm has weaknesses that have been described in the article. It has been derived complexity of optimistic and pessimistic broadcast for a certain class of clusters.

• Wydawca: Oficyna Wydawnicza Politechniki Opolskiej
• Czasopismo: Zeszyty Naukowe. Informatyka / Politechnika Opolska
• Rocznik: 2015
• Tom: vol. 357, z. 3
• Strony: 127--138The article describes an algorithm of efficient message reduction and broadcast in a computer cluster. In order to achieve high efficiency processes are placed in the structure of the hypercube through their appropriate numbering. The algorithm does not require knowledge of the physical structure of the cluster, it is universal for certain standards, for example MPI. The present algorithm has weaknesses that have been described in the article. It has been derived complexity of optimistic and pessimistic broadcast for a certain class of clusters.
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Pokuta Waldemar

• Politechnika Opolska

Bibliografia

• [1] BERMOND J. C., BONNECAZE A., KODATE T., P´ERENNES S., SOLE P.: Broadcasting in hypercubes under the circuit-switched model. in Proc. IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2000
• [2] JIN H. i in.: High performance computing using MPI and OpenMP on multi-core parallel systems, Parallel Computing 37, 562–575 (2011)
• [3] CANG S., WU J.: Time-Step Optimal Broadcasting in 3-D Meshes with Minimum Total Communication Distance, Journal of Parallel and Distributed Computing 60, 966-997 (2000)
• [4] CHAWATHE Y.: Scattercast: an adaptable broadcast distribution framework, Multimedia Systems 9: 104–118 (2003)
• [5] COHENJ., FRAIGNIAUD P., MITJANA M.: Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees, Theory Comput. Systems 35, 641–665 (2002)
• [6] CÉSAR C., CARVALHO S.: An analytical framework for distributed coordinated scheduling in IEEE 802.16 wireless mesh networks, Ad Hoc Networks 13A, 181–190 (2014)
• [7] ZOUNMEVO J., AFSAHI A.: A fast and resource-conscious MPI message queue mechanism for large-scale jobs, Future Generation Computer Systems, 30, 265–290 (2014)
• [8] GEIST A., BEGUELIN B., DONGARRA J., JIANG W., MANCHEK B., SUNDERAM V.: PVM: Parallel Virtual Machine – A User’s Guide and Tutorial for Network Parallel Computing. MIT Press, Cambridge, MA, 1994
• [9] NAZI A., AZAD H. S.: A Path-Based Broadcast Algorithm for Wormhole Hypercubes, I Pervasive Systems, Algorithms, and Networks (ISPAN), 10th International Symposium (2009), 586–591
• [10] KUMAR V., GRAMA A., GUPTA A., KARYPIS G.: Introduction to Parallel Computing. Design and Analysis of Algorithms, Benjamin/Cummings, New York, 1994
• [11] XIANG D., CHEN A., SUN J.: Fault-tolerant multicasting in hypercubes using local safety information, J. Parallel and Distrib. Computing, 66, 248–256 (2006)
• [12] LEIGHTON F. T.: Introduction to Parallel Algorithms and Architectures: Arrays-TreesHypercubes, Morgan-Kaufmann, Los Altos, CA, 1992
• [13] LOUCIF S., OULD-KHAOUA M.: Support for broadcast communication in multicomputer networks, Microprocessors and Microsystems 26 (2002) 151–159
• [14] WANG S., FENG K.: Strong matching preclusion for torus networks 520, 97–110 (2014)
• [15] SALINGER P., TVRDIK P.: Broadcasting in All-Output-Port Meshes of Trees with Distance-Insensitive Switching, Journal of Parallel and Distributed Computing 62,1272–1294 (2002)
• [16] SANDERS P., SIBEYN J.F.: A bandwidth latency tradeoff for broadcast and reduction, Information Processing Letters 86 (2003) 33–38
• [17] SANTOS E. E.: Optimal and Near-Optimal Algorithms for k-Item Broadcast, Journal of Parallel and Distributed Computing 57, 121_139 (1999)
• [18] SANTOS E. E.: Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines Journal of Parallel and Distributed Computing 62, 517_543 (2002)
• [19] SHAHRABI A., MACKENZIE L.M., OULD-KHAOUA M.: An analytical model of wormhole-routed hypercubes under broadcast traffic, Performance Evaluation 53 (2003) 23–42
• [20] SHAHRABI A., OULD-KHAOUA M., MACKENZIE L. M.: Analytical modelling of broadcast in adaptive wormhole-routed hypercubes, Microprocessors and Microsystems 25 (2001) 389–398
• [21] SNIR M., OTTO S. W, HUSS-LEDERMAN S., WALKER D. W., DONGARRA J.: MPI—The Complete Reference, MIT Press, Cambridge, MA, 1996 138
• [22] TANENBAUM A.S., KAASHOEK M.F., BAL H.E.: Parallel programming using shared objects and broadcasting. IEEE Computer 25, 1992
• [23] XU H., MCKINLEY P.K., NI L,M.: Efficient implementation of barrier synchronization in wormhole-routed hypercube multicomputers, J. Parallel and Distrib. Comput. 16 (1992), 172_184
• [24] FIGUEIRA S.: Using a