システム LSI 搭載 FPGA-IP コア向け物理故障検出及び回避手法 *

システム _LSI 搭載 _FPGA-IP コア向け物理故障検出及び回避手法 _*

尼崎 太樹

^†a)

西谷 祐樹

^†

井上 万輝

^†

飯田 全広

^†

久我 守弘

^†

末吉 敏則

^†

A Novel Detection and Recovery Techniques for Physical Defect in FPGA-IP Cores

^∗

Motoki AMAGASAKI

^†a)

, Yuki NISHITANI

^†

, Kazuki INOUE

^†

, Masahiro IIDA

^†

, Morihiro KUGA

^†

, and Toshinori SUEYOSHI

^†

あらまし FPGAは物理故障が発生しても他の領域に回路を再構成することで継続使用が可能である．しか し，故障のない領域に回路を実装するには故障箇所の特定と故障箇所を避けて再構成する時間が必要になる．そ こで本論文では故障箇所特定及び回避にかかる時間の削減を目的に，効率の良い故障診断手法，及び再構成によ る故障回避手法を提案する．故障診断手法では我々の先行研究で提案されている出荷テスト手法に追加経路を加 え故障箇所を特定する．また回避手法では再構成によりタイルレベル及びマルチプレクサレベルで故障回避を行 う．システムLSIに搭載するFPGA-IPコアを対象に評価を行ったところ，配線部に存在する故障に対し完全な 故障箇所特定及び回避を行えることがわかった．

キーワード 故障診断，故障回避，耐故障性技術，FPGA

1.

^{ま え が き}

車載機器や医療機器などの信頼性を必要とするシス テムにおいて耐故障性は重要である．そのため従来 システムの多くではハードウェアの冗長化により信頼 性を保持している．しかしながら，この方法では消費 電力，面積，遅延が大きな課題となる．これに対し，

FPGA

（

Field Prgrammable Gate Array

）ではプロ グラマブルな特徴を利用することで，従来の冗長化に よる問題を緩和した耐故障性の実現が期待できる．特 に

FPGA

を

IP

（

Intellectual Property

）コアとして システム

LSI

に搭載する際，実装面積の制約が非常に 大きいため，この手法は有効な選択肢の一つとなる．

図

1

に示すように回路実装領域内で故障が発生した場 合，故障箇所を避ける形で再構成することで継続動作 が可能になる．このため

FPGA-IP

コア内部に故障が 存在するチップでも早急に交換する必要がない．これ

†熊本大学大学院自然科学研究科，熊本市

Department of Computer Science and Electrical Engineer- ing, Graduate School of Science and Technology, Kumamoto University, Kumamoto-shi, 860–8555 Japan

a) E-mail: [email protected]

*本論文はFIT2012推薦論文である．

は医療機器や遠隔地などのチップ交換が容易でない環 境下で特に有効である．

ここで継続動作を目的とした場合，可能な限り短時 間で故障箇所の特定が行われなければならない．また，

回避による復旧時間増加と性能低下を抑えるために高 い故障診断能力が求められる．ここで故障診断，故障 回避，回路性能に関し，

FPGA

を構成する回路リソー スを

3

種類の分解能（粒度）で考える．ここでは粒度 が粗い方から（

A

）タイルレベル，（

B

）ブロックレベ ル，（

C

）マルチプレクサ（

MUX; Multiplexer

）レベ

図1 再構成を用いた耐故障性技術

Fig. 1 Fault tolerance using FPGA reconfiguration.

図2 故障を扱う粒度間の関係 Fig. 2 Relationship of between the three types

granularity.

ルとする．

（

1

）．タイルレベル：タイルは

LB

（

Logic Block

），

SB

（

Switch Block

）及び

CB

（

Connection Block

）から 構成される．図

2 (a)

に示すように

FPGA

はタイルを アレイ状に並べた形状をとり，タイルレベルで故障を 扱う場合分解能は最も低い．

（

2

）．ブロックレベル：図

2 (b)

に示すように

LB

，

SB

，

CB

で故障を取り扱う場合をブロックレベルとする．

分解能としてはタイルレベルとマルチプレクサレベル の中間に位置する．

（

3

）．

MUX

レベル：図

2 (c)

のように各ブロックは

MUX

（スイッチ）の集合体で構成される．マルチプ レクサ単位で故障を扱うため分解能は最も高い．

故障箇所特定に要する時間は分解能の関係よりタイ ルレベルが最も短く，マルチプレクサレベルが最も長 い．故障回避時間に関してはタイルレベルは再配置配 線が必要になるため，多くの回避時間が必要かつ性能 低下も大きい．一方で

MUX

レベルでは回避対象が故 障

MUX

上の配線のみであるため，その他の配線は動 かす必要がない．すなわち故障

MUX

上を通る信号の みを再配線するインクリメンタル配線で十分な場合が ほとんどのため，回避時間及び性能劣化を最小限に抑 えることができる．

そこで本論文では，故障特定時間の削減及び高い診 断分解能の実現を目的とした故障診断手法を提案する．

システム

LSI

に搭載する

