在有限決策時間下的雲端機器學習計算工 作排程總完工時間最佳化策略研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：135

、訪客IP：18.220.188.4

姓名

張峻瑋(Chun-Wei Chang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在有限決策時間下的雲端機器學習計算工作排程總完工時間最佳化策略研究
(Optimization Strategy for Makespan of ML-Task Scheduling on the Cloud with the Constraint of Scheduling Decision Time)

相關論文

★ 以伸展樹為基礎的Android Binder Driver	★ 應用增量式學習於多種農作物判釋之研究
★ 應用分類重建學習偵測航照圖幅中的新穎坵塊	★ 用於輔助工業零件辨識之尺寸估算系統
★ 使用無紋理之3D CAD工業零件模型結合長度檢測實現細粒度真實工業零件影像分類	★ 一個建立在平行工作系統上的動態全球計算平台
★ 用權重參照計數演算法執行主動物件垃圾收集	★ 一個動態負載平衡之最大可能性估算計算架構
★ 利用多項系統負載資訊進行動態P2P系統重組的策略研究	★ 基於Hadoop系統的雲端應用程式特徵擷取與計算監測架構
★ 適用於大型動態分散式系統的調適性計算模型	★ 一個提供彈性虛擬資料中心的雲端服務平台
★ 雲端彈性虛擬機房服務平台之資源控管中心	★ 一個適用於自動供應雲端系統的動態調適計算架構
★ 線性相關工作與非相關工作的探索式排程策略	★ 適用於大資料集高效率的分散式階層分群演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

由於機器學習的技術不斷的進步，任務對於雲端群集的需求逐漸增加，這些資源密集型的任務需要更多的計算資源來支持，更多的計算資源和任務就表示對於資源分配要有更好的處理。對於阿里巴巴所提出的模擬器，它是利用貪婪演算法進行任務排程，因為貪婪演算法存在著一些缺點，因此本論文提出以Min-Min演算法和Max-Min演算法以動態任務分配的方式來改善貪婪演算法的缺點。另外，所提出之排程演算法因具有高時間複雜度，這對於大規模分散式系統的任務排程造成了挑戰，所以提出了將任務已更小的單位切割任務資料集後再進行排程。實驗結果表明，Min-Min演算和Max-Min演算法之於阿里巴巴所提出的模擬器結果在任務的 Makespan 有良好的表現，而在切割任務後的結果來看也有良好的表現。

摘要(英)

Due to the continuous advancements in machine learning technology, there is a growing demand for tasks in cloud clusters. These resource-intensive tasks require more computational resources to support them. More tasks and computational resources imply a need for improved resource allocation. In the case of the simulator proposed by Alibaba, it utilizes a greedy algorithm for task scheduling. However, since greedy algorithms have their limitations, this paper suggests enhancing the drawbacks of the greedy algorithm by employing the Min-Min and Max-Min algorithms with dynamic task allocation.

Furthermore, the scheduling algorithms introduced here present a challenge due to their high time complexity, especially in the context of task scheduling in large-scale distributed systems. Therefore, it is proposed to break down the task dataset into smaller units for scheduling. Experimental results indicate that both the Min Min and Max-Min algorithms perform well in terms of the Makespan of tasks in Alibaba′s simulator. Moreover, when considering the results after task partitioning, these algorithms still demonstrate excellent performance.

關鍵字(中)

★ 雲端
★ 機器學習工作
★ 總完工時間最佳化
★ 快速排程策略

關鍵字(英)

★ Cloud Computing
★ ML-Task Scheduling
★ Scheduling Decision Time
★ Makespan

論文目次

摘要....i
Abstract....ii
目錄....iii
圖目錄.....iv
表目錄....v
一、緒論....1
1-1 研究背景....1
1-2 研究動機....2
1-3 論文架構....4
二、背景知識....5
2-1 Alibaba Simulator.....5
2-1-2 模擬器所使用的任務資料集....8
2-1-2 排程....8
2-2 最短完成時間（MCT） ....9
2-3 Min-Min 演算法 ....9
2-4 Max-Min 演算法....9
2-5 Min-Min、Max-Min 時間複雜度....10
三、研究內容與方法.... 11
3-1 排程演算法的選擇....11
3-2 排程演算法....12
四、實驗與結果討論....16
4-1 實驗環境設置....16
4-1-1 實驗前置作業....16
4-2 實驗設計....17
4-3 實驗結果與討論....17
4-3-1 第一部分：所提出的排程演算法與阿里巴巴比較....17
4-3-2 第二部分：將欲排任務切分成較小子集....23
五、結論與未來研究方向....25
5-1 結論....25
5-2 未來研究方向....25
參考文獻....27

參考文獻

[1] Akhilesh , J., & Arvind , U. (2019). Cloud scheduling using improved hyper heuristic framework. In R. Kamal, M. Henshaw, & P. Nair (Ed.), InteInternational Conference on Advanced Computing Networking and Informatics (pp. 127-133). Singapore: Springer Singapore.
[2] Alibaba. (2022, March 7). Alibaba Cluster Trace/cluster-trace-gpu-v2020. Retrieved from github.com: https://github.com/alibaba/clusterdata
[3] Arun, K. S., Michael , S., & Zhiyong , Z. (2018). Chapter 10 - Metaheuristic Algorithms: A Comprehensive Review. In A.-B. Mohamed , A.-F. Laila , & S. K. Arun , Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications (pp. 185-231). London: Academic Press.
[4] Chauhan, S., & Joshi, R. (2010). A weighted mean time Min-Min Max-Min selective scheduling strategy for independent tasks on Grid. 2010 IEEE 2nd International Advance Computing Conference (IACC), (pp. 4-9). Patiala, India.
[5] Fard, H., Prodan, R., & Wolf, F. (2020). Dynamic Multi-objective Scheduling of Microservices in the Cloud. 2020 IEEE/ACM 13th International Conference on Utility and Cloud Computing (UCC), (pp. 386-393). Leicester, UK.
[6] freeCodeCamp. (2019, 11 19). Greedy Algorithms Explained with Examples. Retrieved from freeCodeCamp.org: https://www.freecodecamp.org/news/what-is-a-greedy-algorithm/
[7] Gaurang , P., Rutvik, M., & Upendra, B. (2015). Enhanced Load Balanced Min-min Algorithm for Static Meta Task Scheduling in Cloud Computing. 3rd International Conference on Recent Trends in Computing 2015 (ICRTC-2015), 57, pp. 545-553. Ghaziabad, India.
[8] Huang, J., Xiao, C., & Wu, W. (2020). RLSK: A Job Scheduler for Federated Kubernetes Clusters based on Reinforcement Learning. 2020 IEEE International Conference on Cloud Engineering (IC2E), (pp. 116-123). Sydney, NSW, Australia.
[9] Jørgen, B.-J., Gregory, G., & Anders , Y. (2004, 11 15). When the greedy algorithm fails. Discrete Optimization, 1(2), pp. 121-127.
[10] Leo , B., Jerome , F., Charles , S. J., & Richard , A. (1984). Classification and Regression Trees. New York: Routledge.
[11] Lohi, S., & Tiwari, N. (2020). A high performance machine learning algorithm TspINA; scheduling multifariousness destined tasks by better efficiency. 2020 Fourth World Conference on Smart Trends in Systems, Security and Sustainability (WorldS4), (pp. 603-607). London, UK.
[12] Mala , K., & Sarbjeet, S. (2015, 11 01). A review of metaheuristic scheduling techniques in cloud computing. Egyptian Informatics Journal, 16, pp. 275-295.
[13] Min-Yi , T., Ping-Fang , C., Yen-Jan, C., & Wei-Jen, W. (2011). Heuristic scheduling strategies for linear-dependent and independent jobs on heterogeneous grids. Grid and Distributed Computing: International Conference (pp. 496--505). Jeju Island, Korea: Springer.
[14] Mokhtari, A., Hossen, M., Jamshidi, P., & Salehi, M. (2022). FELARE: Fair Scheduling of Machine Learning Tasks on Heterogeneous Edge Systems. 2022 IEEE 15th International Conference on Cloud Computing (CLOUD), (pp. 459-468). Barcelona, Spain.
[15] Qizhen, W., Wencong, X., Yinghao, Y., Wei, W., Cheng, W., Jian, H., . . . Yu, D. (2022). MLaaS in the wild: Workload analysis and scheduling in Large-Scale heterogeneous GPU clusters. 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22) (pp. 945--960). Renton, WA: USENIX Association.
[16] Sarraiuand, S., & Bien, F. (2020). Predictive Technique Of Task Scheduling For BigData In Cloud. 2020 International Conference on Emerging Smart Computing and Informatics (ESCI), (pp. 11-16). Pune, India.
[17] Vashishth, V., Chhabra, A., & Sood, A. (2017). A predictive approach to task scheduling for Big Data in cloud environments using classification algorithms. 2017 7th International Conference on Cloud Computing, Data Science & Engineering - Confluence, (pp. 188-192). Noida, India.
[18] Xiaotang , W., Minghe , H., & Jianhua, S. (2012). Study on Resources Scheduling Based on ACO Allgorithm and PSO Algorithm in Cloud Computing. 2012 11th International Symposium on Distributed Computing and Applications to Business, Engineering & Science, (pp. 219-222). Guilin, China.
[19] Xiumin, Z., Gongxuan, Z., Jin, S., Junlong, Z., Tongquan, W., & Shiyan, H. (2019, 4 1). Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based HEFT. Future Generation Computer Systems, 93, pp. 278-289.
[20] Yihui, F., Zhi, L., Yunjian , Z., Tatiana, J., Yidi , W., Yang, Z., . . . Tao, G. (2021). Scaling large production clusters with partitioned synchronization. 2021 USENIX Annual Technical Conference (USENIX ATC 21) (pp. 81--97). USENIX Association.

指導教授

王尉任(Wei-Jen Wang)

審核日期

2023-10-20

推文