Decomposition Models of Parallel Algorithms

Michal Hanuliak; Juraj Hanuliak

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

| Peer-Reviewed

Decomposition Models of Parallel Algorithms

Michal Hanuliak, Juraj Hanuliak

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

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

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplication. On the basis of the done analysis of the used parallel computers in the world these are divided to the two basic groups which are from the programmer-developer point of view very different. They are also introduced the typical principal structures for both these groups of parallel computers and also their models. The paper then in an illustrative way describes the development of concrete parallel algorithm for matrix multiplication on various parallel systems. For each individual practical implementation of matrix multiplication there is introduced the derivation of its calculation complexity. The described individual ways of developing parallel matrix multiplication and their implementations are compared, analyzed and discussed from sight of programmer-developer and user in order to show the very important role of decomposition strategies mainly at the class of asynchronous parallel computers.

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.16
Page(s)	70-84
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, Parallel algorithms, Performance, Decomposition model, Numerical integration, Matrix multiplication

References

[1]	Abderazek A. B., Multicore systems on chip - Practical Software/Hardware design, Imperial college press, pp. 200, 2010
[2]	Arie M.C.A. KosterArie 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, United Kingdom, pp. 573, 2009
[4]	Bahi J. H., Contasst-Vivier S., Couturier R., Parallel Iterative algorithms: From Seguential to Grid Computing, CRC Press, USA, 2007
[5]	Bronson R., Costa G. B., Saccoman J. T., Linear Algebra - Algorithms, Applications, and Techniques, 3rd Edition, Elsevier Science & Technology, Netherland, pp. 536, 2014
[6]	Dattatreya G. R., Performance analysis of queuing and computer network, University of Texas, Dallas, USA, pp. 472, 2008
[7]	Desel J., Esperza J., Free Choise Petri Nets, Cambridge University Press, United Kingdom, pp. 256, 2005
[8]	Dubois M., Annavaram M., Stenstrom P., Parallel Computer Organization and Design, Cambridge university press, United Kingdom,pp. 560, 2012
[9]	Dubhash D.P., Panconesi A., Concentration of measure for the analysis of randomized algorithms, Cambridge University Press, United Kingdom, 2009
[10]	Edmonds J., How to think about algorithms, Cambridge University Press, United Kingdom, pp. 472, 2010
[11]	Gelenbe E., Analysis and synthesis of computer systems, Imperial College Press, United Kingdom, pp. 324, 2010
[12]	GoldreichOded, P, NP, and NP - Completeness, Cambridge University Press, United Kingdom, pp. 214, 2010
[13]	Hager G., Wellein G., Introduction to High Performance Computing for Scientists and Engineers, CRC Press, USA, pp. 356, 2010
[14]	Hanuliak P., Complex modeling of matrix parallel algorithms, American J. of Networks and Communication, Science PG, Vol. 3, USA, 2014
[15]	Hanuliak P., Hanuliak J., Complex performance modeling of parallel algorithms, American J. of Networks and Communication, Science PG, Vol. 3, USA, 2014
[16]	Hanuliak P., Hanuliak I., Performance evaluation of iterative parallel algorithms, Kybernetes, Volume 39, No.1/ 2010, United Kingdom, pp. 107- 126, 2010
[17]	Hanuliak P., Analytical method of performance prediction in parallel algorithms, The Open Cybernetics and Systemics Journal, Vol. 6, Bentham,United Kingdom, pp. 38-47, 2012
[18]	Hanuliak P., Complex performance evaluation of parallel Laplace equation, AD ALTA – Vol. 2, issue 2, Magnanimitas, Hradec Kralove, Czech republic, pp. 104-107, 2012
[19]	Harchol-BalterMor, Performance modeling and design of computer systems, Cambridge University Press, United Kingdom, pp. 576, 2013
[20]	Hillston J., A Compositional Approach to Performance Modeling, University of Edinburg, Cambridge University Press,United Kingdom, pp.172, 2005
[21]	Hwang K. and coll., Distributed and Parallel Computing, Morgan Kaufmann, USA, pp. 472, 2011
[22]	Kshemkalyani A. D., Singhal M., Distributed Computing, University of Illinois, Cambridge University Press, United Kingdom, pp. 756, 2011
[23]	Kirk D. B., Hwu W. W., Programming massively parallel processors, Morgan Kaufmann, USA, pp. 280, 2010
[24]	Kostin A., Ilushechkina L., Modeling and simulation of distributed systems, Imperial College Press, United Kingdom, pp. 440, 2010
[25]	Kumar A., Manjunath D., Kuri J., Communication Networking, Morgan Kaufmann, USA, pp. 750, 2004
[26]	Kushilevitz E., Nissan N., Communication Complexity, Cambridge University Press, United Kingdom, pp. 208, 2006
[27]	Le Boudec Jean-Yves, Performance evaluation of computer and communication systems, CRC Press, USA, pp. 300, 2011
[28]	Levesque John, High Performance Computing: Programming and applications, CRC Press, USA, pp. 244, 2010
[29]	Lilja D. J., Measuring Computer Performance, Cambridge University Press, United Kingdom, pp. 280, 2005
[30]	McCabe J., D., Network analysis, architecture, and design (3rd edition), Elsevier/ Morgan Kaufmann, USA, pp. 496, 2010
[31]	Misra Ch. S.,Woungang I., Selected topics in communication network and distributed systems, Imperial college press, United Kingdom, pp. 808, 2010
[32]	Paterson D. A., Hennessy J. L., Computer Organisation and Design, Morgan Kaufmann, USA, pp. 912, 2009
[33]	Peterson L. L., Davie B. C., Computer networks – a system approach, Morgan Kaufmann, USA, pp. 920, 2011
[34]	Resch M. M., Supercomputers in Grids, Int. J. of Grid and HPC, No.1, pp. 1 - 9, 2009
[35]	Shapira Y., Solving PDEs in C++ - Numerical Methods in a Unified Object-Oriented Approach (2nd edition), Cambridge University Press, United Kingdom, pp. 800, 2012
[36]	Wang L., Jie Wei., Chen J., Grid Computing: Infrastructure, Service, and Application, CRC Press, USA, 2009www pages
[37]	www.top500.org.