FPGA-IP

コアを対象とし，

故障診断時間，回避時間及び回路性能に関して議論し ていく．故障モデルは縮退故障とし，故障箇所として 特にテストが困難とされる配線部をターゲットとする．

故障診断は我々が提案している手法

[1]

をベースに別 途テストパターンを追加することで行う．また，故障 回避においてはトロント大

VPR [2]

を改良する形で

タイルレベル及び

MUX

レベルの故障回避に対応した ツール開発を行う．

FPGA-IP

コアではディスクリー ト型の

FPGA

と異なり，設計対象に応じて様々な回 路規模が存在する．このため，これらのサイズに応じ たスケーラブルな手法とすることが重要である．

以下，

2.

では関連研究について述べる．

3.

では先行 研究のテスト容易な配線構造及びテスト手法について 説明する．

4.

では提案する故障診断手法について述べ る．

5.

^では

MUX

の故障回避をするために配置配線 アルゴリズムについて詳述する．

6.

にて提案する故障 診断及び回避手法を評価し議論を行う．最後に

7.

で 本論文をまとめる．

2.

^{関 連 研 究}

FPGA

の故障診断及び回避に関する研究は

2

種類 に大別できる

[3]

．第一にハードウェアベースで故障を 取り扱う場合である．この場合，回路退避用のスペア 領域としてにあらかじめ冗長なハードウェアリソース が用意されている

[4]

〜

[7]

．これらの手法ではタイル レベルまたはブロックレベルでの故障診断・回避を行 う．ひとたび故障が検出されるとハードウェアで故障 回避を行うため回避時間は早い．しかしながら，ハー ドウェア上の回避機構に依存するため回避の柔軟性は 低く，代替領域を用意するため回路規模が大きくなる のが欠点である．

第二に

CAD

ベースで故障を取り扱う場合である．

故障箇所を特定した後，当該箇所を避ける形で実装回 路のコンフィグレーションデータを作成する．この手 法では故障箇所以外のハードウェアリソースが使用で きるため

MUX

レベルの故障診断が採用されることが 多い．そのため故障回避に対する柔軟性が高く，配置 配線で対応できる限りの故障を取り扱うことができる．

一方で

CAD

ベース手法では再配置または再配線を行 う必要があるため，一定のアプリケーション停止時間 が許容できない場合は問題となる．

[8]

では，論理クラ スタ内には未使用

LUT

が高確率で存在するという前 提で，故障

LUT

に実装された回路を未使用の

LUT

に移動するという方法を提案している．

LUT

の故障 回避としては最も素直な方法ではあるが，故障診断方 法，配線部の故障，回避後の性能に関しては言及され ていない．

このように故障診断と回避は扱う粒度に応じて様々 なトレードオフが存在する．本論文では

CAD

を用い た故障診断・回避を対象とし，性能劣化を抑え短時間

に復旧可能な手法を提案する．

3.

^{先 行 研 究}

本研究は対象とする

FPGA-IP

コアとして先行研究 で提案したアーキテクチャ

[1]

を用いる．このアーキ テクチャは出荷テストの歩留まり向上を目的としてテ スト容易化設計したものである．本章ではテスト容易 な配線構造を示し，

SB

レベルの故障検出手法につい て説明する．

3. 1

テスト容易な配線構造

従来のアイランド型

FPGA

は高いプログラマビリ ティを実現するため構造が複雑である．特に配線部は構 成メモリで経路を決定するため，出荷テスト用のパタ ン生成に使われる

ATPG

（

Automatic Test Pattern Generator

）が直接利用できない．これより我々は図

3

に示すテスト容易な

FPGA

としてホモジニアスアー キテクチャ

[1]

を提案している．従来のアイランドス タイル

FPGA

は複数のタイル構造から構成されるの に対し，このアーキテクチャは単一のタイルから構成 される．加えて，配線部の接続を単純化するためにア ライナーを実装する．更に，効率良くテストを行うた めに図

4

に示すようなテストパターン生成回路である

TPG

（

Test Pattern Generator

）と出力結果比較す る

ORA

（

Output Response Analyzer

）を

IOB

内に 備えている．また，テスト時間短縮のため行単位で搭 載回路の構成情報をシフトするシフトコンフィグレー ション機構をもつ．

3. 2 SB

に対するテストパターン

故障検出のための構成パターンは

Wilton

タイプ

SB [9]

の規則性を利用し生成する．

Wilton

タイプ

SB

の経路は（

a

）直線，（

b

）時計回り，（

c

）反時計回りの

3

種類に分類できる（図

5

）．例えば，時計回り経路

図3 ホモジニアスな配線構造

Fig. 3 Completely homogeneous tile architecture.

になるよう全ての

SB

をコンフィグレーションした場 合，その経路は基本的に閉経路として構成される．た だし，

FPGA

アレイの外側に位置する

SB

を通る経路 は

IOB

にて遮断される場合もある．閉回路上の

SB

で は始点，終点となる

LB

を

TPG

，

ORA

にコンフィグ レーションする（図

6

）．

TPG

