OPTIMAL ALLOCATION OF LIMITED RESOURCES IN MULTIPROCESSOR SYSTEMS

Authors

  • A. I. Kosolap Oles Honchar Dnipro National University, Dnipro, Ukraine, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2025-2-18

Keywords:

multiprocessor systems, optimization models, problems with Boolean variables, heuristic algorithms, exact quadratic regularization method, final principle

Abstract

Context. The paper considers multiprocessor systems consisting of many processors with a common RAM. The efficiency of such systems depends on the operating system. It must ensure a uniform loading of processors with tasks, in which the peak load on RAM will be minimal. This is a rather complex problem. In this paper, it is solved by building optimization models and developing effective heuristic algorithms. This problem is solved in two stages. The first stage is the optimal loading of processors with tasks, and the second is the minimization of the peak load on RAM. Several optimization models of this problem have been built, for the solution of which the exact quadratic regularization method is effective. Effective heuristic algorithms have also been developed. Comparative computational experiments have been conducted, which confirm the effectiveness of the proposed technology for solving this problem.
Objective. Development of mathematical optimization models, methods, and algorithms for optimal resource allocation in multiprocessor systems.
Method. A two-stage solution to this problem is effective. Several optimization models containing Boolean variables are proposed. Such models are quite complex for finding optimal solutions. To solve them, it is proposed to use the method of exact quadratic regularization. This optimization method is used for the first time for this class of problems, so it required the development of appropriate algorithmic support. Heuristic algorithms are usually implemented in operating systems. Therefore, effective heuristic algorithms are proposed that use the final principle, which significantly improves the solution of the problem.                                                                                                                                                                                                Results. New optimization models for the allocation of limited resources in multiprocessor systems have been constructed. Effective heuristic algorithms have been developed, which are implemented software-wise using VBA in the Excel package. Software for entering initial data for optimization models has also been developed, which simplifies their solution. The results of computational experiments are presented.
Conclusions. A new effective technology for optimal resource allocation in multiprocessor systems has been developed. Heuristic algorithms have been developed and implemented in software. Computational experiments have been conducted to confirm the effectiveness of the proposed technology for solving the problem.

 

Author Biography

A. I. Kosolap, Oles Honchar Dnipro National University, Dnipro, Ukraine

Doctor of Physical and Mathematical Sciences, Professor, Professor of the Department of Computer Science and Information Technologies

References

Kosolap A. A new method for global optimization, ESAIM: Proceedings and surveys, 2021, Vol. 71, pp. 121–130. DOI 10.1051/proc/202171121.

Ramamoorthy C. V., Chandy K. M. and Gonzalez M. J. Optimal Scheduling Strategies in a Multiprocessor System, IEEE Transactions on Computers, 1972, Vol. C-21, No. 2, pp. 137-146. DOI: 10.1109/TC. 1972.5008918.

Coffman E. G., Garey Jr., M. R., and Johnson D. S. An Application of Bin-Packing to Multiprocessor Scheduling, SIAM Journal of Computing, 1978, Vol. 7, Iss. 1, pp. 1-17. DOI: 10.1137/0207001.

Garey M. R. and Johnson D. S. Complexity Results for Multiprocessor Scheduling under Resource Constraints, SIAM Journal on Computing, 1975, Vol. 4, Iss. 4, pp. 397-411. DOI: 10.1137/0204035.

Dilawar N., Zakarya M. and Rahman I. Ur A Review of Power Efficient Load Balancing Algorithms for Multicore Systems, World Applied Sciences Journal, 2013, Vol. 27(9), pp. 1175-1182. DOI: 10.5829/idosi. wasj. 2013.27.09.1627.

Vidyarthi D. P., Sarker D. K., Tripathi A. K., Yang L. T. Scheduling in Distributed Computing Systems Analysis, Design & Models. Springer Science+Business Media, LLC, 2009, 300 p.

Khawatreh S. A. An Efficient Algorithm for Load Balancing in Multiprocessor Systems, International Journal of Advanced Computer Science and Applications, 2018, Vol. 9, No. 3, pp. 160-164. DOI: 10.14569/ IJACSA.2018.090324.

Kermia O. and Sorel Y. Load Balancing and Efficient Memory Usage for Homogeneous Distributed Real-Time Embedded Systems, International Conference on Parallel Processing. Workshops, Portland, OR, USA, 2008, pp. 39-46. DOI: 10.1109/ICPP-W.2008.20.

Teixeira R. B., Lima G. Shared resources in multiprocessor real-time systems scheduled by RUN, Real-Time Syst., 2022, No. 58, pp. 153–188. DOI 10.1007/ s11241-021-09374-3.

Walter R., Lawrinenko A. A characterization of optimal multiprocessor schedules and new dominance rules, Journal of Combinatorial Optimization, 2020, Vol 40, pp. 876–900. DOI 1007/s10878-020-00634-9.

Mehrabi A., Mehrabi S., Mehrabi Ali D. An Adaptive Genetic Algorithm for Multiprocessor Task Assignment Problem with Limited Memory. [Electronic resource]. Access mode: https://www.oalib.com/research/2169214

Revilla-Duarte U., Ramırez-Salinas M. A., Villa-Vargas L. A., Tchernykh A. Proactive Load Balancing to Reduce Unnecessary Thread Migrations on Chip Multi-Processor (CMP) System, Computación y Sistemas, 2024, Vol. 28, No. 2, pp. 623–645. DOI: 10.13053/CyS-28-2-4403.

Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Springer-Verlag Berlin Heidelberg, 2004, 554 p. DOI l0.I007/978-3-540-24777-7.

Hill R. R., Hiremath C. S. Generation Methods for Multidimensional Knapsack Problems and their Implications, Systemics, Cybernetics and Informatics, 2007, Vol. 5, № 5, pp. 59–64. DOI: 10.54808/JSCI.21.04.42.

Published

2025-06-29

How to Cite

Kosolap, A. I. (2025). OPTIMAL ALLOCATION OF LIMITED RESOURCES IN MULTIPROCESSOR SYSTEMS. Radio Electronics, Computer Science, Control, (2), 209–216. https://doi.org/10.15588/1607-3274-2025-2-18

Issue

Section

Progressive information technologies