.png){kind=icon}
Return
Utility Optimal Thread Assignment and Resource Allocation in Multi-Server Systems
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2021.3123817.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Achieving high performance in many multi-server systems (e.g., web hosting center, cloud) requires finding a good assignment of worker threads to servers and also effectively allocating each server's resources to its assigned threads. The assignment and allocation components of this problem have been studied extensively but largely separately in the literature. In this paper, we introduce the assign and allocate (AA) problem, which seeks to simultaneously find an assignment and allocation that maximizes the total utility of the threads. Assigning and allocating the threads together can result in substantially better overall utility than performing the steps separately, as is traditionally done. We model each thread by a utility function giving its performance as a function of its assigned resources. We first prove that the AA problem is NP-hard. We then present a 2 (root 2-1) > 0.828 factor approximation algorithm for concave utility functions, which runs in O(mn(2) + n (log mC)(2)) time for n threads and m servers with C amount of resources each. We also give a faster algorithm with the same approximation ratio and O(n (log mC)(2)) time complexity. We then extend the problem to two more general settings. First, we consider threads with nonconcave utility functions, and give a 1/2 factor approximation algorithm. Next, we give an algorithm for threads using multiple types of resources, and show the algorithm achieves good empirical performance. We conduct extensive experiments to test the performance of our algorithms on threads with both synthetic and realistic utility functions, and find that they achieve over 92% of the optimal utility on average. We also compare our algorithms with a number of practical heuristics, and find that our algorithms achieve up to 9 times higher total utility.
Keywords:
Servers
Resource management
Message systems
Approximation algorithms
Multicore processing
Instruction sets
IEEE transactions
Assignment and allocation
utility
algorithms
multi-server systems
web hosting center
cloud
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K
Organization
Cited Papers
ShareSaveShareSaveCPU, GPU and FPGA Implementations of MALD: Ceramic Tile Surface Defects Detection Algorithm.png)
Automatika
OAAI
AutomatikaIF0
OAAIShareSave
View more