から出力した論理値が アレイ内の

SB

を通り，

ORA

内の

FF

に格納される．

ORA

で格納された論理と

TPG

が生成した論理の一 致が確認できれば，対象経路上には縮退故障がないこ

図4 IOB内のテスト機構 Fig. 4 IOB structure for testing.

図5 SBに対するコンフィグレーションパターン Fig. 5 Three types of SB configuration.

図6 時計回り経路のコンフィグレーション Fig. 6 Configuration for clockwise paths.

とが確認できる．また，閉路とならない場合は

IOB

内 の

TPG

，

ORA

を用いて故障の検査を行う．

ORA

内 の

FF

値はスキャンパスを通すことで観測可能である．

ここでの最大の特徴は全経路を独立にテストできるこ とである．図

6

に時計回りのコンフィグレーション経 路例を示す．破線は

SB

上の経路を表し，代表経路を 実線で示している．図に示すように一つの

SB

を通る 経路は互いに干渉しないため，全ての時計回り経路を 同時に検査可能である．このことは反時計回り，直線 経路に関しても同様である．

また，時計回りと反時計回り経路に関しては，閉路 を

TPG

，

ORA

で切断するため，切断された経路を 検査するためのテスト経路がもう

1

種類づつ必要にな る．これは単純に閉路を切断した

LB

の位置を変えて 同様の（時計回り若しくは反時計回り）経路で検査を 行えばよい．以上より，直線経路

1

種類，時計回り経 路

2

種類，反時計回り経路

2

種類の合計

5

種類の故障 検出経路のコンフィグレーションが必要となる．この

5

種類の経路にて検査を行うことで，

FPGA

配線上の 故障を

100%

検出可能である．ただし，これはあくま で選別テストを対象としているため，故障箇所の特定 まではできない．

4.

^{故 障 診 断}

3. 2

で述べた

5

種類の配線経路を用いた出荷テスト 手法では

FPGA-IP

コア内の故障の有無しかわからな い．そこで故障箇所を特定するために，新規にテスト パターンを追加する．

4. 1

提案診断手法

先行研究のコンフィグレーションでは

SB

レベルの

図7 MUX型のORA.

Fig. 7 Modified output response analyzer.

図8 故障箇所の特定手法

Fig. 8 Combining the paths to specify the faulty point.

故障検出を行った．しかしながら，図

8 (a)

のように 複数の

SB

が故障候補として出現し，故障箇所の特定 まではできない．更に，回避時には故障候補となる全 ての

SB

が使用できない．そこで図

8 (b)

に示すよう に新たなテスト経路で故障診断を行う．続いて図

8 (c)

及び図

8 (d)

に示すように両方の検出結果から重複す る箇所を探索し，タイルレベルまたは

MUX

レベルで 故障箇所の特定を行う．なお，テスト支援回路として 前章で述べた

TPG

と

ORA

を用いる．

ORA

に関し ては診断精度向上のため，従来の

EXOR

タイプから 図

7

のような

MUX

タイプへ変更を行う．なお，信号

Sel

はチップ外部より入力される制御信号で各

ORA

に共通して入力される．

4. 2

故障診断用の経路

故障箇所の特定を行うために，新たに

2

種類のテス ト経路を用意する．一つ目は図

9 (a)

に示すように右 斜め経路と直線経路を組合わせたものである．二つ目

図9 SBに対する追加のコンフィグレーションパターン Fig. 9 Additional SB configuration.

図10 直線・右斜め経路のテストパターン Fig. 10 Test pattern for right-up and orthogonal

paths.

は図

9 (b)

に示すように左斜め経路と直線経路を組合 わせたものである．図

10

に図

9 (a)

で構成された経 路の例を示す．破線部がそれぞれの

SB

のコンフィグ レーションパターンを表している．このパターンでは 閉路は存在しないため，

IOB

内の

TPG

と

ORA

を利 用する．例として実線で示されるパスに注目すると，

IOB

内の

TPG

から出力された信号が実線部を通り同 じく

IOB

内の

ORA

に格納される．これらの経路は 互いに交わらないため，破線部の経路全てを同時にテ ストできる．直線・左斜め経路のテストパターンに関 しても同様の方法で故障診断を行う．

また，図

10

の経路に対し行単位で直線経路と右斜 め経路を入れ替えた場合を図

11

に示す．行単位で

SB

のコンフィグレーション情報を入れ替えることで，全

図11 シフトコンフィグレーションしたテストパターン Fig. 11 Shifted test pattern.

図12 コンフィグレーションパスの構成 Fig. 12 Structure of configuration path.

てのタイルは直線，斜めのテストを行うことができ る．行単位での回路構成変更において

SB

のコンフィ グレーション時間削減のため，シフトコンフィグレー ション機能

[1]

を用いる．シフトコンフィグレーショ ンとはアレイ

1

行分の再構成をシフト動作により実行 することである．これらは図

12

に示すように，コン フィグレーションパスをシフトレジスタで構成し，行 単位で制御可能にしている．この機能を用いることで 図

10

の経路を図

11

