Modelling of Communication Complexity in Computers

Peter Hanuliak; Michal Hanuliak

doi:10.15866/irecap.v6i2.8444

Modelling of Communication Complexity in Computers

Peter Hanuliak^(1*), Michal Hanuliak⁽²⁾

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/irecap.v6i2.8444

Abstract

We have been oft used to ignore the influence of communication in sequential computers or in better cases we have been supposed that this influence should be included in computation complexity representing performed I/O instructions. Multiple using of high performed CPU (central processor unit) within a single computer (SMP parallel computer) but also multiple using of high performed computers (workstations) as the building computing node of dominant parallel computers nowadays (network of workstations - NOW) or integrated network of NOW modules - Grid).The extended communication steps in parallel computers represent inter process communication (IPC) of decomposed parts of given parallel algorithm (PA) named as parallel processes. Then we can simply say that any PA consists of parallel processes with their sequential character and IPC among parallel processes. In relation to increasing role of communications in parallel computers this paper is devoted to modelling of communication complexity (number of communication steps) in the same way as we use to analyse computation complexity so in sequential algorithms. Based on this extended approach we are able better to optimise performance of all existed parallel computers. Another important problem is to analyse critical parts of communication influence to parallel computer performance and that at first in minimisation of communications at developing stages of any PA and secondly at its whole performance optimisation. Finally we have illustrated from the point of user the important role of communication in parallel computers on the chosen examples.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords

Computer; Processor; Parallel Computer; Parallel Algorithm; Communication; Interprocess Communications (IPC); Complexity; Optimisation; Efficiency

Full Text:

PDF

References

Abderazek A. B., Multicore systems on-chip – Practical Software/Hardware design, (Imperial college press, UK, August 2010, 200 pp.)
http://dx.doi.org/10.2991/978-94-91216-33-6

Arora Sanjeev, Barak Boaz, Computational Complexity, (Cambridge University Press, UK, 2009, 578 pages)
http://dx.doi.org/10.1017/cbo9780511804090

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

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

Gautam Natarajan, Analysis of Queues: Methods and Applications, (CRC Press, USA, 2012, 802 pages)

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

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

Hanuliak P., Hanuliak M., Analytical modelling in parallel and distributed computing, (Chartridge Book Oxford, UK, 2014, pp. 294)
http://dx.doi.org/10.11648/j.ajnc.20140301.11

Hanuliak P., Hanuliak M., Performance modelling of parallel computers NOW and Grid, J. of Networks and Communication, Science PG, Vol. 2/5, Issue 10, pp. 112-124, 2013, USA
http://dx.doi.org/10.11648/j.ajnc.20130205.11

Hanuliak J., Modeling of communication complexity in parallel computing, American J. of Networks and Communication, Science PG, 2014, Vol. 3, Special Issue 1, pp. 29-42, USA

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

Harchol-Balter Mor, Performance modelling and design of computer systems, (Queuing theory in action), (Cambridge University Press, UK, 2012)
http://dx.doi.org/10.1017/cbo9781139226424

Hennessy J. l., Patterson D. A., Computer architecture – a quantitave approach (5th edition), (Morgan Kaufmann, USA, 2011, 856 pages)

Kirk D. B., Hwu W. W., Programming massively parallel processors (2nd Edition), (Morgan Kaufmann, USA, 2012, 514 pages)

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

Kshemkalyani A. D., Singhal M., Distributed Computing, University of Illinois, (Cambridge University Press, UK, 2011, 756 pages)

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

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

Meerschaert M., Mathematical modeling (4 - th edition), (Elsevier, The Netherland , 2013, 384 pp.)

McCabe J., D., Network analysis, architecture, and design, (Elsevier/ Morgan Kaufmann, USA, 2010, 496 pages)

Miller S., Probability and Random Processes (2nd edition), (Academic Press, Elsevier Science, The Netherland, 2012, 552 pages)

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

Pacheco P., An Introduction to parallel computing, (Morgan Kaufmann, USA, 2011, pp. 370)

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

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

Tullis Thomas, Albert William, Measuring the User Experience - Collecting, Analyzing, and Presenting Usability Metrics, (Morgan Kaufmann, USA, 2013, 320 pages)

Zhuge H., The Knowledge Grid, (Imperial College Press, UK, 2011, pp. 360)

Refbacks

There are currently no refbacks.

Username
Password
Remember me