Оптимальний розподіл обмежених ресурсів в мультипроцесорних системах

Abstract

UK: Актуальність. В роботі розглядаються мультипроцесорні системи, які складаються з безлічі процесорів з загальною оперативною пам’яттю. Ефективність функціонування таких систем залежить від операційної системи. Вона повинна забезпечити рівномірне завантаження процесорів завданнями, при якому пікове навантаження на оперативну пам'ять буде мінімальним. Це досить складна проблема. В даній роботі вона розв’язується шляхом побудови оптимізаційних моделей та розробкою ефективних евристичних алгоритмів. Дана проблема розв’язується в два етапи. На першому етапі знаходиться оптимальне завантаження процесорів завданнями, а на другому – мінімізація пікового навантаження оперативної пам’яті. Побудовано декілька оптимізаційних моделей цієї задачі, для розв’язування яких ефективним є метод точної квадратичної регуляризації. Розроблені також ефективні евристичні алгоритми. Проведені порівняльні обчислювальні експерименти, які підтверджують ефективність запропонованої технології розв’язування даної проблеми. Мета роботи. Розробка математичних оптимізаційних моделей, методів та алгоритмів оптимального розподілу ресурсів в мультипроцесорних системах. Метод. Ефективним є двоетапний розв’язок даної проблеми. Запропоновано декілька оптимізаційних моделей, які містять булеві змінні. Такі моделі досить складні для знаходження оптимальних розв’язків. Для їх розв’язування пропонується використовувати метод точної квадратичної регуляризації. Цей метод оптимізації використовується вперше для даного класу задач, тому він потребував розробки відповідного алгоритмічного забезпечення. В операційних системах, як правило, реалізуються евристичні алгоритми. Тому пропонуються ефективні евристичні алгоритми, які використовують фінальний принцип, що значно покращує розв’язок задачі. Результати. Побудовані нові оптимізаційні моделі розподілу обмежених ресурсів в мультипроцесорних системах. Розроблені ефективні евристичні алгоритми, які реалізовані програмно засобами VBA в пакеті Excel. Розроблене також програмне забезпечення для введення початкових даних оптимізаційних моделей, що спрощує їх розв’язування. Приведені результати обчислюваних експериментів. Висновки. Розроблена нова ефективна технологія оптимального розподілу ресурсів в мультипроцесорних системах. Розроблені евристичні алгоритми, які реалізовані програмно. Проведені обчислювальні експерименти підтверджують ефективність запропонованої технології розв’язування задачі. EN: 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.