の経路に容易に変更できる．こ のように，追加経路とシフトコンフィグレーション機

能を組み合わせることにより短時間で故障診断能力を 改善できる．また，図

9 (b)

に関しても同様の方法で テスト可能である．

また，これらの経路は直線経路を包含しているため 図

5

の直線経路を独立して実行する必要がない．こ れより，時計回り経路

2

種類，反時計回り経路

2

種 類，直線・右斜め経路

1

種類，直線・左斜め経路

1

種 類の合計

6

種類のテスト経路で故障特定を行う．なお，

これらの経路は

SB

上の全ての配線経路を必ず重複し て通るため，故障

SB

の位置特定が

100%

可能である．

故障

SB

が特定されるため故障タイルも特定でき，故 障している配線も特定できるため故障

MUX

も特定で きる．すなわち，本手法ではタイルレベル，ブロック レベル，

MUX

レベルでの故障特定が可能である．

4. 3

故障診断に必要なサイクル数

故障診断に必要な時間

T

detect

[cycle]

は全体をコン フィグレーションする回数

N

f ullとシフトコンフィグ レーションする回数

N

shif tにより決定される．

T

detect

= T

f ull

· N

f ull

+ T

shif t

· N

shif t

(1)

なお，先行研究

[1]

では

5

種類の経路でテストを行う

ため

N

f ull

= 5

である．また，提案手法では

SB

に対

し

6

種類の経路でテストを行うため

N

f ull

= 6

とな る．加えて，直線・右回り経路と直線・左まわり経路 では

1

回づつシフトコンフィグレーションを行うため

N

shif t

= 2

である．

Wilton

タイプの

SB

を用いる限

り，任意の

FPGA-IP

コアのアレイサイズに対して上 記パラメータは不変である．

T

f ullは全体再構成，及 びスキャンパスにより結果を引出すのに要する時間で あり次式で表現される．

T

f ull

= CF

array

+ CF

iob

+ T

scan

(2)

CF

arrayは

FPGA

アレイ全体の構成メモリ数，

CF

iob

は

IOB

全体の構成メモリ数である．ここで

FPGA

ア レイサイズを

N

array x

×N

array yと表記し，

N

array x

は行方向のタイル数，

N

array yはカラム方向のタイル 数とする．これより

FPGA

アレイを構成する総タイ ル数

T N

tileは次式で算出される．

T N

tile

= N

array x

· N

array y

(3) T

scanは

FPGA-IP

コアのスキャンに要する時間を表 し，

N

f f lb と

N

f f iobを

LB

と

IOB 1

個あたりの

FF

数とすると次式で表現される．

T

scan

= T N

tile

· N

f f lb

+ 2( N

array x

+ N

array y

)

· N

f f iob

(4)

シフトコンフィグレーションに必要なサイクル数は次 式で表される．

T

shif t

= CF

array

N

array x

+ CF

iob

2( N

array y

+ N

array y

)

+ T

scan

(5)

また，

LB

，

CB

，

SB1

個あたりの構成メモリ数をそれ ぞれ

CF

lb，

CF

cb

, CF

sbとすると

FPGA

アレイ全体 の構成メモリ数は以下のようになる．

CF

array

= ( CF

lb

+ CF

cb

+ CF

sb

) · T N

tile

(6)

ここで配線チャネル幅

W

に対し，シングルライン，

クアッドラインの比率を

α

^対

(1 − α )

とすると，

SB1

個当たりの構成メモリ数

CF

sbは次式になる．

CF

sb

= CF

mux sb

· W 2 {1 − 3

4 (1 − α)} · 4 (7)

ここで

CF

mux sbは

SB

中の

MUX

スイッチ

1

個に

要する構成メモリ数を指す．係数^W₂ は単方向配線の ためである．また，クアッドラインの

4

分の

3

は当 該

SB

には入力されないためその本数を引き，最後に 上下左右の出力を考慮して

4

をかけている．例えば

CF

mux sb

= 3

ビット，シングルライン

:

クアッドライ

ン

= 1:5

の場合，

CF

sb

=

^9W₄ となる．これよりチャ ネル幅が全体のテスト時間に与える影響は

O(W )

で ある．

5.

^{故 障 回 避}

前章で故障診断した故障を回避するため，配置配線 ツール

VPR5.0 [2]

に故障回避機能を追加する．

5. 1

配 置

タイルレベルで診断した場合，故障タイル内の

LB

を使用することができない．そのため配置工程で故 障

LB

を回避する必要がある．そこで

VPR

の配置フ ローを図

13 (a)

に示すように変更する．破線部分が故 障判定に関する部分で，故障診断によりあらかじめ故 障タイルの座標情報をもつものとする．

VPR

では焼 きなまし法を用いているため，初期配置や

LB

の交換 の際に故障タイルを除外する機能を追加する．本アル ゴリズムの疑似コードを図

14

に示す．

5

行目では初 期配置で故障ブロックが選択された場合，故障ブロッ ク以外を選択するまで初期配置をやり直す．また，

14

行目ではブロック移動先として故障ブロックが選択さ れた場合，故障ブロック以外を選択するまで配置をや

