ディペンダブルシステム学研究室では、ディペンダブルなシステム、すなわち、ユーザが信頼して使うことのできるシステムを提供するための様々な研究を行っています。その中でも力をいれているのは、分散アルゴリズム、LSI高信頼化設計、LSIテストです。ディペンダブルシステム学研究室では、今年度、それぞれの分野で新たな取り組みをしました。
もののインターネットであるIoT時代が到来し、インターネットをはじめとする分散システム、ICTの基盤であるLSIのディペンダビリティは益々重要となっています。ディペンダブルシステム学研究室では、高度な故障耐性を持つ分散アルゴリズム（分散システムのためのアルゴリズム）である自己安定アルゴリズムの研究に取り組みました。また、LSIのディペンダビリティ向上のためにも2つのテーマに新たに取り組みました。LSI高信頼化設計では、これまで取り組んでいたロジックの高信頼化設計に続き、メモリの高信頼化設計にも取り組みました。さらに、プロセステクノロジーの微細化により、益々複雑化するLSIテストの品質向上のために、テスト時の電源ノイズを考慮した高品質なテスト技術の開発にも取り組んでいます。
今年度、新たに取り組んだ3つのテーマを紹介します。
自己安定アルゴリズム
分散システム、コンピュータネットワークの大規模化は益々すすみ、システムの内に故障が発生するということを前提としたディペンダビリティの考え方が重要になっています。システム内に故障が発生した場合、システムの稼働を一旦中断してメンテナンスする手段と、稼働させたままシステムを安定化させる手段が考えられます。
自己安定アルゴリズムは、コンピュータネットワークで代表される分散システムのための故障耐性を持つアルゴリズムで、システムがどんな状態になってもシステムを稼働させたまま正当な状態までシステムを遷移させ安定させることが可能です。そのため、故障によりシステム内のいくつかのコンピュータが管理する変数の値が改ざんされ、システムがつじつまの合わない状態に陥っても、自己安定アルゴリズムはシステムを自力で正当な状態に戻すことが可能です。また、システムを構成するコンピュータや通信リンクの追加や離脱などによるトポロジー変化にも柔軟に対応する、システムの初期化が不要など様々なメリットを持つアルゴリズムです。
ディペンダブルシステム研究室では、今年度、この自己安定アルゴリズムの研究に新たに取り組みました。特に、コンピュータネットワークをグラフと捉え、グラフ理論の諸問題を解く自己安定アルゴリズムに取り組んでいます。グラフ理論とは、複数の「ノード」と「ノード」と「ノード」との関係をグラフというデータ構造で表して考える様々な応用を持つ理論です。例えば、鉄道の路線図、電気回路・電子回路の回路図、SNSでの友達関係などもグラフで表現できます。
自己安定アルゴリズムに関する今年度一番の成果は、「匿名ネットワークで１−極大マッチングアルゴリズムを解くサイレントな自己安定アルゴリズム」です。
タイトルを説明するにはたくさんの概念を説明する必要があるので、思い切って省略しますが、マッチングとはノードのペアを作ることで、ペア数をなるべく多く作ることを目標とするアルゴリズムです。例えば、男女のカップルをたくさん作るという問題などを連想するとよいかもしれません。
この問題に関して、「匿名」、「１−極大」、「サイレント」、書いていませんが「集中型デーモン」、「木・リング」などの問題設定の下で、既存のアルゴリズムはO(n4)ムーブという性能だったのを、私たちが提案したアルゴリズムではO(n)ムーブに改善しました。ムーブというのは、１ノードが周りのノードの状態を見て、自分の状態を遷移させる動作です。提案するアルゴリズムは、このムーブをノード数nに比例する回数行えば、どんなシステム状態からでも１−極大マッチングというマッチング数が多い状態に遷移することを保証します。アルゴリズムの実行例を図１に示します。各ノードは、自身とリンクでつながっている隣接ノードの状態だけから、どのノードを誘うか、どのノードとペアになるかを決定し、これを繰り返すと、システム全体がいずれ「１−極大マッチング」状態に到達します。自己安定アルゴリズムの面白いところは、各ノードがローカル情報だけで状態遷移を行うにもかかわらず、システム全体がグローバルに安定するところです。
自己安定アルゴリズムの研究は、各ノードの振る舞いを記述するアルゴリズムを考案し、それがどんな場合でも期待通りに動くことを証明し、その性能を数学的に解析する計算理論と呼ばれる分野の研究です。数学的なモデル上でエレガントなアルゴリズムを理論的に解析して楽しんでいます。
研究成果は、International Workshop on Algorithms and Computation (WALCOM2015) で発表しました。
組み込みメモリの高信頼化
メモリとロジックを混載するシステムオンチップ(SoC)内の組み込みメモリのサイズや集積度が大きくなっており、メモリの故障、エラーがSoCの歩留まり、信頼性に大きく影響します。ここで、故障とはメモリ内部に起きたハードウェア的な欠陥を意味し、エラーとはメモリが誤った値を出力することを意味します。エラーには、故障が原因となるハードエラーと、アルファ線などがメモリセルに衝突しセルの値が反転するといったメモリ外部の要因によるソフトエラーとがあります。ソフトエラーを訂正するために、ECC(誤り訂正符号、Error Correcting Code)やScrubbingという手法が用いられています。Scrubbingとは、メモリに格納された値を読み出し、ECCを用いてエラーを訂正した値を再度書き込みメモリからエラーを消去する手法です。
ここで、ECCと１ワード中のエラー数との関係を考えてみましょう。図2では、ECCは１ワード中の１エラーのみ訂正可能とします。このとき、１ワード中にエラーが１個であれば、ソフトエラーでもハードエラーでも訂正可能です。ソフトエラーの場合は、新しい値を上書きする（overwrite）、またはscrubbingによりメモリの値は正しい値になります。一方、ハードエラーの場合、上書きやscrubbingでもエラーが残ることがあるため、同じワードに新たにエラーが起これば、誤り訂正ができなくなってしまいます。
そのため、故障対策としては別の手段として、冗長回路を用いたメモリの修復が考えられています。オンラインメモリ修復として、リマップCAM (Content Addressable Memory, 連想メモリ)を用いた手法が提案されています。この手法は、故障セルを含むワードを正常なスペアワードに置き換えるためにアドレスをメモリ内部で置き換える手法です。
ディペンダブルシステム学研究室では、今年度、ECC, Scrubbingによる誤り訂正とリマップCAMを用いたオンライン修復を組み合わせ、メモリの寿命を延ばす手法の提案に取り組みました。提案手法では、稼働中のシステムに組み込まれたメモリに対し、セルフテスト（BIST, Built-In Self-Test）を定期的に行い、リマップCAMの再構成を行います（図３）。このとき、ワード中のエラー数に応じて優先度を設けて、修復対象となるワードを決定します。図3中のDiagnosis CAM は、BISTの結果を集約し同一ワード内のエラー数を特定するために用いられます。
図4は、提案法と既存法とでメモリの信頼性を評価した結果です。ここで、既存法とは誤り訂正不可能となったワードのみを修復する手法です。信頼性とは時間の関数で、その時間までシステムが正常に稼働する確率を表す指標であう。信頼性の評価は、ソフトエラー、ハードエラーがポワソン分布に従って発生すると仮定して行いました。評価の結果、提案法では信頼性の高い期間が長く、従来法と比較してメモリの寿命が延びていることが確認できました。
研究成果は、IEEE Workshop on RTL and High Level Testing (WRTLT2014)で発表し、IEEE European Test Symposium（ETS2015）でも発表します。
LSIテスト時の電源ノイズの低減
LSIテスト時の過度の電源ノイズによる誤判定が問題になっています。LSIの良・不良を選別するテストによって正しい判定ができないと、不良品の市場流出や、良品の破棄に繋がってしまうため、テストには高い品質が求められています。本研究ではテスト時の電源ノイズを低減するため、テスト時の最適クロック周波数選択手法を提案しました。
LSIのテストでは、テスタ上のLSIにテストパタンと呼ばれる入力信号を印加し、その応答がシミュレーションで求めた正常応答と一致するかどうかで良否の判定をします。全てのテストパタンで応答が一致したものだけが良品として出荷され、不一致が起こったものは破棄されるか、原因の解析がなされます。ここで、テストの結果が必ず正しいとは限らないことに注意しなければなりません。印加するテストパタンや、テスト時の温度・電圧によっては、誤った判定を下してしまうおそれがあります。欠陥のあるLSIを良品と判定してしまうと（アンダーテスト）、不良品をユーザに販売することになり、使用中の誤動作による事故や、メーカとしての信頼の損失に繋がります。反対に、機能的に問題のない回路を不良品と判定してしまうと（オーバーテスト）、歩留り（良品率）を低下させてしまい、コスト高に繋がります。このように、テストの誤判定は様々な問題を引き起こすため、正しく良否を判定することが求められます。
その一方で近年、LSIテスト時の過度の電源ノイズによる誤判定の問題が深刻になっています。テストでは短時間に回路の隅々まで検査をしたいという要求から、通常起こり得ないような状態遷移を発生させます。これにより回路の動作率が高くなり、消費電流は通常動作時の数倍にもなります。消費電流が大きくなると回路の電源電圧が過剰に低下し、トランジスタが動作しなかったり、信号の伝搬遅延が増加したりします。その結果、回路は誤動作を引き起こし、オーバーテストをもたらします。
電源ノイズは大きく、IRノイズ、Ldi/dtノイズ、共振ノイズに分類されます。IRノイズは、回路中の抵抗成分(R)とそこに流れる電流(I)によって起こる電圧降下を指します。また、Ldi/dtノイズは回路中のインダクタンス成分（L)と電流の変化(di/dt) によって起こる電圧降下を指します。そして本研究で対象とする共振ノイズは、回路中のインダクタンス成分(L) とキャパシタンス成分(C) が構成するLC 回路の共振現象によって起こる、電源電圧の変動を指します。この変動は共振周波数1/(2π√LC)の電流によって励起され、回路の抵抗が小さい場合、減衰しながら数クロックサイクルにわたって振動を続けます。
さらに、共振ノイズは電流が変化するたびに発生し、最終的な電圧変動量は発生した共振ノイズ波形の重ね合わせとなる特徴があります。したがって、印加するテストパタンとその時のクロック周波数により、共振ノイズの影響は変動します。我々はこの点に着目し、与えられたテストパタンに応じて最適なクロック周波数を決めてやれば、共振の影響を低減できると考えました。提案手法はSPICEなどの回路シミュレータを用いることなく電圧変動を計算でき、共振ノイズの少ないクロック周波数を高速に求めることができます。ベンチマーク回路を用いた実験では、提案手法によって選択された周波数によって、最悪時のノイズを50％以上低減しました。また、計算時間は商用回路シミュレータの約1800倍を実現しました。今後は電源回路モデルの詳細化によって、提案手法の精度を向上していく予定です。
ディペンダブルシステム学研究室が今年度新たに取り組んだ、自己安定アルゴリズム、組み込みメモリの高信頼化、LSIテスト時の電源ノイズの低減を紹介しました。研究室の詳しい情報は、研究室HPもご覧ください。