Application of rank approach algorithms in planning task distribution in multiprocessor systems

Abstract

The article discusses the application of rank-based algorithms in planning task distribution in multiprocessor systems, which is currently a fairly pressing issue related to the evolution of computing devices, mass transition to multi-core processor architectures, widespread use of Internet resources, and, at the same time, demand for servers and data centers. Evidence is provided of the possibility to reduce the task planning problem in multiprocessor systems to the multiple solution of the integer programming problem with Boolean variables (IPP with Bv).

The authors consider two approximate algorithms for solving the IPP problem with Bv using the example of the classical knapsack problem. Both algorithms are based on the fundamentals of the rank approach. The operation of both is based on the work of the general procedure for constructing solution vectors A0 using the rules for cutting off unpromising paths L1, L2, L3. The logic of each of the three strategies and software options for their implementation are considered. It was found that strategies L1 and L2 can be implemented by sorting or linear search for suitable vectors for constructing vectors of the next rank. For strategy L3, which in its standard form offers cutting off paths based on their maximum potential increase in functionality, a modification is proposed that allows cutting off a larger number of paths without performing checks for each of them.The process of declaring security profiles includes several stages, such as assessing the current state of security, identifying threats and vulnerabilities, defining security requirements, developing and implementing security profiles, and regularly monitoring and updating security measures.

The authors present the results of experimental studies, according to which, when using approximate algorithms A1 and A2, the obtained answer usually does not exceed 10% of the error from the exact one, regardless of the selected software implementation. At the same time, it is possible to reduce the number of analyzed vectors to 170,000 versus 2¹⁵⁰ in the case of a complete enumeration. Using the proposed modification for the L3 strategy allows us to reduce the number of analyzed vectors by an average of another 40,000.

The authors conclude that among the proposed algorithms, the most advantageous is the use of A2 implemented using the L1 strategy through a linear search and a modified L3 strategy.