交換網路的測試與容錯設計

Abstract

本篇論文中，提出了包含班樣網路，奇偶排序網路及雙調排序網路等 交換網路的測試 與容錯設計。針對此設計，這些網路先能被測試，如發 現障礙，然後加以復原。本篇論文中，吾人設計了兩個用以製造交換及排 序元件的非同步控制電路。也推導了三個測試樣本，足夠去檢測一個班樣 網路中所有單一定值障礙；四個測試樣本，有潛力去檢測一個奇偶排序網 路中除了造成高阻抗的障礙外所有單一定值障礙；和四個測試樣本，能夠 去檢測一個雙調排序網路中除了造成高阻抗的障礙外所有單一定值障礙。 吾人已展示用這些測試樣本去檢測輸入數目為16的網路。接著提出了一個 容錯織並加以分析。在正常的使用狀態下，也展示了用於容錯的額外硬體 僅降低了少許操作速率。 In this thesis, testing and fault-tolerant designs for switching networks including the banyan network, the odd-even sorting network and the bitonic sorting network are proposed. For the designs, the networks can be first tested and then recovered. In the thesis, two asynchronous control circuits are designed which are to be used to implement the switching and sorting elements. Three tests which are enough to detect all the single stuck-at faults in the banyan network, four tests which are potentially to be able to detect all the single stuck-at faults, except those faults which can cause high impedance in the odd-even sorting network and fours tests which are able to detect all the single stuck-at faults, except those faults which can cause high impedance in the bitonic sorting network, are derived. These tests are demonstrated to detect the faults for networks of the size N=16. Then fault tolerant schemes are proposed and analyzed. It is also shown that the added hardware to achieve fault-tolerance degraded a little on the speed performance of these networks in the normal operation.