在分散式系統中的簡易啟發式多工配置方式

Abstract

分散式計算系統由於其迷人的優點已經成為目前電腦系統設計的主 流, 而提供程式和資料檔案多份重複以改善系統可靠度即眾多重要特性之 一. 以可靠度為導向的案件配置問題就是找出一種好的案件分配方法, 使 得分散式系統的可靠度為最佳. 因為案件配置問題已經被證明為 NP- hard, 因此我們提出一種簡易啟發式的演算法來求得近似最佳解. 這 篇論文中我們針對案件配置問題提出一個叫做簡易啟發式多工配置方式( Heuristic Multi-task Assignment, HMA)的演算法, 這個演算法使用一 些簡易的方法來減低問題的複雜度, 同時也把許多解決相關問題的類似演 算法所未考慮的多份重複因素列入考慮. 由模擬實驗的結果顯示, HMA 可 以迅速的求得近似最佳的案件配置方式. 最後, 時間的複雜度我們也會加 以分析. Distributed Computing System (DCS) has become major trend in today's computer system design due to its charming advantages. And one ofDCS important characteristics is it offers redundant copies of programs anddata-files to improve system reliability. The reliabiility-oriented taskassignment problem is to find a task distribution such that the DistributedSystem Reliability is maximum. Since task assignment problem we discussed has been proved to be NP-hard, we introduce a heuristic algorithm to generate near-optimum solution. In this thesis, we proposed a heuristic algorithm called Heuristic Multi-task Assignment (HMA) algorithm for the task assignment problem, which uses some heuristics to reduce the problem space. The proposed algorithmalso take copies of tasks which are not considered in most related algorithmsinto account. Based on the simulation results, the proposed HMA algorithm can obtain suboptimal tasks assignment with much less computation time. Also,the time complexity of the proposed algorithm is analyzed.