Effective Distribution of Tasks in Multiprocessor and Multi-Computers Distributed Homogeneous Systems

Authors

  • Serhii Zybin
  • Vladimir Khoroshko
  • Volodymyr Maksymovych
  • Ivan Opirskyy

DOI:

https://doi.org/10.47839/ijc.20.2.2168

Keywords:

optimization, distribution, performance, computing module, multiprocessor, multicomputer, neural network

Abstract

Nowadays, a promising is the direction associated with the use of a large number of processors to solve the resource-intensive tasks. The enormous potential of multiprocessor and multicomputer systems can be fully revealed only when we apply effective methods for organizing the distribution of tasks between processors or computers. However, the problem of efficient distribution of tasks between processors and computers in similar computing systems remains relevant. Two key factors are critical and have an impact on system performance. This is load uniformity and interprocessor or intercomputer interactions. These conflicting factors must be taken into account simultaneously in the distribution of tasks in multiprocessor computing systems. A uniform loading plays a key role in achieving high parallel efficiency, especially in systems with a large number of processors or computers. Efficiency means not only the ability to obtain the result of computations in a finite number of iterations with the necessary accuracy, but also to obtain the result in the shortest possible time. The number of tasks intended for execution on each processor or each computer should be determined so that the execution time is minimal. This study offers a technique that takes into account the workload of computers and intercomputer interactions, and allows one to minimize the execution time of tasks. The technique proposed by the authors allows the comparison of different architectures of computers and computing modules. In this case, a parameter is used that characterizes the behavior of various models with a fixed number of computers, as well as a parameter that is necessary to compare the effectiveness of each computer architecture or computing module when a different number of computers are used. The number of computers can be variable at a fixed workload. The mathematical implementation of this method is based on the problem solution of the mathematical optimization or feasibility.

References

D. A. Patterson, J. L. Hennesy, Computer Organization and Design: The Hardware/Software Interface: ARM Edition, Morgan Kaufmann, 2017, 1074 p.

M. Wolf, Computers as Components: Principles of Embedded Computing System Design, 3rd Ed., Morgan Kaufmann, Elsevier, 2012, XXIII, 500 p.

F. Gebali, Algorithms and Parallel Computing, John Wiley & Sons, 2011, https://doi.org/10.1002/9780470932025.

H. El-Rewini, M. Abd-El-Barr, Advanced Computer Architecture and Parallel Processing, John Wiley & Sons, 2005, 287 p. https://doi.org/10.1002/0471478385.

J.-L. Baer, Microprocessor Architecture from Simple Pipelines to Chip Multiprocessors, Cambridge University Press, New York, 2010, 384 p. https://doi.org/10.1017/CBO9780511811258.

S.V. Zybin, V.O. Khoroshko, “Productivity and optimization of specialized information processing systems that have a structure, is configured by software,” Informatics and Mathematical Methods in Simulation, vol. 9, no. 3, pp. 120–130, 2019, https://doi.org/10.15276/imms.v9.no3.120. (In Ukrainian)

M. Dubois, M. Annavaram, P. Stenström, Parallel Computer Organization and Design, Cambridge: Cambridge University Press, 2012, 566 p.

M. Iverson, F. Ozguner, “Dynamic, competitive scheduling of multiple DAGs in a distributed heterogeneous environment,” Proceedings of the Seventh IEEE Heterogeneous Computing Workshop, Orlando, Florida USA, March 30, 1998, pp. 70–78.

P. Marshall, K. Keahey, T. Freeman, “Improving utilization of infrastructure clouds,” Proceedings of the IEEE / ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid’2011), Newport Beach, CA, USA, May 23–26, 2011, pp. 205–214, https://doi.org/10.1109/CCGrid.2011.56.

J. H. Lala, Performance Evaluation of a Multiprocessor in a Real Time Environment, Ph.D. Thesis, Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1976. https://dspace.mit.edu/handle/1721.1/61020.

H. El‐Rewini, M. Abd‐El‐Barr, Advanced Computer Architecture and Parallel Processing, Wiley-Interscience, 2004, 272 p. https://doi.org/10.1002/0471478385.ch3.

E. De Coninck, T.Verbelen, “Distributed neural networks for internet of things: The big-little approach,” Proceedings of the Second International Summit on Internet of Things. IoT Infrastructures: IoT 360°, Rome. Italy. October 27-29, 2015, Revised Selected Papers, Part II, pp. 484-492, https://doi.org/10.1007/978-3-319-47075-7_52.

Fundamentals of Grid Computing Theory, Algorithms and Technologies, Numerical Analysis and Scientific Computing, Edited by Frédéric Magoulès, Chapman and Hall/CRC; 1 st edition, 2009, 322 p. https://doi.org/10.1201/9781439803684-c1.

N. Kussul, L. Hluchy, A. Shelestov, S. Skakun, O. Kravchenko, M. Ilin, Yu. Gripich, A. Lavrenyuk, “Data fusion grid segment,” Space Science and Technology, vol. 15, no. 2, pp. 49–55, 2009, https://doi.org/10.15407/knit2009.02.049.

