| Peer-Reviewed

Modeling of Communication Complexity in Parallel Computing

Received: 14 July 2014     Accepted: 18 July 2014     Published: 31 July 2014
Views:       Downloads:
Abstract

Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. Parallel using of more computing nodes (processors, cores), which have to cooperate each other in solving complex problems in a parallel way, opened imperative problem of modeling communication complexity so in symmetrical multiprocessors (SMP) based on motherboard as in other asynchronous parallel computers (computer networks, cluster etc.). In actually dominant parallel computers based on NOW and Grid (network of NOW networks) [31] there is necessary to model communication latency because it could be dominant at using massive (number of processors more than 100) parallel computers [17]. In this sense the paper is devoted to modeling of communication complexity in parallel computing (parallel computers and algorithms). At first the paper describes very shortly various used communication topologies and networks and then it summarized basic concepts for modeling of communication complexity and latency too. To illustrate the analyzed modeling concepts the paper considers in its experimental part the results for real analyzed examples of abstract square matrix and its possible decomposition models. These illustration examples we have chosen first due to wide matrix application in scientific and engineering fields and second from its typical exemplary representation for any other PA.

Published in American Journal of Networks and Communications (Volume 3, Issue 5-1)

This article belongs to the Special Issue Parallel Computer and Parallel Algorithms

DOI 10.11648/j.ajnc.s.2014030501.13
Page(s) 29-42
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2014. Published by Science Publishing Group

Keywords

Parallel Computer, NOW, Grid, Shared Memory, Distributed Memory, Parallel Algorithm, MPI, OpenMP, Model, Decomposition, Communication, Complexity, Modeling, Optimization, Overhead

