氏名　角山　正博
学位の種類　工学博士
学位記番号　博乙第3号
学位授与の日付　平成2年3月26日
学位論文の題目　セル構造オートマトンモデルに基く耐故障性を有する並列処理システム
論文審査委員
　主査　助教授　内藤　祥雄
　副査　教授　増田　孝雄
　副査　教授　浅野　重初
　副査　教授　松田　勘一
　副査　助教授　江島　俊明

• 論文目次
• 論文要旨

［平成元（1988）年度博士論文題名一覧］ ［博士論文題名一覧］に戻る．

目次
第1章　緒論　p.1
1-1　本研究の目的と背景　p.1
1-2　従来の研究の概要　p.2
1-3　本研究の意義と応用　p.3
第2章　セル構造オートマトン　p.5
2-1　概要　p.5
2-2　定義　p.5
2-3　性質　p.13
2-4　まとめ　p.16
第3章　等距離定重み性を有するセル構造オートマトンモデル　p.17
3-1　概要　p.17
3-2　定義　p.18
3-3　重み関数の満たすべき条件　p.20
3-4　構成法　p.29
3-5　故障検出　p.34
3-6　まとめ　p.48
第4章　耐故障性を有する並列処理システム　p.50
4-1　概要　p.50
4-2　並列処理システムとセル構造オートマトンモデル　p.52
4-3　許容し得る故障処理要素の数　p.56
4-4　処理要素の接続　p.60
4-5　システムの再構成　p.64
4-6　まとめ　p.70
第5章　実現例　p.72
5-1　まえがき　p.72
5-2　実現例1（ソーテイングシステム）　p.73
5-2-1　概要　p.73
5-2-2　分割法に基づくソーテイングシステム　p.73
5-2-3　処理要素の接続　p.80
5-2-4　システムの構成　p.88
5-2-5　評価　p.89
5-3　実現例2（FFTシステム）　p.93
5-3-1　概要　p.93
5-3-2　完全シャフルに基づくFFTシステム　p.93
5-3-3　処理要素の接続及び再構成　p.96
5-3-4　システムの故障検出　p.104
5-3-5　システムの構成　p.118
5-3-6　評価　p.112
5-4　まとめ　p.125
第6章　結論　p.126
謝辞　p.130
参考文献　p.131

　大規模な実時間処理を行うシステムや画像処理システムあるいは高速推論マシンのような、大量のデータを高速に処理するディジタルシステムが広く求められている。このようなシステムは単一の処理装置（プロセッサ）を用いて実現することが困難であるため、多数の処理装置を用いた並列処理システムとして実現する必要がある。並列処理システムとしては、主としてスーパーコンピュータで用いられる配列演算のような同一種類の演算を繰り返し並列に実行するベクトルプロセッサや、FFTアルゴリズムに基づく処理を並列に実行するFFTプロセッサ及びアレイプロセッサ等がある。しかし大量のハードウエアを用いてシステムを実現する場合にはシステム中に故障の発生する確率が増大し、一度び故障が発生した場合にはシステムの性能が低下するだけでなく、特に実時間処理を行うシステムにおいては、人命に関わる誤動作や社会的に大きな影響を及ぼす場合も少なくない。このような事態を避けるためには、システム中に故障が生じた場合にも正しい動作をすることが保証される、耐故障性を有するシステムとして実現することが必要になる。
　このような耐故障性を有する並列処理システムの基本的な構想は概にいくつか発表されている。しかしこれらのシステムは、再構成を行うために複雑なアルゴリズムに基づく手続きを実行しなければならないため、処理を再会するまでに長時間を要するという問題点を有している。これは特に再構成を行っている間に入力されたデータが処理されないことになるため、実時間処理システムとして用いる場合に問題となる。
　本研究においては、内部に故障が発生した際に速やかにシステムを再構成し、処理を続行することが出来る並列処理システムの構成法について検討を行う。本研究では、内部の処理要素をセル構造オートマトンのセルとして、また並列処理システム全体をセル構造オートマトンとして捉え、このセル構造オートマトンをモデルとしてシステムを構成している。本稿ではまず本研究において必要なセル構造オートマトンの基礎を示すと共に、耐故障性を有する並列処理システムを構成する際に有用となる等距離定重み性を有する構造オートマトンが満たすべき条件を明らかにする。セル構造オートマトンの重み関数が本稿中に条件を満たすとき、この様相の集合は符合に準じて定義された距離及び重みに関して等距離定重み性を有する。またセル構造オートマトンの様相の集合が等距離定重み性を有するとき、様相中の誤りを検出しさらに訂正することが可能になる。次に許容し得る故障の数と共に誤りの検出訂正方法を示す。ここで示した方法に基づいて誤っているセルの位置を決定する場合には、状態集合中の要素の数をq、様相に関する法多項式を重み関数で除した商として得られる多項式の次数をmとするとき、「（qm-1）/2」以下の誤りであるならば、その位置を正しく決定できる。ついでセル構造オートマトンをモデルとする並列処理システムの構造法及び古書が発生した際の再構成法を示す。このシステムは処理要素部、接続部及び制御部の3つの大きな部分から成っており、処理要素部は与えられた命令に従って入力されたデータを処理すると共に、自身の内部に発生した故障の検出を行う。また接続部は制御部からの指令に基づいて定められた処理用要素同士を接続し、制御部は処理要素部からの故障検出信号によって処理要素の状態を変化させると共に接続部に指令を与えてシステムの再構成を行う。このようにして構成されるシステム中に故障が発生した際には、セル構造オートマトンの重み関数に基づいて定められた状態遷移関数に従って状態を変化させることにより、自立的に再構成を行うことが出来る。このためシステム内部に故障が発生した場合にも複雑な再構成アルゴリズムに基づく手続きを実行することなく、モデルとして用いたセル構造オートマトンの重み関数に基づく線形演算によって直ちに再構成を行い処理を再開することが可能となる。なおこのときに許容し得る故障した処理要素の数は、様相に対する法多項式を重み関数で除した結果得られる多項式の次数より1だけ少ない数となっている。ついで本稿で示した構成法に基づいて構成した並列処理システムとして、分割法に基づくソティングシステム及びFFTシステムの例を示す。これらはいずれも、ほぼ等しい量のハードウェアを有する二重系と比べてかなり高い信頼度を有することが示されている。
　本研究で提案したシステムは、再構成を短時間に実行することが出来るため、実時間処理を行う高い信頼度を必要とするシステムに適用することが可能である。またここで示した構成法に基づくシステムにおいては、システム中の処理要素の単一故障のみならず、多重故障が発生した場合にもシステムを再構成することによって処理を続行することが出来るため、高い信頼度を有するシステムを実現することが出来る。今後更に大規模なシステムを構成するために、多次元セル構造オートマトンをモデルとするシステムの構成法についても検討を行う必要がある。