Open Access Open Access  Restricted Access Subscription or Fee Access

Modelling of Communication in Unified Parallel and Distributed Computing Environment

Peter Hanuliak(1*), Michal Hanuliak(2)

(1) DTI University, Slovakia
(2) DTI University, Slovakia
(*) Corresponding author


DOI: https://doi.org/10.15866/irecap.v8i2.12951

Abstract


In modelling of sequential computers and algorithms, communication delay has often been ignored. Later, in modelling of parallel computers and parallel algorithms based on shared memory, it was supposed that the influence of communication is lower compared to computation complexity. It was supposed that, in better cases, communication delay is included in analysed computation complexity. However, a different situation can occur in high performance processors (CPU) or simplified CPUs called cores within the parallel computing node (multiprocessor/ multicore SMP). The similar case could occur in the multiple use of high performing computing nodes as the building computing nodes of modern parallel computers NOW (network of workstations) or Grid module (network of NOW modules). However, if complex problem are intended to be solved in a parallel way (parallel algorithm), they generate additional communication steps which correspond to inter process communication (IPC) among the decomposed parts (parallel processes) of the given solved problem. In general, it can be said that any parallel algorithm (PA) consists of created parallel processes having sequential character and IPC communication. Therefore, the increased role of IPC communication has been analysed in this paper through the analytical modelling of IPC complexity (number of communication steps) in a similar way as the one used to analyse computation complexity in sequential algorithms or parallel processes). Based on the defined communication parameters and the extensions of the complexity theory to PA, a unique modelling approach was developed to model the communication complexity of all existing parallel computers and PA. The secondary problem is to model critical parts of IPC influence for PA performance and that, at first, in minimisation of IPC steps of decomposed parallel processes and secondly at whole performance optimisation of the PA. The achieved results showed, from the user’s point of view, the important influence of modelling IPC complexity in PA on the illustrated real examples.
Copyright © 2018 Praise Worthy Prize - All rights reserved.

Keywords


Computing Node; SMP; NOW; Grid; Shared Memory; Distributed Memory; Parallel Algorithm (PA); Decomposition Model (DM); Modelling; IPC; Communication Complexity; Optimisation; Efficiency; Isoefficiency Function

Full Text:

PDF


References


Hanuliak, P., Hanuliak, M., Modelling of Communication Complexity in Computers, (2016) International Journal on Communications Antenna and Propagation (IRECAP), 6 (2), pp. 68-81.
http://dx.doi.org/10.15866/irecap.v6i2.8444

Hager G., Wellein G., Introduction to High Performance Computing for Scientists and Engineers (CRC Press, 2010, Pages 356).
http://dx.doi.org/10.1201/ebk1439811924

Peterson L. L., Davie B. C., Computer networks – a system approach (Morgan Kaufmann, 2011, Pages 920).
http://dx.doi.org/10.1109/mcom.1998.667947

Abderazek A.B., Multicore systems on-chip–Practical Software/Hardware design (Imperial college press, 2010, p. 200).

Coulouris G., Dollimore J., Kindberg T., Distributed Systems – Concepts and Design (5-th ed.), (Addison Wesley, 2011, Pages 800).

Dubois M., Annavaram M., Stenstrom P., Parallel Computer Organisation and Design (Cambridge University Press, 2012, Pages 560).
http://dx.doi.org/10.1017/cbo9781139051224

Hanuliak J., Modeling of communication complexity in parallel computing, American Journal of Networks and Communication, Science PG, Volume 3, (Special Issue 1), 2014, Pages 29-42.
http://dx.doi.org/10.11648/j.ajnc.s.2014030501.13

Patterson D. A., Hennessy J. L., Computer Organization and Design (4th edition) (Morgan Kaufmann, 2011, Pages 914).
http://dx.doi.org/10.1016/b978-1-4832-0775-9.50007-5

Hanuliak J., Hanuliak I., To performance evaluation of distributed parallel algorithms, Kybernetes, Volume 34, (No. 9/10), 2005, Pages 1633-1650.
http://dx.doi.org/10.1108/03684920510614858

Hudik, M., Hodon, M., Performance optimisation of parallel algorithms, JCN Korean Institute of Communication Sciences, Volume 16, Issue 4., 2014, Pages 436 – 446.
http://dx.doi.org/10.1109/jcn.2014.000074

McCabe J., D., Network analysis, architecture, and design (Morgan Kaufmann, 2010, Pages 496).
http://dx.doi.org/10.1016/b978-012370480-1/50006-2

Misra S., Misra Ch. S., Woungang I., Selected topics in communication network and distributed systems (Imperial college press, 2010, Pages 808).
http://dx.doi.org/10.1142/9789812839442

Kshemkalyani A. D., Singhal M., Distributed Computing (Cambridge University Press, 2011, Pages 756).
http://dx.doi.org/10.1017/cbo9780511805318.002

Le Boudec Jean-Yves, Performance evaluation of computer and communication systems, (CRC Press, 2011, Pages 300).
http://dx.doi.org/10.1201/b16328

Bronson R., Costa G. B., Saccoman J. T., Linear Algebra - Algorithms, Applications, and Techniques 3rd ed. (Elsevier Science & Technology, 2014, Pages 536).
http://dx.doi.org/10.1016/b978-0-12-391420-0.00005-6

Kushilevitz E., Nissan N., Communication Complexity (Cambridge University Press, 2006, Pages 208).
http://dx.doi.org/10.1017/cbo9780511574948.003

Goldreich O., P, NP and NPC (Cambridge University Press, 2010, Pages 214).
http://dx.doi.org/10.1017/cbo9780511761355

Hwang K. and coll., Distributed and Parallel Computing (Morgan Kaufmann, 2011, Pages 472).

Hanuliak, P., Hanuliak, M., Optimisation of Communication Complexity in Parallel Computing, (2016) International Review on Computers and Software (IRECOS), 11 (2), pp. 109-115.
http://dx.doi.org/10.15866/irecos.v11i2.8471

Wang L., Jie Wei., Chen J., Grid Computing: Infrastructure, Service, and Application (CRC Press, 2009).
http://dx.doi.org/10.1201/9781420067682

Arora S., Barak B., Computational complexity - A modern Approach, (Cambridge University Press, 2009, Pages 578).
http://dx.doi.org/10.1017/cbo9780511804090

Goldreich O., Computational complexity (Cambridge University Press, 2010, Pages 632).

Riano l., McGinity T.M., Quantifying the role of complexity in a system’s performance, (Evolving Systems, Springer Verlag, 2011, Pages 189 – 198).
http://dx.doi.org/10.1007/s12530-011-9031-4

Kostin A., Ilushechkina L., Modelling and simulation of distributed systems (Imperial College Press, 2010, Pages 440).
http://dx.doi.org/10.1142/7562


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2019 Praise Worthy Prize