分散式計算系統可靠度最佳化之研究

Abstract

分散式計算系統由於它的高可靠度，對計算機系統的設計尤其是可靠度最 佳化的問題愈來愈重要了,至於K 個點的可靠度最佳化的問題，甚少報告 做此方面的研究，至於K 個點的可靠度可定義為所有K 個點能連在一起的 機率。此篇論文對下面三個重要問題提出解決之道:此篇論文我們提出一 個新的可得到正確解的方法，此方法是用來解決在分散式計算系統選取最 佳化的K 個節點，在容量的限制下，而使這 K 個節點的可靠度達到最大, 此方法是以partial ordering relation為基礎，為了加速計算過程,我們 提出一些規則來減少不必要的可靠度計算。在大型分散式計算系統裡為了 減少計算時間，我們同時提出了一個啟發式演算式用來解決在分散式計算 系統裡選取最佳K 個節點且在容量的限制下，使這K 個節點的可靠度達到 最大。此演算法的第一部份是用來選取最佳化的K 個節點，第二部份的演 算法稱為K-tree disjoint reduction method是為了加速此演算法計算 K 個節點的可靠度,此啟發式演算法對於不同Topology的模擬結果可知我 們所提出的演算法對於計算大型分散式計算系統的可靠度較有效率。眾所 周知，在分散式計算系統資料的不同分佈，會影響系統可靠度，為了考慮 資料的分佈，我們也提出了一個較有效率的演算法稱為 HROFA (Heuristic Reliavility-Oriented File Assignment)，此演算法使用 Top-down簡化的方法，來化簡問題的空間，這些化簡方法可以有效的縮小 問題展開的空間，如此也就加快了計算可靠度的時間和空間。 the term of K-node Reliability(KNR) is define as the probability of all nodes in K(subset of all processing elements) are connected. This dissertation discusses:(1)The k- node reliability optimization for the distributed computer system with exact method.(2)To reduce the computational complexity for large distributed computer system, we also proposed a heuristic method for the K-node reliability optimization.(3)To propose an efficient technique for improving the reliability -oriented file assignment optimization that is to find the file distribution in a DCS such that system reliability is maximized. Three problems for system reliability optimization are presented. The first we propose an easily programmed exact method for obtaining the optimal set K of nodes in a distributed computer system in terms of maximizing K- node reliability subject to capacity constraints. The method is based on the partial ordering relation approach. To speed up the procedure, some rules are proposed to that can be skipped over. To reduce the execution time of the problem under large DCS, We also proposed a heuristic algorithn for obtaining the optimal set K of nodes in a DCS in terms of maximizing K-node reliability subject to capacity constraints. The 1st part of the heuristic algorithm selects an optimal set K of nodes that maximizes the K-node reliability in a DCS subject to the resource constraint. The 2nd part of the heuristic algorithm focus on a new approach by using K-tree disjoint reduction method to speed up the K-node reliability evaluation. Both execution time and space than exact and exhaustive method for a large DCS. The distribution of data files can affect the system reliability optimization in distributed computer systems. To consider the distribution of data files, we developed an efficient algorithm to improve the reliability-oriented file assignment optimization problem, which uses a careful reduction method to reduce the problem space.