G. Capannini, F. Silvestri, and R. Baraglia, “K-model: A new computational model for stream processors,” Proceedings of the 2010 IEEE 12 th International Conference on High Performance Computing and Communications, HPCC’2010, 2010, pp. 239–246, https://doi.org/10.1109/HPCC.2010.22.

Proceedings of the 15-th International Workshop on Heterogeneous Wireless Networks (HWISE-2019), Kunibiki Messe, Matsue, Japan, March 27–29, 2019. URL: http://voyager.ce.fit.ac.jp/conf/hwise/2019/.

X. Lu, L. Chen, & Z. Li, “Performance evaluation and enhancement of process-based parallel loop execution,” Int J Parallel Prog, vol. 45, pp. 185–198, 2017, https://doi.org/10.1007/s10766-015-0394-1.

H. Gao, A. Schmidt, A. Gupta, P. Luksch, “Load balancing for spatial –grid-based parallel numeric simulations on clusters of SMPs,” Proceeding of the 11th Euromicro Conference on Parallel, Distributed and Network based Processing (PDP’2003), Genoa, Italy February, 5–7, 2003, pp. 75–82.

H. Gao, A. Schmidt, A. Gupta, P. Luksch, “A graph-matching based intra-mode task assignment methodology for SMP clusters,” Proceeding of the 7th World Multiconference on Systemics, Cybernetics and Informatics (SCI’2003), Orlando, Florida, USA, July, 27–30, 2003, pp. 406 – 411.

C. R. Kothari, Research Methodology: Methods and Techniques, Second revised edition, New Age International, 2007, 414 p.

C. Andre, R. Pinheiro, F. McNeill, Heuristics in Analytics: A Practical Perspective of What Influences Our Analytical World, John Wiley & Sons Inc, 2014, 256 p. https://doi.org/10.1002/9781118434260.

G. Karypis, V. Kumar, “Unstructured tree search on SIMD parallel computers,” IEEE Transactions on Parallel and Distributed Systems, vol. 5, issue 10, pp. 1057–1072, 2004, https://doi.org/10.1109/71.313122.

M.A. Miroshnik, L.A. Klimenko, “Placement of subtasks in distributed computing systems of cluster-metacomputing type,” Information and Control Systems on Railway Transport, no. 4, pp. 71–77, 2014. (in Russian)

H. Shafiee, M. N. Moqadam, “Information resources management (IRM): The key of accountability,” Jurnal Fikrah. Jilid 8, Special Issue 1, pp. 232–246, 2017.

A. D. Kshemkalyani, M. Singhal, Distributed Computing Principles, Algorithms, and Systems, Cambridge University Press, 2008, 754 p. https://doi.org/10.1017/CBO9780511805318.

W. L. Winston, Introduction to Mathematical Programming Operations Research: Volume One, 4th Edition, Thomson Brooks/Cole, 2003, 924 p.

Y.S. Yvanchenko, V.A. Khoroshko, “Analysis of information resource traffic,” Informational security, no. 1, pp. 63–68, 2013. (in Russian)

L. Li, K. Ota and M. Dong, “Deep learning for smart industry: Efficient manufacture inspection system with fog computing,” IEEE Transactions on Industrial Informatics, vol. 14, no. 10, pp. 4665-4673, 2018, https://doi.org/10.1109/TII.2018.2842821.

V. Dudykevych, I. Prokopyshyn, V. Chekurin, I. Opirskyy, Yu. Lakh, T. Kret, Ye. Ivanchenko, I. Ivanchenko, “A multicriterial analysis of the efficiency of conservative information security systems,” Eastern-European Journal of Enterprise Technologies. Information and Controlling System, vol. 3, no. 9(99), pp. 6-13, 2019, https://doi.org/10.15587/1729-4061.2019.166349.

L. Karpov, V. Feldman and A. Sheerai, “Universal engineering console and its software for Elbrus-1 and Elbrus-2 multiprocessor computer systems,” Proceedings of the 2017 Fourth International Conference on Computer Technology in Russia and in the Former Soviet Union (SORUCOM), Zelenograd, 2017, pp. 54-63, https://doi.org/10.1109/SoRuCom.2017.00014.

J. Gómez-Luna, E. Herruzo, & J. I. Benavides, José, “MESI Cache Coherence Simulator for Teaching Purposes,” CLEI Electron. J., vol. 12, no. 1, 2009, https://doi.org/10.19153/cleiej.12.1.5.

Downloads

Published

2021-06-28

How to Cite

Zybin, S., Khoroshko, V., Maksymovych, V., & Opirskyy, I. (2021). Effective Distribution of Tasks in Multiprocessor and Multi-Computers Distributed Homogeneous Systems. International Journal of Computing, 20(2), 211-220. https://doi.org/10.47839/ijc.20.2.2168

Issue

Section

Articles