無閉路パーシャルスキャン厳密解法に基づく 最小スキャンFF選択問題の厳密解法に関する研究 日本大学 生産工学部 数理情報工学科 細川研究室 4年 27074番 登坂 元英 内容 回路のテストの容易化設計 回路のテスト：回路中の故障を検出 テストパターンを生成 今回用いるテスト容易化設計 パーシャルスキャン設計 組合せ回路ATPGの基本原理 ＡＴＰＧ ・テストパターン自動生成 ・テストパターン：故障の影響が任意の外部出力ピンに 伝わるような外部入力ピンの値を求める 解（テストパターン）の探索問題 LSI A B C D 外部入力 Ａ＝１ D＝０ 故障 外部出力 経験的にO(G2)以下 D＝１ やり直し B＝０ G：ゲート数 大規模回路に対してもほぼ100%の故障検出効率を達成 順序回路のATPGモデル ・回路を時間軸に展開 ・一般に展開する展開数は大きい ・たとえ小規模な回路であっても高故障検出効率は保証できない →LSIは順序回路 →テスト容易化設計が必要 組合せ回路 外部入力 FF 状態０ 初期状態 組合せ回路 外部入力 FF 状態１ 組合せ回路 外部入力 FF 組合せ回路 外部入力 × 状態２ 故障 FF 状態３ 外部出力 スキャン設計 スキャンスリップフロップ フリップフロップ（ＦＦ）にマルチプレクサを付加 FF 入力 D Q ｃｌｋ 出力 通常入力 スキャンイン 制御入力 M U X D Q ｃｌｋ スキャン設計によりFFの値が可制御、可観測 スキャン設計 ・フルスキャン設計 ・パーシャルスキャン設計 出力 スキャン アウト フルスキャン設計方法 すべてのフリップフロップ（ＦＦ）をスキャンＦＦで構成 外部入力 外部出力 組合せ回路 スキャンアウト（外部出力） FF FF FF スキャンイン（外部入力） ・核回路 は組合せ回路→高故障検出効率達成 ・オーバーヘッド（面積、遅延、消費電力）大：すべてのFFにMUX パーシャルスキャン設計方法 一部のフリップフロップ（ＦＦ）をスキャンＦＦで構成 外部入力 外部出力 組合せ回路 FF スキャンアウト FF FF スキャンイン ・核回路は順序回路→高故障検出効率の保証なし ・オーバーヘッド（面積、遅延、消費電力）小：一部のFFにMUX 無閉路パーシャルスキャン 外部入力から外部出力まで各FFを 一度しか通らないようにスキャンFFを選択 時間軸で展開せずにテスト生成が可能 故障検出効率を高めることができる 無閉路パーシャルスキャンの スキャンＦＦの選択方法 スキャンＦＦ選択の厳密解法 ・グラフ変換 ・分割分枝限定法 ・ＩＬＰに基づいた下界による枝刈り技術 上記３つの方法を総合的に用いることにより 現実的な時間で厳密解を求めることが出来る。 厳密解 ： 必ず最適解が求まる 最適解：最小個のスキャンFFで核回路を無閉路に グラフ変換 Ｓグラフ： ＦＦの繋がりを表したグラフ 頂点： ＦＦ 辺： 組み合わせ回路を通って到達可 例 v2 v1 v3 v4 Ｖ２ Ｖ１ Ｖ３ Ｖ４ グラフ変換 グラフ変換の操作 remove(vi) viの削除（viのすべての入出力の辺を削除） Ｖ２ Ｖ１ Ｖ２ Ｖ３ Ｖ４ Ｖ３ remove(v1) Ｖ４ ignore(vi) 全ての出力先に入力先を接続し、remove(vi) Ｖ２ Ｖ１ Ｖ２ Ｖ３ Ｖ４ Ｖ３ ignore(v1) Ｖ４ グラフ変換 グラフ変換の手続きのルール Ｔ１：viが自己ループを持っている時remove(vi)し、スキャンＦＦ選択 Ｖ２ Ｖ１ Ｖ２ Ｖ３ Ｖ４ Ｖ３ Ｖ４ Ｔ２：viの入力か出力が０の時remove(vi)する Ｖ２ Ｖ１ Ｖ２ Ｖ３ Ｖ４ Ｖ３ Ｖ４ Ｔ３：viの入力か出力が１で自己ループがない時ignore(vi)する Ｖ２ Ｖ１ Ｖ２ Ｖ３ Ｖ４ Ｖ３ Ｖ４ グラフ変換 グラフ変換の手続き Ｔ１、Ｔ２、Ｔ３が適用不可、空のグラフにならない 異なるＳＣＣ（強連結：任意の2点間で到達可能）間の辺を削除 この辺を削除 ＳＣＣごとに再度グラフ変換手続き適用 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 グラフが空、適用不可になったら終了 ＳＣＣ ＳＣＣ ＳＣＣ 総合的手法 以下のように グラフ変換、分割分枝限定法、ILPに基づいた下界による枝刈り を用いて厳密解を求める グラフ変換 適用可？ 分割分枝限定法 ILP計算 結果 circuit s208 s344 s420 s641 s838 s1488 s5378 s9234 s38417 ff sff 8 15 16 19 32 6 179 228 1636 8 7 16 14 32 6 0 150 1078
© Copyright 2024 ExpyDoc
