トップPDF J152 e IEICE 2010 6 最近の更新履歴 Hideo Fujiwara J152 e IEICE 2010 6

Fig. 6 (a) Single-core bypass path by IEEE 1500 wrapper. (b) Multi-core bypass path by IEEE 1500 wrapper. of making cores transparent as well as the cost of additional interconnect area simultaneously during optimization. (Additional Bypass Path) In the SoC design strategies, the behavioral models described using a hardware description language are not always available due to IP protection and so on. Even if it is available, it may happen that the total cost (including area and layout etc.) of making cores transparent by embedding multiplexers [23] is higher than that of bypass paths added outside of the cores since the embedded cores usually have IEEE 1500 wrappers and they can be used to configure the bypass paths. Figure 6 (a) shows an example of the bypass path using IEEE 1500 wrapper for the core used in Fig. 1 (a). In this example, a 4-bit bypass path from input wrapper boundary cells to output wrapper boundary cells is added outside of the core. Similarly, we can consider the multi-core bypass path (bypass path from a core input to another core output) by using IEEE 1500 wrappers as shown in Fig. 6 (b). In this paper, we use the term “single/multi- core bypass path” for the path implemented by IEEE 1500 wrappers while the term “transparent path” denotes the path implemented by embedded multiplexers. In transparency-

すべての静的・動的通信チャネルは FIFO キューで あるとする．すなわち，通信チャネルを用いて送信し た メッセージは 送信され た順に 相手に 受信され る．更 に ，チャネルを用いて 送信され た メッセージは紛失さ れないとする．文献 [8] のモデルでは ，ハンド オフ時に 動的通信チャネルが 消失し た場合，その FIFO キュー 内の メッセージは 紛失するとし ている．し かし 本論文 では ，簡単のために ，静的，動的にかかわらずすべて の通信チャネルに 入力され た メッセージは 有限時間内 に出力され ，メッセージの紛失は起きないと仮定する．

クラスタ再構成法とし ては ，既存のクラスタ構成法 を 適 用す るこ と も 考え られ る ．こ の 場 合 ，ク ラ ス タ ヘッド 数は 小さく抑えられ るが クラスタヘッド 変更数 は 大きくなってし まう．クラスタヘッド 変更数を小さ くする手法として， LCC （ Least Cluster Change ）法 が 提案され ている [5] ． LCC 法では ，トポ ロジ ーが 変 化し た場合に ，支配性，または 独立性が 成り立たない 部分だけで局所的にクラスタを再構成する手法である．

(1) p c 上にレジスタが存在する場合 p c 上にレジスタが存在する場合は TM を付加する． ここで， p c 上にある e 1 の直後のレジスタを r とす る． r の出力ポートを z ′ とし， r の直後の回路要素の 伝搬入力を x ′ とする．また， TM の二つの入力ポー トを x 及び y とし，出力ポートを z とする．このと き， TM を付加する場所について考える． TM を外部 入力に近い場所に付加すれば， TM を再利用できる可 能性が高くなり，面積オーバヘッドを縮小できると期

昭 44 阪大・工・電子卒．昭 46 同大大 学院博士後期課程了．阪大工学部助手，明 治大理工学部教授を経て，現在，奈良先端 科学技 術大学院大学情報科 学研究科教授． 昭 56 ウォータールー大客員助教授．昭 59 マッギル大客員準教授．論理設計，高信頼 設 計 ，設 計 自 動化 ，テ ス ト容 易 化 設計 ，テ ス ト生 成 ，並 列処 理，計算複雑度に関する研[r]

4. 2. 1 制御経路の決定と DFT 要素付加 各組合せ回路要素に対し，最小の付加ハードウェア で実現できる制御経路（ 2 入力組合せ回路要素の場合 は，互いに共通部分をもたない二つの制御経路）を決 定し， DFT 要素（マルチプレクサ，スルー機能）を付 加する．制御経路を求める組合せ回路要素は，一つず つ処理していくが，先の処理で付加した DFT 要素は 後の処理でも利用できるので，組合せ回路要素を処理 する順序によって，全体のハードウェアオーバヘッド は異なる．全体のハードウェアオーバヘッドを低く抑 えるには，なるべく必要性の高い DFT 要素から付加 していくことが望ましい．そこで，前処理として，必 ず付加が必要な DFT 要素を付加する．次に，外部入 力に近い組合せ回路要素から順に制御経路を決定する． これは，外部入力に近い組合せ回路要素ほど，制御経 路の選択肢が少なく，そこで付加する DFT 要素は必 要性が高いと考えられるからである．また，外部入力

G J に存在するすべての枝は SoC の実動作速度での連 続し たテ スト 系列の 印加に 利用可能であ る． c の G J は 無閉路であるので ，条件 1 より， c の各入力端子に 対し て， SoC の外部入力から 一つ以上の単純経路が 存 在する．更に 条件 3 より，各コアは 一つの 形状が 選択 され ， G J の頂点のうち V out に属する頂点 （ コアの出 力端子に 対応する頂点 ）の連続透明性を実現するため に 必要なすべての入射枝（ 連続透明経路 ）が G J に 存 在する．以上より， c が 連続可制御であれば ， c の G J に存在する各単純経路に沿って，テスト 系列を SoC の 外部入力から c のすべての入力端子に 連続し て印加可 能である．

