Modeling of Communication Complexity in Parallel Computing

Juraj Hanuliak

doi:doi:10.11648/j.ajnc.s.2014030501.13

| Peer-Reviewed

Modeling of Communication Complexity in Parallel Computing

Juraj Hanuliak

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

Received: 14 July 2014 Accepted: 18 July 2014 Published: 31 July 2014

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Juraj Hanuliak

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

Download PDF

Sections

Plain Text BibTeX RIS

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