在匯流排網路上以可靠度為導向的程式配置模式輿求解方法

Abstract

分散式計算機系統(distributed-computer system) 的優點之一是它具有較高的系統 可靠度。系統可靠度決定于傳輸連盄線 (communication link) 的可靠度，處理機( processor)的可靠度，以及系統資源配置等等。在系統資源配置問題中，程式配置問 題(task assignment problem)是一個重要主題，所謂「程式配置問題」簡單的說就 是給定一個含有m 個模組(module)程式，欲在一有n 個處理機的分散式計算機系統上 執行，如何找到一個配置方式使得目標成本函數 (objective cost-function)最少。 目前已有一些解決「程式配置問題」的模式提出，其主要著眼於如何使傳輸及執行成 本最低，或執行時間最短；而關於系統可靠度方面的研究較少。本論文主要探討如何 在匯流排網路上將具的執行順序限制(prece-dence constraint)的程式模組做最佳配 置，使得系統可靠度最大。在本篇論文中我們將建立一個以可靠度為導向的程式配置 數學模式，在此模式中，我們假設傳輸連線可靠度及處理機可靠度是其回轉時間(tur naround time) 的一個指數函數(exponential function)。回轉時間包括累積執行時 間(accumative execution time)，模組間傳輸時間(inter-moudle communication t ime)以及因傳輪同步的等候時間(idle time)。同時我們也提出一個分枝與定限方法( branch-and-bound algorithm) 來求解這個問題。由計算機模擬結果顯示，我們提出 的方法相當有效。