執行緒指派與資源分配問題最早在[15]中被定義，其目標是在多個同質伺服器上分配執行緒，並合理配置資源，以最大化整體系統效益。此問題可用來模擬多種實際應用情境，例如網站代管中心、雲端運算平台以及多核心處理器等。本文提出三種演算法：其中一種針對 [15]所提出的方法在特定條件下進行效能優化，另兩種則受到最小化最大完成時間問題中經典演算法的啟發，重新設計執行緒的分配策略。此外，我們發現原始架構下存在潛在的執行緒飢餓問題，因此設計出一套合理的機制以避免此問題，並進一步衡量改良方法的效能。實驗結果顯示，本文所提出的演算法在多種實驗場景中皆展現出優於常見啟發式方法與[15]所提出演算法的效能表現。

The Assign-and-Allocate (AA) problem, first introduced in~cite{9606219}, aims to assign threads to homogeneous servers and allocate server resources to maximize the system-wide utility. This problem models a variety of practical scenarios, including web hosting centers, cloud computing platforms, and multicore processors. In this paper, we propose three algorithms: one improves the performance of the method in~cite{9606219} under specific conditions, and the other two are inspired by classical algorithms for makespan minimization to redesign the thread assignment strategy. Moreover, we identify a potential issue of thread starvation in the original framework and propose a mechanism to prevent starvation while maintaining effective resource allocation. Experimental results demonstrate that our proposed methods outperform both common heuristic baselines and the algorithm presented in~cite{9606219} across a range of settings.

[1] Michela Becchi and Patrick Crowley. Dynamic thread assignment on heterogeneous multiprocessor architectures. In Proceedings of the 3rd conference on Computing frontiers, pages 29–40, 2006.
[2] Norman Bobroff, Andrzej Kochut, and Kirk Beaty. Dynamic placement of virtual machines for managing sla violations. In 2007 10th IFIP/IEEE International Symposium on Integrated Network Management, pages 119–128. IEEE, 2007.
[3] Bennett Fox. Discrete optimization via marginal analysis. Management science, 13(3):210–216, 1966.
[4] Zvi Galil and Nimrod Megiddo. A fast selection algorithm and the problem of optimum distribution of effort. J. ACM, 26(1):58–64, January 1979.
[5] George Gens and Eugene Levner. An approximate binary search algorithm for the multiple-choice knapsack problem. Information Processing Letters, 67(5):261–265, 1998.
[6] Laleh Ghalami and Daniel Grosu. Scheduling parallel identical machines to minimize makespan:a parallel approximation algorithm. Journal of Parallel and Distributed Computing, 133:221–231, 2019.
[7] R. L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45(9):1563–1581, Nov 1966.
[8] R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416–429, 1969.
[9] Allan Hartstein, Viji Srinivasan, Thomas R Puzak, and Philip G Emma. Cache miss behavior: is it√ 2? In Proceedings of the 3rd Conference on Computing Frontiers, pages 313–320, 2006.
[10] Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM, 34(1):144–162, January 1987.
[11] Brendan Jennings and Rolf Stadler. Resource management in clouds: Survey and research challenges. Journal of Network and Systems Management, 23:567–619, 2015.
[12] A Karve, Tracy Kimbrel, Giovanni Pacifici, Mike Spreitzer, Malgorzata Steinder, Maxim Sviridenko, and A Tantawi. Dynamic placement for clustered web applications. In Proceedings of the 15th international conference on World Wide Web, pages 595–604, 2006.
[13] Pan Lai and Rui Fan. Fast optimal nonconcave resource allocation. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 1508–1516. IEEE, 2015.
[14] Pan Lai, Rui Fan, Wei Zhang, and Fang Liu. Utility maximizing thread assignment and resource allocation. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 433–442, May 2016.
[15] Pan Lai, Rui Fan, Xiao Zhang, Wei Zhang, Fang Liu, and Joey Tianyi Zhou. Utility optimal thread assignment and resource allocation in multi-server systems. IEEE/ACM Transactions on Networking, 30(2):735–748, April 2022.
[16] Pan Lai, Yiran Tao, Jun Qin, Yuanai Xie, Shihua Zhang, Shanjiang Tang, Qirui Huang, and Shengquan Liao. Joint optimization of application placement and resource allocation for enhanced performance in heterogeneous multi-server systems. Computer Networks, 253:110692, 2024.
[17] Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic right-sizing for power-proportional data centers. IEEE/ACM Transactions on Networking, 21(5):1378–1391, Oct 2013.
[18] A Neebe and D Dannenbring. Algorithms for a specialized segregated storage problem. University of North Carolina, pages 77–5, 1977.
[19] Moinuddin K. Qureshi and Yale N. Patt. Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches.In 2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’06), pages 423–432, Dec 2006.
[20] Petar Radojkovi´c, Vladimir Cakarevi´c, Miquel Moret´o, Javier Verd´u, Alex Pajuelo, Francisco J Cazorla, Mario Nemirovsky, and Mateo Valero. Optimal task assignment in multithreaded processors: a statistical approach. ACM SIGPLAN Notices, 47(4):235–248, 2012.
[21] G. E. Suh, L. Rudolph, and S. Devadas. Dynamic partitioning of shared cache memory. Journal of Supercomputing, 28(1):7–26, 2004.
[22] Dominique Thiebaut. On the fractal dimension of computer programs and its application to the prediction of the cache miss ratio. IEEE transactions on Computers, 38(7):1012–1026, 2002.
[23] Bhuvan Urgaonkar, Arnold L Rosenberg, and Prashant Shenoy. Application placement on a cluster of servers. International Journal of Foundations of Computer Science, 18(05):1023–1041, 2007.
[24] Huidong Ye, Pan Lai, Xiao Zhang, Yuanai Xie, Liudong Zuo, Jianlin Zhu, Haiyan Yin, and Peiying Lin. Energy-aware thread assignment and resource allocation in multi-server systems. In 2025 10th International Conference on Computer and Communication System (ICCCS), pages 1171–1176, April 2025.