References
[1] Abderazek A. B., Multicore systems on chip - Practical Software/Hardware design, Imperial college press, UK, pp. 200, 2010
[2] Arie M.C.A. Koster Arie M.C.A., Munoz Xavier, Graphs and Algorithms in Communication Networks, Springer Verlag, Germany, pp. 426, 2010
[3] Arora S., Barak B., Computational complexity - A modern Approach, Cambridge University Press, UK, pp. 573, 2009
[4] Barria A. J., Communication network and computer systems, Imperial College Press, UK, pp. 276, 2006
[5] Casanova H., Legrand A., Robert Y., Parallel algorithms, CRC Press, USA, 2008
[6] Dubois M., Annavaram M., Stenstrom P., Parallel computer organization and design, UK, pp. 560, 2012
[7] Hager G., Wellein G., Introduction to High Performance Computing for Scientists and Engineers, CRC Press, USA, pp. 356, 2010
[8] Hanuliak P., Analytical method of performance prediction in parallel algorithms, The Open Cybernetics and Systemics Journal, Vol. 6, Bentham, UK, pp. 38-47, 2012
[9] Hanuliak M., Unified analytical models of parallel and distributed computing, American J. of Networks and Communication, Science PG, Vol. 3, No. 1, USA, pp. 1-12, 2014
[10] Hanuliak P., Hanuliak I., Performance evaluation of iterative parallel algorithms, Kybernetes, Vol. 39, No.1/ 2010, UK, pp. 107- 126
[11] Hanuliak M., Modeling of parallel computers based on network of computing nodes, American J. of Networks and Communication, Science PG, Vol. 3, USA, 2014
[12] Hanuliak P., Complex modeling of matrix parallel algorithms, American J. of Networks and Communication, Science PG, Vol. 3, USA, 2014
[13] Hanuliak M., Hanuliak I., To the correction of analytical models for computer based communication systems, Kybernetes, Vol. 35, No. 9, UK, pp. 1492-1504, 2006
[14] Harchol-Balter Mor, Performance modeling and design of computer systems, Cambridge University Press, UK, pp. 576, 2013
[15] Hwang K. and coll., Distributed and Parallel Computing, Morgan Kaufmann, USA, pp. 472, 2011
[16] Kshemkalyani A. D., Singhal M., Distributed Computing, University of Illinois, Cambridge University Press, UK, pp. 756, 2011
[17] Kirk D. B., Hwu W. W., Programming massively parallel processors, Morgan Kaufmann, USA, pp. 280, 2010
[18] Kostin A., Ilushechkina L., Modeling and simulation of distributed systems, Imperial College Press, USA, pp. 440, 2010
[19] Kumar A., Manjunath D., Kuri J., Communication Networking , Morgan Kaufmann, USA, pp. 750, 2004
[20] Kushilevitz E., Nissan N., Communication Complexity, Cambridge University Press, UK, pp. 208, 2006,
[21] Le Boudec Jean-Yves, Performance evaluation of computer and communication systems, CRC Press, USA, pp. 300, 2011
[22] McCabe J., D., Network analysis, architecture, and design (3rd edition), Elsevier/ Morgan Kaufmann, USA, pp. 496, 2010
[23] Meerschaert M., Mathematical modeling (4-th edition), Elsevier, pp. 384, 2013
[24] Misra Ch. S., Woungang I., Selected topics in communication network and distributed systems, Imperial college press, UK, pp. 808, 2010
[25] Mieghem P. V., Graph spectra for Complex Networks, Cambridge University Press, UK, pp. 362, 2010
[26] Park K., Willinger W., Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., USA, pp. 558, 2000
[27] Peterson L. L., Davie B. C., Computer networks – a system approach, Morgan Kaufmann, USA, pp. 920, 2011
[28] Resch M. M., Supercomputers in Grids, Int. J. of Grid and HPC, No.1, Germany, pp. 1 - 9, 2009
[29] Riano l., McGinity T.M., Quantifying the role of complexity in a system´s performance, Evolving Systems, Springer Verlag, Germany, pp. 189 – 198, 2011
[30] Ross S. M., Introduction to Probability Models, 10th edition, Academic Press, Elsevier Science, Netherland, pp. 800, 2010
[31] Wang L., Jie Wei., Chen J., Grid Computing: Infrastructure, Service, and Application, CRC Press, USA, 2009
[32] Wolf Marilyn, High-Performance Embedded Computing (Second Edition), Morgan Kaufmann, USA, pp. 600, 2014
[33] Zhuge Hai., The Knowledge Grid, Imperial College Press, USA , pp. 360, December 2011www pages
[34] www.top500.org.
Cite This Article
  • APA Style

    Juraj Hanuliak. (2014). Modeling of Communication Complexity in Parallel Computing. American Journal of Networks and Communications, 3(5-1), 29-42. https://doi.org/10.11648/j.ajnc.s.2014030501.13

    Copy | Download

    ACS Style

    Juraj Hanuliak. Modeling of Communication Complexity in Parallel Computing. Am. J. Netw. Commun. 2014, 3(5-1), 29-42. doi: 10.11648/j.ajnc.s.2014030501.13

    Copy | Download

    AMA Style

    Juraj Hanuliak. Modeling of Communication Complexity in Parallel Computing. Am J Netw Commun. 2014;3(5-1):29-42. doi: 10.11648/j.ajnc.s.2014030501.13

    Copy | Download

  • @article{10.11648/j.ajnc.s.2014030501.13,
      author = {Juraj Hanuliak},
      title = {Modeling of Communication Complexity in Parallel Computing},
      journal = {American Journal of Networks and Communications},
      volume = {3},
      number = {5-1},
      pages = {29-42},
      doi = {10.11648/j.ajnc.s.2014030501.13},
      url = {https://doi.org/10.11648/j.ajnc.s.2014030501.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajnc.s.2014030501.13},
      abstract = {Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. Parallel using of more computing nodes (processors, cores), which have to cooperate each other in solving complex problems in a parallel way, opened imperative problem of modeling communication complexity so in symmetrical multiprocessors (SMP) based on motherboard as in other asynchronous parallel computers (computer networks, cluster etc.). In actually dominant parallel computers based on NOW and Grid (network of NOW networks) [31] there is necessary to model communication latency because it could be dominant at using massive (number of processors more than 100) parallel computers [17]. In this sense the paper is devoted to modeling of communication complexity in parallel computing (parallel computers and algorithms). At first the paper describes very shortly various used communication topologies and networks and then it summarized basic concepts for modeling of communication complexity and latency too. To illustrate the analyzed modeling concepts the paper considers in its experimental part the results for real analyzed examples of abstract square matrix and its possible decomposition models. These illustration examples we have chosen first due to wide matrix application in scientific and engineering fields and second from its typical exemplary representation for any other PA.},
     year = {2014}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Modeling of Communication Complexity in Parallel Computing
    AU  - Juraj Hanuliak
    Y1  - 2014/07/31
    PY  - 2014
    N1  - https://doi.org/10.11648/j.ajnc.s.2014030501.13
    DO  - 10.11648/j.ajnc.s.2014030501.13
    T2  - American Journal of Networks and Communications
    JF  - American Journal of Networks and Communications
    JO  - American Journal of Networks and Communications
    SP  - 29
    EP  - 42
    PB  - Science Publishing Group
    SN  - 2326-8964
    UR  - https://doi.org/10.11648/j.ajnc.s.2014030501.13
    AB  - Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. Parallel using of more computing nodes (processors, cores), which have to cooperate each other in solving complex problems in a parallel way, opened imperative problem of modeling communication complexity so in symmetrical multiprocessors (SMP) based on motherboard as in other asynchronous parallel computers (computer networks, cluster etc.). In actually dominant parallel computers based on NOW and Grid (network of NOW networks) [31] there is necessary to model communication latency because it could be dominant at using massive (number of processors more than 100) parallel computers [17]. In this sense the paper is devoted to modeling of communication complexity in parallel computing (parallel computers and algorithms). At first the paper describes very shortly various used communication topologies and networks and then it summarized basic concepts for modeling of communication complexity and latency too. To illustrate the analyzed modeling concepts the paper considers in its experimental part the results for real analyzed examples of abstract square matrix and its possible decomposition models. These illustration examples we have chosen first due to wide matrix application in scientific and engineering fields and second from its typical exemplary representation for any other PA.
    VL  - 3
    IS  - 5-1
    ER  - 

    Copy | Download

Author Information
  • Dubnica Technical Institute, Sladkovicova 533/20, Dubnica nad Vahom, 018 41, Slovakia

  • Sections