[[alternative]]The decision model of task allocation for constrained stochastic distributed systems

碩士[[abstract]]由於分散式系統具有高速和可靠的優點，因此分散式系統已普遍被運用於日常生活中，例如電力控制系統、自動提款機系統。在分散式系統環境下可將軟體執行視為一個任務，而軟體是由數個模組所構成，當執行任務時會將模組分配到系統中的各個運算節點上執行，因此可將分散式系統的系統可靠度定義為系統能成功完成整個任務的機率。在設計分散式系統時，若系統硬體架構已固定，系統可靠度主要是受軟體設計影響，而任務配置是軟體設計的一個重要階段，因此本研究提出一適用於機率型分散式系統的任務配置決策模式，此模式的決策目標為系統可靠度最大化，而我們的系統可靠度函數是以Cheung所提出的馬可夫模式為發展基礎，由模組可靠度、節點的硬體可靠度、模組的執行轉移機率與模組配置策略所構成。此模式是以運算節點的儲存空間與運算負載量以及所能承擔的最大系統成本做為本模式的限制條件，使用限制規劃求解。最後，我們利用一案例說明此模式之應用，並針對模組可靠度與節點硬體可靠度進行敏感度分析。[[abstract]]With the advantages of high speed and high reliability, distributed systems, like power control system or ATM, have already been widely applied in daily lives. In a distributed system, a software application could be called a task and software is composed of a set of cooperating modules. Each module of a task will be executed on one of the processors of the distributed system. Then the system reliability of a distributed system could be defined as the probability that the system can run an entire task successfully. In designing a distributed system, if its hardware configuration is fixed, then its system reliability will depend mainly on the software design. Task allocation is an important step in distributed software design. This thesis aims to build a decision model of task allocation that is suitable for the stochastic distributed systems. Based on the Markov model proposed by Cheung, the objective function of the model is to maximize the system reliability, which is composed of module reliability, hardware reliability of processing nodes, transition probability between modules, and module allocation strategy. The model includes constraints about storage and load limitations at each processor and constraints about bounds of system cost, and solves the task allocation problem by Constraint Programming. Finally, we apply the decision model in an extended case, and perform sensitivity analysis for module reliability and hardware reliability.[[tableofcontents]]目 錄 第1章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 3 1.3 論文架構 4 第2章 文獻探討 7 2.1 系統可靠度計算方式 7 2.2 分散式系統任務配置相關文獻 9 2.3 限制規劃 15 第3章 模式建構 18 3.1 問題定義 18 3.2 系統環境的假設與限制 18 3.3 變數說明 19 3.4 系統可靠度計算 22 3.5 模式限制式 24 3.6 任務配置決策模式 26 第4章 模式案例與敏感度分析 27 4.1 案例說明 27 4.2 敏感度分析 30 第5章 結論與未來研究方向 35 5.1 結論 35 5.2 未來研究方向 36 參考文獻 38 附錄一 敏感度分析數據 40 附錄二 模式程式碼 43 圖 目 錄 圖 1：研究流程圖 6 圖 2：模組的轉移執行機率 29 圖 3：各模組可靠度改變對系統可靠度的影響 32 圖 4：各節點硬體可靠度改變對系統可靠度的影響 33 表 目 錄 表1 節點的儲存負荷量、運算負載量及硬體可靠度 27 表2 模組的儲存需求量、運算需求量及可靠度 28 表3 節點間的通訊連結其單位資料量的傳輸成本(元/KB) 28 表4 模組在各個節點上的執行成本(/元) 28 表5 模組間的傳輸資料量(/KB) 28 附 表 目 錄 附表1 p1與各模組的可靠度改變對系統可靠度影響 40 附表2 p2與各模組的可靠度改變對系統可靠度影響 41 附表3 p4與各模組的可靠度改變對系統可靠度影響 42[[note]]學號: 692520751, 學年度: 9