OPTIMAL ALLOCATION OF LIMITED RESOURCES IN MULTIPROCESSOR SYSTEMS
DOI:
https://doi.org/10.15588/1607-3274-2025-2-18Keywords:
multiprocessor systems, optimization models, problems with Boolean variables, heuristic algorithms, exact quadratic regularization method, final principleAbstract
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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 A. I. Kosolap
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