図13 再配置及び再配線フロー Fig. 13 Re placement and routing flow.

図14 配置による故障回避の疑似コード Fig. 14 Pseudo-code in fault avoidable placement.

り直す．

5. 2

配 線

タイルレベルと

MUX

レベルの回避において，配線 時に必要となる配線リソースグラフから故障経路を除 く必要がある．そこで

VPR

の配線フローを図

13 (b)

に示すように変更する．破線部分が故障判定に関す る部分で，配置と同様にあらかじめ故障タイルの座 標情報をもつものとする．回避による性能劣化を防 ぐため，全体を再度配線するのではなく，故障箇所に 該当する経路のみを変更するインクリメンタル配線 を行う．そのため，

VPR

の配線アルゴリズムである

pathfinder [10]

の変更を行う．本アルゴリズムの疑似 コードを図

15

に示す．

21

行目に選択したノードが故

図15 配線による故障回避の疑似コード Fig. 15 Pseudo-code in fault avoidable routing.

障しているかどうか判定処理を追加する．仮に故障配 線を

pathfinder

が選択した場合，その時点で配線処 理を失敗とし，そのほかの経路に対し配線を行う．

6.

^{評 価}

故障診断及び回避に関して先行研究

[1]

と提案手法 の比較を行う．本評価ではタイルレベルと

MUX

レベ ルを対象とする．続いて，故障回避に対応させた配置 配線ツールを用いて故障回避後の回路性能及び復旧時 間の評価を行う．最後に，テスト時間，性能及び復旧 時間におけるトレードオフについて議論していく．

6. 1

評 価 条 件

表

1

に評価対象のアーキテクチャ情報を示す．評 価に用いる

FPGA-IP

コアはアレイサイズ

16 × 16

の ホモジニアスアーキテクチャである．論理ブロック中 に搭載される

LUT

数を論理クラスタサイズと定義 し，ここでは

4

とする．本評価では

65nmCMOS

ス タンダードセルライブラリを用いて

Synopsys Design CompilerY-2006.06-SP6-2

で合成した値をデバイス パラメータとして使用する．想定する故障モデルは縮 退故障とし，

Cadence NC-Verilog06.20-s004

にてト グルカバレッジを観測した値を故障特定率として扱う．

本評価において配線部の任意の箇所に最大

5

個の 故障を発生させる．それぞれの故障個数に基づきラン ダムに配置された

1,000

パタンの故障に対し故障診断 を行う．また，回路性能を評価するために

MCNC

ベ

表1 アーキテクチャパラメータ Table 1 Architecture parameter.

項目 値

アレイサイズ 16×16

論理セル 6-LUT

論理クラスタサイズ 4

LBの入力ピン数 12

SBの構成 Wilton (Fs = 3)

CBの構成 normal (Fc = 0.5)

single line数 8/channel

quad line数 40/channel

I/Oピン数 128

コンフィグレーションビット数 136,896

ンチマーク回路

[11]

に対し，

ABC mapper [12]

，

T- VPack [10]

及び回避機能を追加した配置配線ツール を用いて評価する．シミュレーションに用いる計算機 のスペックは

Intel Xeon X5680 3.30GHz

のプロセッ サとメモリ

48GBytes

である．

6. 2

故 障 診 断

表

2

に一つの故障に対する診断結果を示す．故障診 断能力はテスト経路と

ORA

に集まるテスト経路に依 存するため最良値と最悪値をそれぞれ示す．先行研究 のテスト手法

[1]

では

3. 2

^で示した

5

種類のテスト回 路を全体再構成する必要があるため，

FPGA-IP

コア 全体の再構成回数は

5

（

N

f

ull = 5

）である．また，こ の際に要するクロックサイクル数は

798,992

で，その 内訳は全体再構成に

786,245

サイクル（

98.4%

），ス キャンに

11,528

サイクル（

1.4%

），その他の制御動作 に

1,219

サイクル（

0.2%

）となる．ただし，この手法 は元来チップ内の故障の有無だけを特定するものであ る．このため，故障箇所の検出能力はタイルレベルで 最良値が

4

個，最悪値では

44

個と低い．一方，提案手 法では

4. 2

^で示した

6

種類のテスト回路を全体再構成 及び

2

回のシフトコンフィグレーションが必要なため，

FPGA-IP

コア全体の再構成回数は

6

（

N

f ull

= 5

），

シフトコンフィグレーション回数は

2

（

N

shif t

= 2

） である．また，この際に要するクロックサイクル数は

975,278

で，その内訳は全体再構成に

943,494

サイク ル（

96.7%

），シフトコンフィグレーションに

19,010

サ イクル（

1.9%

），スキャンに

11,528

サイクル（

1.2%

）， その他の制御動作に

1,246

サイクル（

0.1%

）となる．

テスト時間は

22.0%

増加するものの，タイルレベル，

MUX

レベルの両方で故障箇所を完全に特定できる．

続いて，最大

5

か所の故障を発生させた場合の故障 診断結果を表

3

と表

4