通常のプ ロト コルでは ，プ ロト コル 実行開始時の分 散シ ステムの大域状況が ，あらかじ め決められた初期 状況であると仮定する．つまり，各プ ロセスは， あらか じ め決められた初期状態から実行を開始する．これに 対し ，自己安定プ ロトコル（ self-stabilizing protocol ） は ，プ ロト コル 実行開始時の分散シ ステムの大域状況 について 何も定めない．つまり，自己安定プ ロト コル は ，任意の大域状況から 実行を開始し ても，問題の解 を求めた状況に 安定するプ ロト コルである．この性質 から ，自己安定プ ロト コルでは ，プ ロセ スの一時的な 故障（プ ロセスの変数の値，プ ログ ラムカウンタの値 の破壊など ）により分散シ ステムがど のような大域状 況に 陥っても，故障し たプ ロセ スが 復旧すれば ，自動 的に 再び 解を求めた状況で 安定する．し たが って自己

ISB-RISC に 対し ， C ∗ (S) を 用いた テ スト 生成では ， S に 比べ，より多くの故障が 検出可能となり，テスト 生成時間もそれぞ れ 約 1/10000 ， 1/20 と 大幅に 短縮 した ．また ， C ∗ (S) で判定不可能となる故障も存在す るが ， S と比べてより多くの故障が 検出可能または冗 長と 判定され た ．すなわ ち，組合せ ATPG を用いて テスト 生成を行 うことにより，より短いテ スト 生成時

本研究では，強可検査性に基づくテスト容易化設計 法と同様に，対象とする故障モデルを単一縮退故障と し，レジスタ転送レベルデータパスをテスト容易化設 計の対象とする．強可検査のテスト容易性を失うこと なく，面積オーバヘッドを更に削減するために，強可 検査性の性質を緩和した部分強可検査性を新たに導入 し，部分強可検査性に基づくデータパスのテスト容易 化設計法及びテスト生成法を提案する．強可検査性が すべての回路要素に対して任意の値の印加を保証する のに対し，部分強可検査性では回路要素に対して値域 の任意の値の印加を保証する．また，提案するテスト 容易化設計法では，データパスを部分強可検査にする

．コント ローラ は 有限状態機械，デ ータパスは回路要素と回路要素を 接続する信号線で 記述され る．回路要素は ， PI ， PO ， ラッチ，レジ スタ，マルチプレ クサ，演算モジ ュール ， 観測モジ ュールに 分類され る．この うち，マルチプレ クサ，演算モジ ュール ，観測モジ ュールを組合せ回路 要素と呼ぶ．各回路要素は 端子をもち，それぞれデ ー タ端子，制御端子，観測端子に 分類され る．デ ータ端 子には ，回路要素にデ ータを 入力する入力端子と回路 要素からデ ータを 出力する出力端子がある．制御端子 は ，コント ロー ラか ら 制 御 信 号を 入 力す る 端 子で あ る．観測端子は ，コント ローラへ ステータス信号を出 力する端子である．信号線は ，デ ータ信号線，制御信 号線，ステータス信号線に 分類され る．デ ータ信号線 は ，二つの回路要素のデ ータ端子を接続する．制御信 号線は ，コント ローラと 制御端子を接続する．ステー タ ス信号線は ，観測端子とコント ローラを 接続する ．

DFT とし て Genesis [5] ∼ [7] がある． Genesis では 第 1 段階とし て回路要素ご とにゲ ートレ ベル 回路を 用い たテ スト 生成を行う．次に 第 2 段階とし て各回路要素 に 対し て ，外部入力から 回路要素の入力へ任意の値を 伝達し ，また回路要素の任意の値を外部出力まで 伝達 できるテ ストプ ラン の生成を試みる．テ ストプ ランが 存在し ない場合には DFT とし て 外部入力から 直接値 を代入し たり，外部出力で 直接値を観測するためのマ ルチプレ クサ（ テスト マルチプレ クサ ）と配線を RTL デ ータパ ス上の適切な回路要素の前後に 挿入する．こ のよ うな 手法に よって 従来手法 [2] で 生じ る第 2 段階

T 2 を圧縮し たテスト 系列 T を生成することができる． また ，テ スト 系列 T 1 , T 2 に 示すよ うに ，テ スト 系 列において 0 又は 1 に値が 決定し ている箇所と X で ある箇所は ，すべてのテスト 系列について一定である． この 情報から 複数のテ スト 系列が 圧縮可能か 否かは ， テ スト 系列中の値に 関係なく決定できる．よって，テ スト 系列が 生成され る前の段階で ，静的に 圧縮方法が 決定でき，圧縮時に 高速にテスト 系列を圧縮すること

