Open Access Open Access  Restricted Access Subscription or Fee Access

Optimisation of Communication Complexity in Parallel Computing


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecos.v11i2.8471

Abstract


Parallel principles have been for a long time the most effective way how to increase performance in parallel computing (parallel computers, parallel algorithms). Dominant parallel computers are based on network of workstations (NOW) and on high integrated network of NOW modules (Grid). Effective using of such parallel computers assumes minimisation of at least substantial overheads representing with overhead function h(s, p). To the most important overhead latency belongs communication latency representing by inter process communication (IPC) of decomposed parallel processes. In this sense the paper is devoted to the modelling of communication complexity in unified parallel and distributed computing. This overhead function, representing by communication overhead, is then an integral part of the complex parallel execution time. Based on this we are able better to optimise PA during the developing process of PA and to come to final effective (optimised) PA. The article analysis such parts in PA developing process which are critical to communication complexity and that first the critical role of problem parallelisation (decomposition strategy) and second at own performance PA optimisation (shared memory, distributed memory, hybrid). Based on analysed optimised examples of PA the paper illustrates these critical parts from the point of user. In similar way the article point to concept of complex isoefficiency function to asymptotic performance predictions of given complex problems on given parallel computer in order to illustrate critical role of decomposition strategy and needed optimisation of communication complexity to developed effective PA.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords


Parallel Computer; Parallel Algorithm; Decomposition Strategy; Optimisation; Overhead Function; Inter Process Communications (IPC); Complex Isoeffiency

Full Text:

PDF


References


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

Alasha'ary, H., Matrouk, K., Al-Hasanat, A., Alqadi, Z., Al-Shalabi, H., Improving Matrix Multiplication Using Parallel Computing, (2013) International Journal on Communications Antenna and Propagation (IREIT), 1 (6), pp. 346-349.

Ben Halima, N., Compile-Time Task Scheduling in Computer Networks Using Non-Preemptive Processing and Time Quantum, (2015) International Journal on Communications Antenna and Propagation (IRECAP), 5 (3), pp. 169-177.
http://dx.doi.org/10.15866/irecap.v5i3.5766

Dubois M., Annavaram M., Stenstrom P., Parallel Computer Organization and Design, Cambridge university press, UK, 560 pages, 2012
http://dx.doi.org/10.1017/cbo9781139051224

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

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

Hanuliak M., Hanuliak J., Decomposition models of parallel algorithms, AJNC, Vol. 3, Special Issue 1, Science PG, USA,2014, pp. 70-84

Hanuliak J., Modelling of communication complexity in parallel computing, AJNC, Vol. 3, Special Issue 1, Science PG, USA, 2014, pp. 29-42

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

Harchol-BalterMor, Performance modelling and design of computer systems, Cambridge University Press, UK, 2013, 576 pp.

Hwang K. and coll., Distributed and Parallel Computing, Morgan Kaufmann, USA, 2011, 472 pages

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

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

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

Levesque John, High Performance Computing: Programming and applications, CRC Press, USA, 2010, 244 pages
http://dx.doi.org/10.1201/b10442

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

Misra Ch. S.,Woungang I., Selected topics in communication network and distributed systems, Imperial college press, United Kingdom, 2010, 808 pages

Peterson L. L., Davie B. C., Computer networks – a system approach, Morgan Kaufmann, USA, 2011, 920 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

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


Refbacks

  • There are currently no refbacks.



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