に示す．ここでは想定した故 障位置と故障数に基づき，

1,000

回試行を行った際の

表2 故障診断結果 Table 2 Result of fault detection.

先行研究[1] 提案手法

FPGA-IPコアの全体再構成回数 5 6

シフトコンフィグレーション回数 – 2 テスト時間(サイクル数) 798,992 975,278 テスト時間の増加率 – +22.0%

故障候補タイル数(最悪値) 45 1 故障候補タイル数(最良値) 4 1

故障候補MUX数(最悪値) 144 1

故障候補MUX数(最良値) 12 1

表3 検出箇所の候補数（先行研究）

Table 3 Candidates of detected faulty points (Previous).

# of defects tile level mux level best worst ave. best worst ave.

1 9 45 23.5 24 144 57.6

2 13 88 40.5 46 288 123.7

3 23 110 54.1 85 324 168.9

4 35 167 83.0 123 564 247.6

5 83 183 94.8 157 642 290.2

表4 検出箇所の候補数（提案手法）

Table 4 Candidates of detected faulty points (Proposed).

# of defects tile level mux level best worst ave. best worst ave.

1 1 1 1.0 1 1 1.0

2 2 2 2.0 2 2 2.0

3 3 3 3.0 3 3 3.0

4 4 4 4.0 4 4 4.0

5 5 5 5.0 5 5 5.0

最良値，最悪値，平均値を表している．例えば，五つ の故障が存在する場合，先行研究では平均してタイル レベルで

94.8

，

MUX

レベルで

290.2

個までしか特定 できない．一方で，提案手法では

6. 2

で述べたように タイルレベル，

MUX

レベルともに想定した複数の故 障箇所に対し，完全に故障位置を特定できることがわ かる．

6. 3

故 障 回 避

FPGA

アレイの任意の箇所に最大

5

個の故障を発生 させたものに対し，（

1

）先行研究の手法，（

2

）提案手法 の

2

種類で故障診断を行い，提案ツールで回避を行っ た．実装に用いた

MCNC

ベンチマーク回路は

5

種類 である．実装回路とは関係ない位置に故障がある場合 は故障箇所特定のみで回避を行う必要がないが，今回 の評価では故障箇所上に実装回路がある場合のみを想 定した．表

5

と表

6

にタイルレベルと

MUX

レベル で故障回避を行った場合のそれぞれのクリティカルパ ス遅延を示す．表の

1

カラム目は実装回路名，

2

カラ ム目は回避前の動作速度，

3

カラム目は埋め込んだ故

表5 タイルレベル故障回避後の動作速度(10サンプル) Table 5 Delays for tile-level avoidance (ten samples).

circuit delay[ns] # of Previous Propose (no faults) faults rate delay[ns] rate delay[ns]

C6288 96.7 1 7/10 99.9 10/10 95.9

2 1/10 99.4 10/10 94.8

3 0/10 N/A 10/10 94.1

4 0/10 N/A 10/10 96.1

5 0/10 N/A 10/10 95.5

cordic 103.4 1 6/10 108.2 10/10 100.8 2 0/10 126.0 10/10 102.0 3 0/10 N/A 10/10 104.0 4 0/10 N/A 10/10 104.0 5 0/10 N/A 10/10 108.0

ex4p 46.4 1 5/10 54.9 10/10 47.5

2 0/10 50.3 10/10 47.9

3 0/10 N/A 10/10 47.9

4 0/10 N/A 10/10 49.9

5 0/10 N/A 10/10 49.3

vg2 39.3 1 8/10 41.5 10/10 40.4

2 4/10 41.7 10/10 41.4 3 6/10 44.9 10/10 39.8 4 4/10 43.6 10/10 40.6

5 0/10 N/A 10/10 40.8

N/A: Implementation failed.

表6 MUXベル故障回避後の動作速度(10サンプル) Table 6 Delays for MUX-level avoidance (ten samples).

circuit delay[ns] # of Previous Propose (no faults) faults rate delay[ns] rate delay[ns]

C6288 96.7 1 10/10 97.2 10/10 96.7

2 9/10 97.5 10/10 96.9 3 9/10 97.6 10/10 96.7 4 8/10 98.8 10/10 96.5 5 0/10 N/A 10/10 96.7 cordic 103.4 1 10/10 99.8 10/10 97.5 2 9/10 98.7 10/10 95.9 3 9/10 99.6 10/10 94.3 4 8/10 109.0 10/10 100.0 5 0/10 N/A 10/10 98.8

ex4p 46.4 1 10/10 48.4 10/10 46.9

2 8/10 49.4 10/10 47.4 3 10/10 49.3 10/10 47.2 4 10/10 50.3 10/10 46.9 5 0/10 N/A 10/10 47.3

vg2 39.3 1 10/10 40.3 10/10 39.9

2 8/10 40.5 10/10 39.4 3 8/10 40.1 10/10 39.6 4 7/10 41.8 10/10 39.6 5 0/10 N/A 10/10 40.0 N/A: Implementation failed.

障数，

4

カラム目と

5

