顏嗣鈞臺灣大學：電機工程學研究所彭孟池Peng, Meng-ChihMeng-ChihPeng2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/53041在問題計算量常常非常龐大的今天，如何能將多台電腦串聯一起、共同計算工作已是一項重要課題。分散式運算已行之有年，也能夠順利的將來自不同地方的相異資源做有效的分配、利用。然而在刀鋒式伺服器的系統裡，如法炮製使用分散式運算的模式並不是明智之舉。舉凡如資源性質的異同性，聯繫各資源之間的網路型態、速度，皆指出在刀鋒式伺服器的管理上，其排程(scheduling)、配對(matchmaking)、配置(allocation)演算法均可再由分散式運算的現有方法再加以改進。本篇論文主要在探討刀鋒式伺服器該如何處理高計算量的工作，以求得較佳效率。我們以修改過的配對方法，來充分利用刀鋒式伺服器的高速頻寬，減少配對階段鎖耗費的時間與資源。並且採用類似網際網路上避免碰撞時所使用的概念，將每次進行配對、配置的工作以指數方式成長╱遞減，並提出一套有效的配置演算法。最後並實際在刀鋒式伺服器上進行實驗，與其他方法做個比較。 本論文的組織如下：第一章先簡單敘述現今的計算需求以及分散式運算和刀鋒式伺服器之異同。第二章介紹相關理論基礎，包含Amdahl's Law以及配對(matchmaking)機制。第三章則介紹、說明一套將排程(scheduling)、配對、配置(allocation)三者整合的演算法，並探討其實作方面的考量。第四章將從刀鋒式伺服器的接收工作輸入、中間的工作處理流程，一直到工作輸出，對整體系統架構及流程做個完整的說明。第五章則以實際測試結果來印證基礎理論以及演算法分析。並於第六章提出結論和未來工作展望，由前面所得之結果整理出結論，同時提出本論文尚未能臻至完美之處。最後附上所有在撰寫本論文時所借重之參考文獻。摘要 ……………………………………………………………………… 3 第一章 序論 …………………………………………………………… 4 第二章 理論基礎 ……………………………………………………… 6 2.1 Amdahl's Law ………………………………………………… 6 2.2 配對(Matchmaking) …………………………………………… 7 第三章 演算法與其實作 ………………………………………………… 12 3.1 計劃/排程(Scheduling) ……………………………………… 12 3.1.1 工作佇列(Job Queue) ………………………………… 12 3.1.2 等待週期(Job Fetching Interval) ………………… 13 3.1.3 工作取出量(Job Fetching Window Size) …………… 14 3.2 配對(Matchmaking) …………………………………………… 16 3.2.1 要求條件 ………………………………………………… 16 3.2.2 蒐集資訊 ………………………………………………… 16 3.3 配置(Allocation) …………………………………………… 17 3.3.1 資源配置(Resource Allocation)的選擇方法 ……… 19 3.3.2 依實際需要決定不同的演算法抉擇 ………………… 24 3.3.3 找出最佳解(滿足最多工作數) ……………………… 25 3.3.4 避免飢餓(Starvation) ………………………………… 26 3.4 演算法分析 ……………………………………………………… 26 3.4.1 等待週期(Job Fetching Interval)的影響 …………… 27 3.4.2 工作取出量(Job Fetching Window Size)的影響 … 30 3.4.3 求最佳解的影響 ……………………………………… 31 3.4.4 時間複雜度(Time Complexity) ……………………… 32 第四章 系統架構 ……………………………………………………… 34 4.1 系統之輸入及輸出 …………………………………………… 35 4.1.1 系統輸入 ………………………………………………… 35 4.1.2 系統輸出 ………………………………………………… 37 4.2 架構及流程 ……………………………………………………… 38 4.2.1 資料庫 ………………………………………………… 38 4.2.2 蒐集最新資訊 …………………………………………… 40 4.2.3 工作佇列 ………………………………………………… 41 4.2.4 工作處理 ………………………………………………… 42 4.2.5 PVM ……………………………………………………… 43 第五章 實驗環境及實驗數據 …………………………………………… 44 5.1 Amdahl's Law ………………………………………………… 45 5.2 等待週期(Job Fetching Interval)的影響 ………………… 52 5.3 工作取出量(Job Fetching Window Size)的影響 …………… 55 5.4 可用資源總數的影響 …………………………………………… 61 第六章 結論及未來工作展望 …………………………………………… 63 第七章 參考文獻 ……………………………………………………… 643520345 bytesapplication/pdfen-US工作配對工作配置刀鋒伺服器刀鋒式伺服器工作排程allocationjob schedulingblade serverbladematchmakingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53041/1/ntu-93-R91921019-1.pdf