Open Access Open Access  Restricted Access Subscription or Fee Access

Modelling of Communication in Unified Parallel and Distributed Computing Environment

(*) Corresponding author

Authors' affiliations



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.


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:



Hanuliak, P., Hanuliak, M., Modelling of Communication Complexity in Computers, (2016) International Journal on Communications Antenna and Propagation (IRECAP), 6 (2), pp. 68-81.

Hager G., Wellein G., Introduction to High Performance Computing for Scientists and Engineers (CRC Press, 2010, Pages 356).

Peterson L. L., Davie B. C., Computer networks – a system approach (Morgan Kaufmann, 2011, Pages 920).

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

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.

Patterson D. A., Hennessy J. L., Computer Organization and Design (4th edition) (Morgan Kaufmann, 2011, Pages 914).

Hanuliak J., Hanuliak I., To performance evaluation of distributed parallel algorithms, Kybernetes, Volume 34, (No. 9/10), 2005, Pages 1633-1650.

Hudik, M., Hodon, M., Performance optimisation of parallel algorithms, JCN Korean Institute of Communication Sciences, Volume 16, Issue 4., 2014, Pages 436 – 446.

McCabe J., D., Network analysis, architecture, and design (Morgan Kaufmann, 2010, Pages 496).

Misra S., Misra Ch. S., Woungang I., Selected topics in communication network and distributed systems (Imperial college press, 2010, Pages 808).

Kshemkalyani A. D., Singhal M., Distributed Computing (Cambridge University Press, 2011, Pages 756).

Le Boudec Jean-Yves, Performance evaluation of computer and communication systems, (CRC Press, 2011, Pages 300).

Bronson R., Costa G. B., Saccoman J. T., Linear Algebra - Algorithms, Applications, and Techniques 3rd ed. (Elsevier Science & Technology, 2014, Pages 536).

Kushilevitz E., Nissan N., Communication Complexity (Cambridge University Press, 2006, Pages 208).

Goldreich O., P, NP and NPC (Cambridge University Press, 2010, Pages 214).

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.

Wang L., Jie Wei., Chen J., Grid Computing: Infrastructure, Service, and Application (CRC Press, 2009).

Arora S., Barak B., Computational complexity - A modern Approach, (Cambridge University Press, 2009, Pages 578).

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

Kostin A., Ilushechkina L., Modelling and simulation of distributed systems (Imperial College Press, 2010, Pages 440).


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2024 Praise Worthy Prize