それほど 考慮が 必要とされず，上記の並列計算モデ ル においても，通信コ ストの表現には 重点が おかれてい † 奈良先端科学技術大学院大学情報科学研究科 ，生駒市 Graduate School of Information Science Nara Institute of Science and Technology, 8916–5 Takayama, Ikoma-shi, 630– 0101 Japan

SDFG で 両立可能な 二つの 演算間に 経路が 存在し ， それらの演算を一つの 演算器とし て共有すれば ，もと の演算間の経路は共有し た演算器を通るループ となる． よって ，その演算間の経路上にあるいずれかの変数は ループ を切断するための スキャンレジ スタに 割り当て なければ なら ない ．両立可能な 演算間の 経 路の 長さ ， すなわちその経路上にある変数の数が 大きければ ，そ の うちいずれか 一つを スキャンレジ スタに 割り当てれ ば よいので ，スキャンレジ スタを選択する自由度は 大 きくなる．一般に 両立可能な二つの演算間には複数の 経路が 存在する．簡単のため，ここでは 最短経路を複 数の経路の代表とし て扱うことにする．複数ある経路 の中で 最短経路上の変数は 最もスキャンレジ スタの共 有が 行いに くいと 考えられ る．また ，スキャンレジ ス タに 割り当てられ る変数の ラ イフタ イムが 長ければ ， スキャンレジ スタは 共有し にくい．ラ イフタ イムの正 確な見積もりはレジ スタバ インデ ィングで行うとし て， ここではラ イフタ イムの代わりに 経路をもつ両立可能 な二つの演算間の時刻差を単純に評価することにする．

井上 智生 （ 正員 ） 昭 63 明大・工・電子通信卒．平 2 同大 大学院博士前期課程了．同年松下電器産業 （ 株 ）入 社．明治大大学院博士後期課程を 経て，平 5 奈良先端大情報科学研究科助手． 平 11 より広島市立大学情報科学部助教授． 松下電気電器産業（ 株 ）に おいて マイクロ プ ロセッサの研究開発に 従事．明治大，奈良先端大，広島市大 に おいて ，テスト 生成，並列処理，テスト 容易化設計に 関する 研究に 従事．博士（ 工学 ） ．IEEE，情報処理学会各会員．

増澤 利光 （ 正員 ） 昭 57 阪大・基礎工・情報卒．昭 62 同大 大学院博士後期課程了．同年同大情報処理 教育セン ター助手．同大基礎工助教授を経 て ，平 6 奈良先端科学技術大学院大学情報 科学研究科助教授，現在に 至る．平 5 コー ネル大客員準教授 （ 文部省在外研究員 ） ．分 散アルゴ リズム，並列アルゴ リズム，テスト 容易化設計，テス ト 容易化高位合成に 関する研究に 従事．工博．ACM，IEEE， EATCS，情報処理学会各会員．

BIST は ， test per scan 方式と test per clock 方式 に分類できる． test per scan 方式では ，回路中の（ 一 部の ）レジ スタを スキャンレジ スタに 変更し ，スキャ ン 操作に より， TPG で 生成し たテ スト 系列を スキャ ンレジ スタにシフト インし ，スキャンレジ スタに 格納 された応答を RA にシフトアウト する． test per scan 方式では ，スキャン 操作によりテスト 系列を 1 ビ ット ずつシフト イン するので ，連続し たシ ステムクロック でテ スト 系列を印加できず，テ スト 実行時間も長い． 一方， test per clock 方式では ，回路中の（ 一部の ） レ ジ スタを TPG ， RA に 変更する ．このよ うなテ ス トレジ スタとし ては ， BILBO （ Built-In Logic Block

Chen ら [11] は，テストプログラムテンプレートを 利用して制約を求める手法を提案している．テストプ ログラムテンプレートとは，オペランドの値が未決定 のテストプログラムであり，テスト対象モジュールに 対し，テストパターンの正当化及びテスト応答の観測 を行う命令列からなる．この手法では，テンプレート に 対 し ，い く つ か の ラ ン ダ ム パ タ ー ン を オ ペ ラ ン ド に与えたシミュレーション結果から回帰解析により制 約を抽出し，抽出した制約のもとでモジュール単体に 対してテスト生成を行う．最後に，得られたテストパ ターンからテンプレートのオペランドを求めてテスト プログラムを生成する．提案手法では，テンプレート 生成法にも触れているが，テスト対象モジュールの入 力空間として，テストパターンをモジュールに印加す る命令のオペランドのみを考慮するといった単純なテ ンプレート生成法を採用している．そのため，先行す る命令によって設定されたレジスタの値など，命令の オペランドには陽に現れないが命令の実行で用いられ る値などを考慮することができない．また，制約抽出 に回帰解析を利用するため正確な制約を抽出している ともいえない．実験結果では，組合せモジュールに対 しては良い結果が得られているが，順序モジュールに 対するテストプログラム生成は行われていない．

NOT ゲートの出力にはファンアウトがないという回 図 1 ノンロバストテスト可能なパス遅延故障 Fig. 1 A non-robust testable path delay fault. 図 2 パスリーフ化変換（ステップ 1） Fig. 2 The first step of the path-leaf transformation.