Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
The collective computing model
Keywords:
Parallelism, Bulk Synchronous Parallel Model, Supersteps, Performance Prediction, Parallel ComputerAbstract
The parallel computing model used in this paper, the Collective Computing Model (CCM), is a variant of the well-known Bulk Synchronous Parallel (BSP) model. The synchronicity imposed by the BSP model restricts the set of available algorithms and prevents the overlapping of computation and communication. Other models, like the LogP model, allow asynchronous computing and overlapping but depend on the use of specific libraries. The CCM describes a system exploited through a standard software platform providing facilities for group creation, collective operations and remote memory operations. Based in the BSP model, two kinds of supersteps are considered: Division supersteps and Normal supersteps. The structure of divisions produced by the Division Functions and the partnership relation among processors give place to communication patterns among processors that are topologically similar to a hypercube. We have named the resulting structures Dynamic Polytopes To illustrate these concepts, the Fast Fourier Transform Algorithm is used. Computational results prove the accuracy of the model in four different parallel computers: a Parsytec Power PC, a Cray T3E, a Silicon Graphics Origin 2000 and a Digital Alpha Server.
Downloads
Download data is not yet available.
References
[1] Abandah, G.A., Davidson E.S. Modeling the Communication Performance of the IBM SP2. Proc. 10th IPPS. 1996.
[2] Arruabarrena, J.M., Arruabarrena A., Beivide R., Gregorio J.A. Assesing the Performance of the New IBM-SP2 Communication Subsystem. IEEE Parallel and Distributed Technology. pp 12-22. 1996.
[3] Culler D., Karp Richard, Patterson D., Sahay A., Schauser K.E., Santos E., Sub Eicken T.. LogP: Towards a Realistic Model of Parallel Computation. Proceedings of the 4th ACM SIGPLAN, Sym. Principle Parallel Programming. 1993.
[4] Eicken T., Culler D.E., Goldstein S.C., Schauser K.E. Active Messages: A Mechanism for Integrated ommunication and Computation. Report No. UCB/CSD 92/#675. Computer Science Division. University of California, Berkeley, CA 94720. Mar. 1992.
[5] Geist A., Beguelin A., Dongarra J., Jiang W., Mancheck R., Sunderam V.. PVM: Parallel Virtual Machine - A Users Guide and Tutorial for Network Parallel Computing. MIT Press. 1994.
[6] Hambrush S.E., Khokhar A. C3: A Parallel Model for Coarse-grained Machines. Journal of Parallel and Distributed Computing. Vol 32, nr. 2, pp. 139-154, 1996.
[7] Hill J., McColl B., Stefanescu D., Goudreau M., Lang K., Rao B., Suel T., Tsantilas, Bisseling R.. BSPLib: The BSP Programming Library. Technical Report PRG-TR-29-97, Oxford University Computing Laboratory. May 1997.
[8] Kort I, Trystram D. Assesing LogP Model Parameters for the IBM-SP.
EuroPar’98. LNCS Springer Verlag.
[9] Li, X., Lu, P., Schaefer, J., Shillington, J., Wong, P.S., Shi, H. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, pp. 1079-1103. 1993.
[10] Pakin S., Lauria M., Buchanan M., Hane K., Giannini L.,Prusakova J., Chien A. Fast Messages on Myrinet. http://www-csag.cs.uiuc.edu/projects/comm/fm20-user doc /userdoc.html. 1995.
[11] Rodríguez C., Sande F., Leon C. and García L. Extending Processor Assignment Statements. 2nd IASTED European Conference on Parallel and Distributed Systems. Acta Press. 1998.
[12] Rodríguez C., Roda J.L., Morales D.G., Almeida F. h-relation Models for Current Standard Parallel Platforms. EuroPar ’98. Springer Verlag. 1998.
[13] Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J. MPI: The complete Reference. Cambridge, MA: MIT Press, 1996.
[14] Valiant L.G.. A Bridging Model for Parallel Computation. Communications of the ACM, 33(8): 103-111, 1990.
[2] Arruabarrena, J.M., Arruabarrena A., Beivide R., Gregorio J.A. Assesing the Performance of the New IBM-SP2 Communication Subsystem. IEEE Parallel and Distributed Technology. pp 12-22. 1996.
[3] Culler D., Karp Richard, Patterson D., Sahay A., Schauser K.E., Santos E., Sub Eicken T.. LogP: Towards a Realistic Model of Parallel Computation. Proceedings of the 4th ACM SIGPLAN, Sym. Principle Parallel Programming. 1993.
[4] Eicken T., Culler D.E., Goldstein S.C., Schauser K.E. Active Messages: A Mechanism for Integrated ommunication and Computation. Report No. UCB/CSD 92/#675. Computer Science Division. University of California, Berkeley, CA 94720. Mar. 1992.
[5] Geist A., Beguelin A., Dongarra J., Jiang W., Mancheck R., Sunderam V.. PVM: Parallel Virtual Machine - A Users Guide and Tutorial for Network Parallel Computing. MIT Press. 1994.
[6] Hambrush S.E., Khokhar A. C3: A Parallel Model for Coarse-grained Machines. Journal of Parallel and Distributed Computing. Vol 32, nr. 2, pp. 139-154, 1996.
[7] Hill J., McColl B., Stefanescu D., Goudreau M., Lang K., Rao B., Suel T., Tsantilas, Bisseling R.. BSPLib: The BSP Programming Library. Technical Report PRG-TR-29-97, Oxford University Computing Laboratory. May 1997.
[8] Kort I, Trystram D. Assesing LogP Model Parameters for the IBM-SP.
EuroPar’98. LNCS Springer Verlag.
[9] Li, X., Lu, P., Schaefer, J., Shillington, J., Wong, P.S., Shi, H. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, pp. 1079-1103. 1993.
[10] Pakin S., Lauria M., Buchanan M., Hane K., Giannini L.,Prusakova J., Chien A. Fast Messages on Myrinet. http://www-csag.cs.uiuc.edu/projects/comm/fm20-user doc /userdoc.html. 1995.
[11] Rodríguez C., Sande F., Leon C. and García L. Extending Processor Assignment Statements. 2nd IASTED European Conference on Parallel and Distributed Systems. Acta Press. 1998.
[12] Rodríguez C., Roda J.L., Morales D.G., Almeida F. h-relation Models for Current Standard Parallel Platforms. EuroPar ’98. Springer Verlag. 1998.
[13] Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J. MPI: The complete Reference. Cambridge, MA: MIT Press, 1996.
[14] Valiant L.G.. A Bridging Model for Parallel Computation. Communications of the ACM, 33(8): 103-111, 1990.
Downloads
Published
2000-10-02
How to Cite
Gonzalez, J. A., León, C., Piccoli, M. F., Printista, A. M., Roda García, J. L., Rodríguez, C., & Sande, F. de. (2000). The collective computing model. Journal of Computer Science and Technology, 1(03), 11 p. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/1003
Issue
Section
Original Articles
