Optimisation of Communication Complexity in Parallel Computing
(*) Corresponding author
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
Full Text:
PDFReferences
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