カラム目は先行研究と提案手法 での回避結果を示す．回路は初期配置を変更する形で

10

回試行したものを用いたため，

“rate”

は

10

回中の 回避成功回数，遅延はその平均値を表す．先行研究の タイルレベル回避ではほとんどの場合再配線に失敗し，

成功した場合でも約

10%

の性能低下がみられた．これ

図16 ベンチマークex4pの配線結果 Fig. 16 Result of the ex4p benchmark circuit.

表7 回避時間[sec]

Table 7 Avoidance time [s].

circuit Tile MUX

(re-place&routing) (re-routing only)

C6288 3.102 0.432

cordic 4.654 1.206

ex4p 4.148 0.495

vg2 1.437 0.177

はタイルの故障候補数が多いため，再配線時にリソー ス不足になったためである．一方，提案手法では故障 回避後の性能劣化は平均

2%

ほど存在するものの，全 パタンで回避が成功した．

MUX

レベルに関しては先 行研究の検出手法では故障回避数が向上し，性能低下 も約

2%

に抑えられた．提案手法に関してはタイルレ ベル同様に全てのパタンで回避が成功し，動作速度の 劣化もみられなかった．

図

16

にベンチマーク

ex4p

中に三つの故障がある 場合での配線結果を示す．

(a)

は先行研究の検出手法 を用いタイルレベルで回避を行った場合である．ここ では

45

種類の故障候補が存在したため配線リソース が不足し，故障回避に失敗している．

(b)

は同条件に て提案手法で故障診断及び回避を行った配線結果を示 す．ここでは故障したタイルを避ける形で配線が行わ れ，故障回避が成功している様子がわかる．

計算機を用いた場合の復旧時間を表

7

に示す．

MUX

レベルでの故障回避時間はタイルレベルよりも平均し て

84%

短い．これはタイルレベルの故障回避では再配 置配線が必要なのに対し，

MUX

レベルでは再配線の みで良いためである．

6. 4

考 察

先行研究での故障検出方法を用いた場合，タイルレ ベルと

MUX

レベルでは再配線の成功率が大きく異 なることがわかった．特にタイルレベルの故障回避で

図17 総タイル数，チャネル幅とテスト時間の関係 Fig. 17 Relationship of between total number of tiles

and channel width.

は多くのベンチマーク回路の実装に失敗した．これは タイルレベルで故障回避を行った場合，論理ブロック 内の全ての要素が使用できなくなったためだと考えら れる．一方，

MUX

レベルでは必要最低限の故障箇所 のみ回避を行うため，タイルレベルと比較して回避の 柔軟性も高い．しかし，回避成功回数はあがったもの の

5

個の故障に対しては全て失敗した．一方で，提案 診断手法に関してはタイルレベルと

MUX

レベル両 方とも故障特定と回避が可能であり，性能劣化もほと んどないことがわかった．また，復旧時間に関しても

MUX

レベルの故障回避時間はタイルレベルよりも短 いことがわかった．以上より，提案手法を用いること で

MUX

レベルの故障診断・回避は復旧時間，回避成 功率，性能全ての面でタイルレベルよりも優れている ことがわかった．

最後に図

17

に

FPGA-IP

のコアサイズ及びチャネ ル幅を変動させた場合の故障診断に要する時間を示す．

本評価で用いたアレイサイズ

16 × 16

，チャネル幅

48

本のテストサイクル数は

1,123,018

であった（表

2

）．

一方，アレイサイズ

128 × 128

，チャネル幅

192

本に 変更した場合，テストサイクル数は

98,862,596

とな る．

4. 3

で定式化したようにテスト時間はチャネル幅

W

に比例して増加するものの，テスト用のクロック サイクルを

10MHz

で行った場合でも

1

秒以内にはテ ストが完了する．

7.

む す び

本研究において，

FPGA-IP

コアの配線部に対する 故障診断手法について提案し，故障回避を行うため配 置配線ツールの開発を行った．提案手法では

6

種類の テストコンフィグレーションのみで高い故障診断能力

を得られることを確認した．また，計算機を用いた実 験にてタイルレベル，

MUX

レベル両方において，

5

個の故障に対し故障特定，故障回避共に完全に行える ことを確認した．加えて，その際の動作速度について

MUX

レベルの回避手法では回避前と比較して性能劣 化はみられなかった．

文 献

[1] K. Inoue, M. Koga, M. Iida, M. Amagasaki, Y.

Ichida, M. Saji, J. Iida, and T. Sueyoshi, “An eas- ily testable routing architecture and prototype chip,”

IEICE Trans. Inf. & Syst., vol.E95-D, no.2, pp.303–

313, Feb. 2012.

[2] J. Luu, I. Kuon, P. Jamieson, T. Campbell, A.

Ye, W. Fang, and J. Rose, “VPR 5.0: FPGA CAD and architecture exploration tools with single- driver routing, heterogeneity and process scaling,”

Proc. ACM/SIGDA International Symposium on Field Programmable Gate Arrays, pp.133–142, Feb.

2009.