Cite This Article

Plain Text BibTeX RIS

APA Style

Michal Hanuliak, Juraj Hanuliak. (2014). Decomposition Models of Parallel Algorithms. American Journal of Networks and Communications, 3(5-1), 70-84. https://doi.org/10.11648/j.ajnc.s.2014030501.16

Copy | Download

ACS Style

Michal Hanuliak; Juraj Hanuliak. Decomposition Models of Parallel Algorithms. Am. J. Netw. Commun. 2014, 3(5-1), 70-84. doi: 10.11648/j.ajnc.s.2014030501.16

Copy | Download

AMA Style

Michal Hanuliak, Juraj Hanuliak. Decomposition Models of Parallel Algorithms. Am J Netw Commun. 2014;3(5-1):70-84. doi: 10.11648/j.ajnc.s.2014030501.16

Copy | Download

@article{10.11648/j.ajnc.s.2014030501.16,
  author = {Michal Hanuliak and Juraj Hanuliak},
  title = {Decomposition Models of Parallel Algorithms},
  journal = {American Journal of Networks and Communications},
  volume = {3},
  number = {5-1},
  pages = {70-84},
  doi = {10.11648/j.ajnc.s.2014030501.16},
  url = {https://doi.org/10.11648/j.ajnc.s.2014030501.16},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajnc.s.2014030501.16},
  abstract = {The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplication. On the basis of the done analysis of the used parallel computers in the world these are divided to the two basic groups which are from the programmer-developer point of view very different. They are also introduced the typical principal structures for both these groups of parallel computers and also their models. The paper then in an illustrative way describes the development of concrete parallel algorithm for matrix multiplication on various parallel systems. For each individual practical implementation of matrix multiplication there is introduced the derivation of its calculation complexity. The described individual ways of developing parallel matrix multiplication and their implementations are compared, analyzed and discussed from sight of programmer-developer and user in order to show the very important role of decomposition strategies mainly at the class of asynchronous parallel computers.},
 year = {2014}
}

Copy | Download

TY  - JOUR
T1  - Decomposition Models of Parallel Algorithms
AU  - Michal Hanuliak
AU  - Juraj Hanuliak
Y1  - 2014/07/31
PY  - 2014
N1  - https://doi.org/10.11648/j.ajnc.s.2014030501.16
DO  - 10.11648/j.ajnc.s.2014030501.16
T2  - American Journal of Networks and Communications
JF  - American Journal of Networks and Communications
JO  - American Journal of Networks and Communications
SP  - 70
EP  - 84
PB  - Science Publishing Group
SN  - 2326-8964
UR  - https://doi.org/10.11648/j.ajnc.s.2014030501.16
AB  - The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplication. On the basis of the done analysis of the used parallel computers in the world these are divided to the two basic groups which are from the programmer-developer point of view very different. They are also introduced the typical principal structures for both these groups of parallel computers and also their models. The paper then in an illustrative way describes the development of concrete parallel algorithm for matrix multiplication on various parallel systems. For each individual practical implementation of matrix multiplication there is introduced the derivation of its calculation complexity. The described individual ways of developing parallel matrix multiplication and their implementations are compared, analyzed and discussed from sight of programmer-developer and user in order to show the very important role of decomposition strategies mainly at the class of asynchronous parallel computers.
VL  - 3
IS  - 5-1
ER  -

Copy | Download

Author Information

Michal Hanuliak

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

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

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Michal Hanuliak, Juraj Hanuliak. (2014). Decomposition Models of Parallel Algorithms. American Journal of Networks and Communications, 3(5-1), 70-84. https://doi.org/10.11648/j.ajnc.s.2014030501.16

Copy | Download

ACS Style

Michal Hanuliak; Juraj Hanuliak. Decomposition Models of Parallel Algorithms. Am. J. Netw. Commun. 2014, 3(5-1), 70-84. doi: 10.11648/j.ajnc.s.2014030501.16

Copy | Download

AMA Style

Michal Hanuliak, Juraj Hanuliak. Decomposition Models of Parallel Algorithms. Am J Netw Commun. 2014;3(5-1):70-84. doi: 10.11648/j.ajnc.s.2014030501.16

Copy | Download

@article{10.11648/j.ajnc.s.2014030501.16,
  author = {Michal Hanuliak and Juraj Hanuliak},
  title = {Decomposition Models of Parallel Algorithms},
  journal = {American Journal of Networks and Communications},
  volume = {3},
  number = {5-1},
  pages = {70-84},
  doi = {10.11648/j.ajnc.s.2014030501.16},
  url = {https://doi.org/10.11648/j.ajnc.s.2014030501.16},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajnc.s.2014030501.16},
  abstract = {The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplication. On the basis of the done analysis of the used parallel computers in the world these are divided to the two basic groups which are from the programmer-developer point of view very different. They are also introduced the typical principal structures for both these groups of parallel computers and also their models. The paper then in an illustrative way describes the development of concrete parallel algorithm for matrix multiplication on various parallel systems. For each individual practical implementation of matrix multiplication there is introduced the derivation of its calculation complexity. The described individual ways of developing parallel matrix multiplication and their implementations are compared, analyzed and discussed from sight of programmer-developer and user in order to show the very important role of decomposition strategies mainly at the class of asynchronous parallel computers.},
 year = {2014}
}

Copy | Download

TY  - JOUR
T1  - Decomposition Models of Parallel Algorithms
AU  - Michal Hanuliak
AU  - Juraj Hanuliak
Y1  - 2014/07/31
PY  - 2014
N1  - https://doi.org/10.11648/j.ajnc.s.2014030501.16
DO  - 10.11648/j.ajnc.s.2014030501.16
T2  - American Journal of Networks and Communications
JF  - American Journal of Networks and Communications
JO  - American Journal of Networks and Communications
SP  - 70
EP  - 84
PB  - Science Publishing Group
SN  - 2326-8964
UR  - https://doi.org/10.11648/j.ajnc.s.2014030501.16
AB  - The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplication. On the basis of the done analysis of the used parallel computers in the world these are divided to the two basic groups which are from the programmer-developer point of view very different. They are also introduced the typical principal structures for both these groups of parallel computers and also their models. The paper then in an illustrative way describes the development of concrete parallel algorithm for matrix multiplication on various parallel systems. For each individual practical implementation of matrix multiplication there is introduced the derivation of its calculation complexity. The described individual ways of developing parallel matrix multiplication and their implementations are compared, analyzed and discussed from sight of programmer-developer and user in order to show the very important role of decomposition strategies mainly at the class of asynchronous parallel computers.
VL  - 3
IS  - 5-1
ER  -

Copy | Download