The collective computing model

  1. Jesús Alberto Gonzalez
  2. Coromoto León Hernández
  3. María Fabiana Piccoli
  4. Alicia Marcela Printista
  5. José Luis Roda García
  6. Casiano Rodríguez León
  7. Francisco de Sande González
Journal:
Journal of Computer Science and Technology

ISSN: 1666-6038

Year of publication: 2000

Volume: 1

Issue: 3

Pages: 2

Type: Article

Export: RIS

Abstract

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.

Bibliographic References

  • 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.