[3] J. Cheatham, J. Emmert, and S. Baumgart, J. Luu, I. Kuon, P. Jamieson, T. Campbell, A. Ye, W. Fang, and J. Rose, “A survey of fault tolerant methodolo- gies for FPGAs,” ACM Trans. Design Automation of Electronic Systems (TODAES), vol.11, no.2, pp.501–

533, 2006.

[4] A. Doumar and H. Ito, “Defect and fault tolerance SRAM-based FPGAs by shifting the configuration data,” IEICE Trans. Inf. & Syst., vol.E83-D, no.5, pp.1104–1115, May 2000.

[5] J.L. Kelly and P.A. Ivey, “A novel approach to defect tolerant design for SRAM based FPGAs,”

Proc. ACM International Workshop on Field Pro- grammable Gate Arrays, pp.1–11, Feb. 1994.

[6] S. Durand and C. Piguet, “FPGA with selfrepair ca- pabilities,” Proc. ACM International Workshop on Field Programmable Gate Arrays, pp.1–6, Feb. 1994.

[7] N. Howard, A. Tyrrell, and N. Allinson, “The yield enhancement of field-programmable gate arrays,”

IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol.2, no.1, pp.115–123, 1994.

[8] V. Lakamraju and R. Tessier, “Tolerating operational faults in clusterbased FPGAs,” Proc. ACM/SIGDA international symposium on Field programmable gate arrays, pp.187–194, 2000.

[9] G.G. Lemieux and D.M. Lewis., “Analytical Frame- work for Switch Block Design,” Proc. FPL, pp.122–

131, Aug. 2002.

[10] V. Betz, J. Rose, and A. Marquardt, Architecture and CAD for deepsubmicron FPGAs, Kluwer Aca- demic, 1999.

[11] K. McElvain, “IWLS’93 Benchmark Set: Version 4.0,” Distributed as part of the MCNC International Workshop on Logic Synthesis ’93 benchmark distri-

bution, May 1993.

[12] “ABC: A system for sequential synthesis and verifica- tion,” http://www.eecs.berkeley.edu/˜alanmi/abc/

（平成25年3月6日受付，6月15日再受付）

尼崎 太樹 （正員）

2000九工大・情報工・制御システム工卒．

2002同大大学院修士課程了．同年NEC マイクロシステム（株）入社．アナログコ ア開発に従事．2005同社退職．同年，熊 本大学大学院自然科学研究科に入学．2007 博士後期課程修了．同年，同大学院自然科 学研究科助教．博士（工学）．現在，リコンフィギャラブルシス テムの研究に従事．IEEE，情報処理学会各会員．

西谷 祐樹

2012熊本大・工・情報電気電子工卒．同 年同大大学院自然科学研究科情報電気電子 工学専攻博士前期課程入学，同課程に在学 中．リコンフィギャラブルシステム等の研 究に従事．

井上 万輝 （学生員）

2008熊本大・工・数理情報システム工 卒．同年同大大学院自然科学研究科情報電 気電子工学専攻博士前期課程入学．2013 博士後期課程修了．博士（工学）．リコン フィギャラブルシステム等の研究に従事．

IEEE，情報処理学会各会員．

飯田 全広 （正員）

1988東京電機大・工・電子卒．同年三菱 電機エンジニアリング（株）入社．オフィ スサーバ，DBエンジン等の開発に従事．

1995同社を休職し，九州工業大学大学院 情報工学研究科に入学．1997博士前期課 程修了．同年，同社に復職．1999熊本大学 大学院自然科学研究科に入学．2002博士後期課程修了．2003 熊大・工・助教授．2006改組により同大学院自然科学研究科情 報電気電子工学専攻助教授．2007同専攻准教授．博士（工学）． 現在，リコンフィギャラブルシステム，VLSIシステム設計等 の研究に従事．著書「リコンフィギャラブルシステム」（共著）． 情報処理学会会員．

久我 守弘 （正員）

1987福岡大・工・電子卒．1989九大大 学院総理工修士課程了．1992同大学院博 士後期課程了．同年九工大マイクロ化総合 技術センター・講師．1998熊大・工・助 教授．2006改組により同大学院自然科学 研究科情報電気電子工学専攻助教授．2007 同専攻准教授．博士（工学）．現在，リコンフィギャラブルシス テム，計算機アーキテクチャ，VLSIシステム設計等の研究に 従事．著書「リコンフィギャラブルシステム」（共著）．情報処 理学会会員．

末吉 敏則 （正員）

昭51九大・工・情報工学卒．昭53同 大大学院修士課程修了．同年九大・工・助 手．同大学院助教授，九工大助教授を経て，

平9熊本大・工・教授．平18改組により 同大学院自然科学研究科情報電気電子工学 専攻教授．工学博士．この間，コンピュー タアーキテクチャ，VLSIシステム，システムソフトウェア等 の研究に従事．本会リコンフィギャラブルシステム研専元委員 長，本会コンピュータシステム研専元委員長．著書「並列処理 マシン」（共著），「リコンフィギャラブルシステム」（共著）な ど．IEEE，情報処理学会，電気学会各会員．