在PMC模式下超立方體之g-good-neighbor條件式診斷能力

Abstract

在多處理器系統當中，為維持處理器在計算上的可靠度，處理器偵錯一直是很重要的議題。對於許多著名的連結網路，已經有相關的處理器偵錯之診斷能力的研究結果。 舉例而言，n維的超立方體(hypercubes)、n維的交叉立方體(crossed cubes)、n維的梅氏立方體(m□bius cubes)、n維的雙扭立方體(twisted cubes)之處理器偵錯之診斷能力皆為n。而n維的超立方體在PMC模式下條件式處理器偵錯之診斷能力為4(n-2)+1。在本文中我們將探討n維的超立方體在PMC模式下的g-good-neighbor條件式處理器偵錯之診斷能力，並証明其為2^g(n-g)+2^g-1，其中0 <= g <= n – 3。 在g-good-neighbor條件式下處理器偵錯之診斷能力為傳統的處理器偵錯之診斷能力的數倍。

Processor fault diagnosis plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. For example, hypercubes, crossed cubes, m\"{o}bius cubes, and twisted cubes of dimension $n$ all have diagnosability $n$. The conditional diagnosability of $n$-dimensional hypercube $Q_n$ is proved to be $4(n-2)+1$ under the PMC model. In this thesis, we study the $g$-good-neighbor conditional diagnosability of $Q_n$ under the PMC model and show that it is $2^g(n-g)+2^g-1$ for $0 \le g \le n-3$. The $g$-good-neighbor conditional diagnosability of $Q_n$ is several times larger than the classical diagnosability of $Q_n$.