J93 j IEICE 2002 2 最近の更新履歴 Hideo Fujiwara J93 j IEICE 2002 2

論 文

連続可検査性に 基づ くコアベースシ ステムオンチップ の

テスト 容易化設計法

米田 友和

藤原 秀雄

A DFT Method for Core-Based Systems-on-a-Chip Based on Consecutive

Testability

Tomokazu YONEDA^† and Hideo FUJIWARA^†

あらまし コアベー スシ ステムオンチップ（SoC）が可検査であるためには，それを構成するコア自身が可検 査（ 高品質のテ スト 系列が 提供され る ）であり，かつSoC の外部から内部の各コアへのテストアクセスが可能で ある必要が ある．更に ，このテストアクセス方式によりコア間の信号線も可検査である必要が ある．_{SoC では縮} 退故障など のような論理故障のみならず，遅延故障など のようなタ イミング 故障のテ スト も重要となる．そのた めには ，コアに 実動作速度（at-speed）で任意のテストパターンを連続して印加でき，その応答を連続して観測 できる必要が ある．本論文では ，このようなテストアクセスを可能とする性質とし て，コアに 対し て連続透明性， SoC に対して連続可検査性なる新しい概念を提案し ，連続可検査な SoC を実現するためのテスト容易化設計法 を示す．

キーワード テスト 容易化設計，コアベ ースシ ステムオン チップ，テストアクセス機構，連続透明性，連続可 検査性

1. ま え がき

近年，半導体技術の進歩により，シ リコンチップ 上 に 搭載することので きるト ランジ スタ数は 増加の一途 をたど っている．これにより従来は 複数の_LSIで 構成 し ていたシ ステムを ，各_LSIをコアと呼ばれ る機能ブ ロックとし て再利用し ，シ ステム全体を一つの_LSIで 実現するコアベースシ ステムオンチップ（_core-based Systems-on-a-Chip^{，以 下}SoC）が 注 目 され て い る ． 複数の_LSIの機能を₁チップに 集積し た場合，ボ ード へ 搭載するチップ 数の 低減に よる 実装面積の 縮小化 ， 実装コ スト の 低減 ，更に 高速化と いった 効果を もつ ． また，設計済みの_IP（Intellectual Property^）コアを 利用することで 短期間で 大規模な回路の設計が 可能と なる．しかし 現在，この_SoCのテスト 技術の開発が 課 題_[1]となっている．

SoCでは ，各コアに 対し てテ スト 系列が 供給され ，

†奈良先端科学技術大学院大学情報科学研究科 ，生駒市

Graduate School of Information of Science, Nara Institute of Science and Technology, 8916–5 Takayama-cho, Ikoma-shi, 630–0101 Japan

コアの 入出力が 直接制御_/観測可能であれば ，この供 給され るテ スト 系列でそのコアをテ スト することが 可 能で あ る．このため_SoCのテ スト は ，テ スト 系列を SoC外部からコアへ印加し その 応答を_SoC外部で 観 測（ テスト アクセ ス ）することで 行われ る．し たが っ て_SoCが 可検査で あ るためには ，コア 自身が 可検査

（ 高品質なテ スト 系列が 提供され る ）で あ り，か つコ アへのテストアクセスが可能である必要がある．更に ， コア間の信号線も可検査である必要がある．

テ スト ア クセ ス 方式には ，テ スト バ ス方式_{[2], [3]}， 境界 スキャン 方式_{[4], [5]}，透明経路方式_[6]∼_[8]など がある．テストバス方式は_SoCの外部入力から外部出 力へテ ストデ ータを 伝搬するためのバ スを付加し ，更 に 各コアの入力に マルチプレ クサを 付加し 通常動作時 の入力とテ スト 実行時の入力を切り換え ることでテ ス ト アクセ スを実現する方式である．この方式はテスト 実行時間は 短いが ，面積_/遅延オーバヘッド が 大きい という欠点がある．更にコア間のテ ストが 困難である という問題点がある．

境 界 スキャン 方 式は ，_SoC内の す べ て のコ ア の 入 出力に スキャンフ リップ フロップ を挿入し ，スキャン

D– Vol. J85–D– No. 2 pp. 173–183 2002 2 173

パスを形成する．この スキャンパスを利用し ，各コア の入出力値を_SoC外部から 直接制御_/観測可能とする ことでテ ストアクセスを実現する方式である．この方 式はコア間のテ ストはできるが ，テ スト 実行時間は 長 く，更に 面積_/遅 延オーバヘッド が 大きいと い う欠点 がある．

透明経路方式は ，テ ストバス方式や境界スキャン 方 式とは 異なり，コア 内部の回路要素や信号線を利用し てコアの内部に 透明経路と呼ばれ るテ ストデ ータを 伝 搬す るため の 経路を 実 現し て いる ．これ に より_SoC の既存の接続線を利用し たテストアクセ スを実現し て いる．この方式はコア間のテストができ，更に境界ス キャン方式よりも低い面積_/遅延オーバヘッド ，短いテ スト 実行時間を達成し ている．

SoCでは縮退故障など のような論理故障のみならず， 遅延故障など のよ うなタ イミング 故障のテ スト も重要 となる．し たが って ，_SoCのコアに対し てはタ イミン グ 故障を対象とし たテ スト 系列が 供給され る場合も想 定され る．このよ うに ，コアには 様々な故障モデ ルを 対象とし た様々なテ スト 系列が 供給され ，そのコアが SoCに組み込まれた後でも，その系列を用いて 想定し た故障を完全にテスト することが 必要となる．そのた めには ，各コアへ任意のテ スト 系列を実動作速度で 連 続し て_SoCの外部から 印加し ，その応答を_SoCの外 部で 観測（ 連続テ スト ア クセ ス ）で きる 必要が あ る ． テストバス方式はこの連続テストアクセスはできるが ， コア間のテ ストが 困難である．一方，境界スキャン 方 式と透明経路方式はコア間のテ ストはできるが ，連続 テ ストアクセスができない．

本論文ではこのよ うな連続テストアクセ スを可能と し ，かつコア間のテ ストを可能とする性質とし て ，コ アに 対し て連続透明性，_SoCに 対し て連続可検査性な る新し い概念を提案し ，連続可検査な_SoCを実現する ためのテ スト 容易化設計法を示す．連続可検査な_SoC は ，すべてのコアとすべての信号線に 対し て連続テス ト アクセスが 可能であり，任意のテ スト 系列を実動作 速度で 連続し てコアや信号線に 印加し ，観測すること ができるので ，コア単体に対し てテスト 可能な故障は ， SoCに組み込まれた後でもテスト 可能であることを保 証する．

以下，2.では 本論文で 対象とする_SoCのモデ ル 化 を行い，3.では_SoCの連続可検査性について述べる． 4.で_SoCを連続可検査に するためのテ スト 容易化設 計法について述べ，5.でまとめを行う．

図1 コアベースシステムオンチップ

Fig. 1 Core-based systems-on-a-chip.

2. コアベースシ ステムオンチップ（ SoC ）

本章では ，本論文で 対象と する_SoCに ついて 述べ る．_SoCは信号線と回路要素で構成され る（ 図₁）．回 路要素は_SoCの 外部入力 ，外部出力 ，コアに 分類さ れ ，信号線を接続する端子をもつ．コアは 一般に 複数 の入力端子と出力端子をもち，各端子のビ ット 幅は 必 ずし も同じ でない．外部入力は 出力端子のみからなる 回路要素，外部出力は 入力端子のみからなる回路要素 とみなす．信号線は 回路要素の出力端子と入力端子を 接続する．出力端子には 複数の信号線が 接続できるが

（ ファンアウト 可能 ），入力端子に 接続できる信号線は 一つとする．

3. 連続可検査性に基づく SoC のテスト

本章では ，連続可検査性に基づく_SoCのテ ストにつ いて 述べる ．連続可検査な_SoCと その 連 続テ スト ア クセスを図₂に示す．コアの入力端子の連続透明性と は ，その入力端子に 入力され る任意の長さの 系列を値 を変え ることなく，出力側に 連続し たクロックサ イク ルで 伝搬で きる性質をい う．図₂のコア₄に おいて ， 灰色の入力端子は 連続透明であり，時刻_{t+ 1}からの 連続し た時刻で 入力され るコア₃のテ スト 応答系列を mサ イクル 後の 時刻_{t+ 1 + m}から 連続し て 出力可 能である．このときの 系列の伝搬経路を入力端子の連 続透明経路という．同様に ，コアの出力端子の連続透 明性とは ，その出力端子から出力され る任意の長さの 系列を入力側から 連続し たクロックサ イクルで伝搬で きる性質をいい，その 伝搬経路を出力端子の連続透明 経路という．図₂のコア₂において ，灰色の出力端子 は 連続透明であり，時刻_{t− k}からの連続し た時刻に

コア₃へのテ スト 系列をコア₂の入力端子に印加する ことで ，時刻tからの連続し た時刻にその系列を出力 することが 可能である．各コアに 対し て ，テ ストコン ト ローラ（_SoC内部または外部に 存在 ）から制御信号 が 供給され ，その制御信号により各コアの連続透明経 路が 実現され る．このように制御信号によりコアが 連 続透明経路を 実現し ている 状態をコアの 形状と 呼ぶ ． SoCの連続可検査性とは ，各コア（ 各信号線 ）に 対し て ，他のコアの形状を選択することにより，連続透明 経路及び 信号線を用いて 連続テストアクセ スできる性 質をい う．図₂では ，時刻_tからの連続し た時刻にコ ア₃の 各入力端子へテ スト 系列を 印加し ，時刻t+ 1 から 連続し た時刻に 出力され る応答系列を観測するコ ア₃への連続テストアクセスを示し ている．テ ストコ ント ローラからの制御信号により，コア₁，コア₂，コ ア₄の 灰色の 端子の 連続透明経路が 実現され て い る． コア₃のテ スト に 必要なテ スト 系列を_SoCの 外部入 力に 時刻_{t− l}と時刻_{t− k}からの連続し た 時刻に そ れぞれ 入力し ，_SoCの外部出力で 時刻_{t+ 1 + m}から の連続し た時刻に 出力され る応答系列を観測すること で コア₃の 連続テ スト ア クセ スが 実現され る ．以下 ， 3.1でコアの連続透明性を，3.2で_SoCの連続可検査 性を定義する．

3. 1 コアの連続透明性

［ 定義₁］（ コアの連続透明性 ） 入力端子I のi番目 のビ ット を _I(i)，出 力 端 子 _Oの _j 番 目のビ ット を

図2 連続テストアクセス Fig. 2 Consecutive test access.

O(j)^{とする．制御入力}T により，I(i)^とO(j)^間に 経路P が 存在し ，_I(i)に 連続し て入力され る任意の 長さの系列を_O(j)で連続し て観測できるとき，_P は 連続透明経路であるといい，_I(i)と_O(j)は 連続透明 であ るとい う．_T に より_P を 実現し ている状態をコ アの形状という．入力端子I（ 出力端子O）に関し て， I(O)のすべてのビ ット を同一のT で 連続透明にする ことが 可能であるとき ，_I(O)は 連続透明であると い い，_T により実現され る経路を_I(O)の連続透明経路 と い う．すべ ての 入 出力 端子が 連続透 明で あ ると き ， コアは 連続透明であるとい う． _✷

連続透明なコアとその 形状を図₃に示す．連続透明 なコアには様々な形状が存在し ，各形状は番号によって 識別され る．形状を選択することに より，各入出力端 子の連続透明経路が 実現され ，その端子が 連続透明と なる．連続透明経路を系列の伝搬方法によって，_JA型

（Justification AND^），PA^型（Propagation AND^）， PO^型（Propagation OR^）の3^{種類に 分類する．}JA 型は 出力端子の連続透明経路であり，テ スト 系列の印 加に利用され る．_PA型，_PO型は入力端子の透明経路 であり，応答系列の観測に利用され る．図_{3 (a)}は_PA 型の連続透明経路を示している．入力端子I1^に入力さ

れ る任意の長さの 系列は ，出力端子_O2にのみ伝搬す る．図_{3 (b)}も_PA型の連続透明経路を示し ているが ， 入力端子_I2に入力され るビ ット 幅_W(I2)の任意の長 さの系列は，ビット 分割し_{(W (I2}) = w2 + w3)^，出力 端子O1^とO2^{に 伝搬する．図} 3 (c)^はPO^型の連続 透明経路を示している．入力端子_I3に入力され るビッ ト 幅_W(I3)の任意の長さの 系列は ，ファン アウトし (W (I2) = w2 = w3)^{，出力端子}O1^とO2^{の両方に伝}

搬する ．図_{3 (d)}は_JA型の 連続透明経路を 示し てい

図3 連続透明なコアとその形状

Fig. 3 Various configurations of a consecutive transparent core.

る．出力端子O1 から出力され る任意の長さの系列は ， 入力端子I2からのみ伝搬され る．図_{3 (e)}も_JA型の 連続透明経路を示し ているが ，出力端子_O2 から出力 され るビ ット 幅_W(O2)の任意の長さの系列は ，入力 端子_I1と_I3 から 伝搬され る_{(W (O2}) = w7 + w8)^．

SoCの回 路要素であ るコアが 連続透明であると き， SoCは ，外部入力，外部出力，コアの端子を頂点に 対 応させ ，信号線，コアの連続透明経路を枝に 対応させ たコア接続グ ラフ _G= (V, E, λ)^{で 表現することがで} きる．_SoCに 対し て ，コア接続グ ラフ_G= (V, E, λ) を次の有向グ ラフ（ 図₄）とし て定義する．

• V = VP I∪ VP O∪ Vin∪ Vout

VP I ^はSoCの外部入力に 対応する頂点の集合， VP O^はSoCの外部出力に 対応する頂点の集合， Vinはコアの入力端子に 対応する頂点の集合， Voutはコアの出力端子に 対応する頂点の集合とする．

• E = Ecore∪ Enet

Ecore= {(x, y) ∈ Vin× Vout|^{連続透明経路に対応す} る枝の集合_}，

Enet= {(y, x) ∈ Vout× Vin|信号線に 対応する枝の 集合_}．

• λ : E → 2^{C×I×T ×W} C^{はコアの集合とする．} Iは 形状識別番号の集合とする． T = {JA, JO, P A, P O}^とする．

JA, P Aは 連続透明経路の型を表し ，_{P O}は 連続透明 経路と信号線の型を表し ，JOは 信号線のみの 型を表 すラベル とする．続透明経路に 対応する枝_{e∈ Ecore} は ，_eの型に 応じ て JA, P A, P O ^{のラベル で 表され} る．本論文で対象とする_SoCにおいて ，信号線はファ

図4 コア接続グラフ Fig. 4 Core connectivity graph.

ンアウト のみが 可能であり，テ スト 系列の印加と応答 の観測の両方に利用することが 可能である．これより， 信号線_{e∈ Enet}は ，ファンアウト のみが 可能であり， テスト 系列の印加に 利用可能を表す_JOと，連続透明 経路の型である_{P O}（ ファンアウトのみが 可能であり， 応答の観測に利用可能 ）の二つのラベルで 表され る． W は ，連続透明経路と 信号線のビ ット 幅の 集合とす る．

ただし ，_{e∈ Enet} ならば

λ(e) : {{φ, φ, JO,^{信号線のビ ット 幅}}, {φ, φ, P O,^{信号線のビ ット 幅}}}

とする．

図₃の連 続透明経路と 形状を もつコ アに 対す る_λ によるラベルを図₅に示す．ここで ，コア接続グラフ， またはその部分グ ラフにおいて 出射枝のみをもち，入 射枝をもたない頂点をソース，入射枝のみをもち，出 射枝をもたない頂点をシン クとする．コアの形状を選 択するとは ，選択され た形状識別番号をもつ枝のみを 残し ，他の枝をそのコアから除去することをいう．

3. 2 SoCの連続可検査性

本論文では ，コアにはテ スト 系列が 与えられている ものと仮定し ，以下の二つの条件が 成り立てば_SoCが 連続可検査であるとする．

• すべてのコアへの連続テストアクセ スが 可能

• コア間のすべての信号線のテ ストが 可能 本節では ，_SoCの連続可検査性をコア接続グ ラフ上で 定義する．はじ めに ，コアの連続可制御性，信号線の 連続可制御性，端子の連続可観測性をコア接続グ ラフ 上で 定義し ，次に_SoCの連続可検査性を定義する．

3. 2. 1 コアの連続可制御性

コアの すべて の 入力端子に_SoCの 外 部入力から 連 続し たクロックサイクルで 任意の値が 伝搬可能な性質 とし てコアの連続可制御性を次のよ うに定義する．

［ 定義₂］（ コアの連続可制御性 ）_SoCの コ ア 接 続グ ラフ _G，コア_{c∈ C}について ，次の 条件をすべて 満

図5 ^λによるラベル Fig. 5 Label by λ.

たす無閉路コア 接続部分グ ラフ GJ ^{が 存在するとき ，}

コアcは連続可制御であるという．また ，部分グ ラフ GJ ^をコアcの正当化部分グ ラフという．

（₁）_GJ のシン クは_cのすべての入力端子からな り，ソースは_SoCの外部入力だけからなる．

（₂）GJ ^{のすべての枝は ，}JAまたはJOのラベ ルをもつ．

（₃）_Gにおいて ，各コアに 対し 一つの形状を選択 することで 得られ る部分グ ラフを_G^′ とする．_GJ の 各頂点について ，

（_a）_G^′におけ るすべての入射枝を含む．

（_b）出射枝がJOのラベルをもつ場合，G^′ にお け るただ 一つの出射枝のみを含む． _✷

コア _cの 正 当化部分グ ラフ_GJ に 存在するすべて の枝は 連続透明経路またはコア間を接続する信号線で あり，_JOまたは_JAのラベルをもつ（ 条件₂）ので ， GJに存在するすべての枝は_SoCの実動作速度での連 続し たテ スト 系列の 印加に 利用可能であ る．_cの_GJ は 無閉路であるので ，条件₁より，_cの各入力端子に 対し て，_SoCの外部入力から 一つ以上の単純経路が 存 在する．更に 条件₃より，各コアは 一つの 形状が 選択 され ，GJ^{の頂点のうち}Vout^{に属する頂点（ コアの出}

力端子に 対応する頂点 ）の連続透明性を実現するため に 必要なすべての入射枝（ 連続透明経路 ）が _GJ に 存 在する．以上より，_cが 連続可制御であれば ，_cの_GJ に存在する各単純経路に沿って，テスト 系列を_SoCの 外部入力からcのすべての入力端子に 連続し て印加可 能である．

3. 2. 2 信号線の連続可制御性

信号線に_SoCの 外 部入力から 連続し た ク ロックサ イクルで 任意の値が 伝搬可能な性質とし て信号線の連 続可制御性を次のよ うに定義する．

［ 定義₃］（ 信号線の連続可制御性 ） _SoCの コ ア 接 続 グ ラフ_G，信号線_e= (y, x) ∈ Enet^{について ，次の}

条件をすべて満たす無閉路コア接続部分グ ラフ_GJが 存在するとき ，信号線_eは 連続可制御であると い う． また，部分グラフ_GJ を信号線_eの正当化部分グ ラフ という．

（₁）_GJ の シ ン クは _yの みか ら な り，ソ ー スは SoCの外部入力だけからなる．

（₂）_GJ のすべての枝は ，_JAまたは_JOのラベ ルをもつ．

（₃）_Gにおいて ，各コアに 対し 一つの形状を選択 することで 得られ る部分グ ラフを_G

′

とする．_GJ の

各頂点について ，

（_a）G^′におけ るすべての入射枝を含む．

（_b）出射枝が_JOのラベルをもつ場合，_G

′

に お け るただ 一つの出射枝のみを含む． _✷

コアの連続可制御性と同様に ，信号線_eが 連続可制 御であれば ，eのGJ に存在する各単純経路に沿って， テ スト 系列を_SoCの 外部入力からeに 連続し て 印加 可能である．

3. 2. 3 端子の連続可観測性

端子から 出力され る任意の系列を連続し たクロック サ イクルで_SoCの 外 部出力まで 伝搬可能な 性質とし て端子の連続可観測性を次のよ うに 定義する．

［ 定義₄］（ 端子の連続可観測性 ）_SoCの コ ア 接 続グ ラフ_G，端子 _{v∈ V} について ，次の 条件をすべて満 たす無閉路コア 接続部分グ ラフ _GP が 存在するとき， 端子_vは連続可観測であるという．また ，部分グ ラフ GP ^を端子vの伝搬部分グ ラフという．

（₁）_GP のシン クは_SoCの 外 部出力だけ から な り，ソースは端子_vのみである．

（₂）_GP のすべての枝は ，_{P A}または_{P O}のラベ ルをもつ．

（₃）Gにおいて ，各コアに対し 一つの形状を選択 することで 得られ る部分グ ラフを_G

′

とする．_GP の 各頂点について ，

（_a）出射枝が _{P A}のラベル をもつ場合，_G^′にお け るすべての出射枝を含む．

（_b）出射枝が P Oのラベルをもつ場合，G^′にお け るただ 一つの出射枝のみを含む． _✷

v^のGP に存在するすべての枝は連続透明経路また はコア間を接続する信号線であり，_{P O}または_{P A}の ラベルをもつ（ 条件₂）ので ，_GP に 存在するすべて の 枝は_SoCの 実動作速度で の 連続し たテ スト 応答系 列の伝搬に利用可能である．_cの_GJ は無閉路であり， 条件₁より，_vから_SoCの外部出力への単純経路が 存 在する．条件₃より，各コアは一つの形状が 選択され ， GP ^{の頂点の うち}Vinに 属する頂点（ コアの入力端子 に 対応する頂点 ）の連続透明性を実現するために 必要 なすべての出射枝（ 連続透明経路 ）が_GPに存在する． 以上より，_vが 連続可観測であれば ，_vの_GP に 存在 する単純経路に 沿って ，_vから 出力され る任意の応答 系列を_SoCの外部出力へ連続し て伝搬可能である．

3. 2. 4 _SoCの連続可検査の定義

コア（ 信号線 ）への連続テストアクセ スを可能とす るためには ，連続し たクロックサイクルでのテスト パ

ターン の印加と出力応答の観測が 同時にできなければ ならない．テスト パターン の印加に 関し ては ，コアの すべての入力端子に 同時に 連続し て印加する必要があ り，コアは 連続可制御でなければ ならない．応答の観 測に 関し ては ，すべての出力端子を同時に 連続し て観 測する必要はなく，各出力端子ご と時分割で 観測すれ ば 十分であるので ，各出力端子が 連続可観測であれば よい ．以上の 理 由より_SoCの 連続可検査性を 次のよ うに 定義する．

［ 定義₅］（_SoCの連続可検査性 ） _SoCのコ ア 接 続グ ラフ_G= (V, E, λ)が 次の 条件を すべて 満た すと き ， SoCは 連続可検査であるという．

（₁）各コア_{c∈ C}の各出力端子_{v∈ Vout}に 関し て ，互いに共通部分をもたない_cの正当化部分グ ラフ と_vの伝搬部分グ ラフが 存在する．

（₂）各信号線_e= (y, x) ∈ Enet^{に 関し て ，互い}

に 共通部分を もたないeの正当化部分グ ラフとxの 伝搬部分グ ラフが 存在する． _✷

SoCが連続可検査であれば ，各コア_cの各出力端子 vに 関し て ，互いに共通部分をもたない_cの正当化部 分グ ラフと_vの伝搬部分グ ラフが 存在する．定義₂よ り，cの 正当化部分グ ラフGJ ^{が 存在すれば ，}GJ ^に

存在する各単純経路に沿ってテスト 系列を_SoCの外部 入力から_cのすべての入力端子に連続し て印加可能で あり，定義₄より，_vの伝搬部分グ ラフ _GP が 存在す れば ，_GJ に 存在する単純経路に 沿って ，_vから 出力 され る任意の 応答系列を_SoCの 外部出力へ 連 続し て 伝搬可能であ る．更に_GJ と _GP が 共通部分を もた ないので ，連続し たクロックサイクルでのテ スト 系列 の印加と応答系列の観測を同時に 行うことができるの で ，コアへの連続テ ストアクセスが 可能である．_SoC が 連続可検査であれば ，各信号線_eについても同様に 連続テ スト アクセスが 可能となるので ，コア間のすべ ての信号線のテ ストが 可能である．

4. テスト 容易化設計法 4. 1 テスト 容易化設計

SoC^{に 含まれ る}IPコアを設計変更することはで き ない．本章では ，すべてのコアが 連続透明であり，コ ア内部は 設計変更できないという仮定のもとで ，与え られ た_SoCを 連続可検査に するため のテ スト 容易化 設計法（Design for Testability^，以下DFT^{）を 考察} する．コアが 連続透明でない場合，コアの入力端子か ら 出力端子へマルチプレ クサを 用いてバ イパス経路を

付加することにより，コア内部を設計変更することな く連続透明性を実現可能であるので ，上記の仮定で 一 般性を失うことはない．

連続可検査な_SoCは ，コアの各出力端子に 関し て ， 互いに 共通部分をもたない正当化部分グ ラフと伝搬部 分グ ラフをもつ．更に 信号線に 関し ても，互いに 共通 部分をもたない正当化部分グ ラフと伝搬部分グ ラフを もつ．これらの部分グ ラフの経路に 沿って連続し たク ロックサ イクルで 任意の系列を伝搬することが 可能で ある．

与えられた_SoC内のコアの出力端子，または信号線 に 対し て ，互いに 共通部分をもたない正当化部分グ ラ フと伝搬部分グ ラフが 存在し ない場合，連続可検査に するために_SoCに 新たに 経路を 付加する必要があ る． この経路は マルチプレ クサを用いて 外部入力からの経 路，または 外部出力への経路を付加することで実現す る．そこで ，_SoCを連続可検査にするための_DFTを， 次の最適化問題とし て定式化する．

［ 定義₆］（ 連続可検査_DFT） _SoCを連続可検査にす るための_DFTを次の最適化問題とし て定義する．

・ 入力：_SoC（ コア接続グ ラフ ）

・ 出力：連続可検査な_SoC

・ 最適化目標：付加するハード ウェア量最小化 _✷ 4. 2 テスト 容易化設計法

連続可検査_DFTを 解くための 発見的アルゴ リズム を 示す．本アルゴ リズムでは ，連続可検査_DFTを 解 くために 以下の四つの 段階に分けて考え る．

（₁）コアの連続可制御性のための_DFT

（₂）コアの連続可観測性のための_DFT

（₃）信号線の連続可制御性のための_DFT

（₄）信号線の連続可観測性のための_DFT

各段階で最適解を求めるアルゴ リズムを以下に示す． 4. 2. 1 コアの連続可制御性のための_DFT

具体的には以下の方法で 各コアに 対し て制御初期グ ラフ，制御中間グ ラフを生成する．その 制御中間グ ラ フが 正当化部分グ ラフと な るための 条 件式を 導出し ， 整数計画問題を解くことで 最小の付加ハード ウェアで すべてのコアを連続可制御とする．

［_Step1］ 制御初期グ ラフの生成

コア接続グ ラフ _Gから ，コア_{c∈ C}の制御初期グ ラフ_GJcを以下の方法で 生成する．図₆に ，図₄の コア接続グ ラフ Gに対する，コア_c6の制御初期グ ラ フ_GJc6 を示す．図中の数字は ，その連続透明経路を 実現するための形状識別番号を表す．

図6 制御初期グ ラフG_Jc6 Fig. 6 Justification initial graph.

はじ めに ，_Gから_JA または_JOのラベルをもつ 枝のみを 残し ，他の枝を除去する．次に ，c内の連続 透明経路の枝を_Gから除去し ，_cの入力端子に対応す る頂点_{v∈ Vin}をすべてをシン クとする．そのシン ク から 有向辺を逆にたど ることで 到達可能となる枝，頂 点を_cの制御初期グ ラフ_GJc とする．_GJcには_cの 入力端子に 対応する頂点も含む．

GJ_cに 含まれ るコアの集合を _AJc とする．ここで コアが _GJc に 含まれ るとは ，コアに 属する一つ以 上 の 連 続透明経路が _GJc に 存在することを い う．コア a∈ AJc ^{に 対し ，G}Jc に 含まれ る形状の 集合を _BJa とする．a∈ AJ_c^{に 対する}BJ_a^{の直積集合を}

KJ_c =

a∈A_Jc

BJ_a

= BJ_a1× BJ_a2× BJ_a3× . . . .

とする．制御初期グ ラフでは ，各コアには 複数の形状 識別番号が 存在し ，連続透明性が 実現され ていない．

［_Step2］ 制御中間グ ラフの生成

GJ_c ^とk∈ KJ_c ^{から ，}c^{の 制御中間グ ラフ} GJ_c,k

を 以下の 方法で 生成する ．図₇に ，図₆の_GJc6 に 対する，制御中間グ ラフ_GJ

c6,k1 ^{を示す．図中のJA，}

JOは 連続透明経路及び 信号線の型を表す．

はじ めに ，_AJc に 属するコアにおいて ，_kに 対応す る形状をそれぞれ 選択し ，各コアの連続透明性を実現 する．このとき，新たにシン クとなった頂点からのみ 到達可能な 枝，頂点を _GJc から 除去することで 得ら れ るグ ラフを制御中間グ ラフ_GJ

c,k ^{とする．GJ}c,k ^は

Gに 対し ，各頂点はすべての入射枝を含み，各コアに ついて 一つの形状に 関する枝のみを 残し た部分グ ラフ である．_GJ

c,k の頂点の うち，以下のいずれかの 条件

図7 制御中間グ ラフG_Jc6,k1 Fig. 7 Justification middle graph.

に 当ては まる頂点qの集合をQJ ^とする．

（₁）qはソースであり，VP I^{に 属さない}

（₂）_qは_JOのラベルをもつ二つ以上の出射枝を もつ

（₃）_qを含む閉路が 存在

QJ ^はGJ_c,k の頂点の中で ，正当化部分グ ラフの条件

（［ 定義₂］）にあては まらない頂点の集合となる．

［_Step3］ 整数計画問題への帰着

コア_cの連続可制御性の評価変数とし て ，以下の整 数変数を定義する．

Yc ^：cに 関する連続可制御性

Yc,k^：cの形状集合kに 関する連続可制御性 Y_c,k^{q ：}GJ_c,k ^{におけ る頂点}q^{に 関する}

連続可制御性

各変数は₁以上のとき，その性質を満たすものとする． 更に ，_xei を次のよ うに 定義する．

xe_i=

1 eiに マルチプレ クサを 挿入 0 eiに マルチプレ クサを 挿入し ない

(1)

この _eiを用いて_Y

q

c,k^をqが 満たす条件によって，以 下の（₁）∼（₃）のように定義する．_qが（₁）∼（₃） の複数の条件を同時に 満たす場合は ，各条件で定義さ れ る_Y

q

c,k ^{の積をqのY} q

c,k^{とし て定義する．}

（₁）_qが_GJc,kのソースであり，_{VP I}に属さない 場合

q^とGJ_c,k のシン ク間の単純経路の 集合を _S とす る ．_qに 関し て_GJ

c,k を 連続可制御とするためには ， S^{に属する各単純経路}sに対し て，一つ以上の信号線 に マルチプレ クサを付加し ，_SoCの外部入力からの経 路を実現すれば 十分である．_sに存在する信号線に 対 応する枝の集合を_Esとすると ，_sに 対し ，一つ以上

の信号線に マルチプレ クサを付加するとは ，以下の式 で 表され るms^が1以上となることをいう．

ms= ^

e_i∈E_s

xe_i (2)

この_msを用いて ，_Y

q

c,kを次の式で 表現する． Y_c,k^q =

s∈S

ms (3)

（₂）_qが_JOのラベルをもつ二つ以上の出射枝を もつ場合

GJ_c,k ^{に おけ る}q の 出射枝の 集 合を _R と す る ．_q と_GJ

c,k のシン ク間の単純経路の集合の うち，_{r∈ R} を含む単純経路の集合を Sr とする．正当化部分グ ラ フでは ，頂点に 対し て一つの_JOのラベルをもつ出射 枝のみを 含む（［ 定義₂］）．_qに 関し て_GJ

c,k ^{を 連続}

可制御とするためには ，_{R− r}の各要素_rnに 対する Srn の各単純経路に 対し て，一つ以上の信号線に マル チプレ クサを付加し ，_SoCの外部入力からの経路を実 現すれば 十分である．ms^{を用いて ，}Y_c,k^q を次の式で 表現する．

Y_c,k^q =^

r∈R





r_n∈R−r





s∈S_rn

ms







 (4)

（₃）qを含む閉路が 存在する場合

GJ_c,k ^{に おいて ，}qを 含む閉路の集合をS とする． q^{に関し て}GJ_c,kを連続可制御とするためには ，_Sに 属する各閉路_sに対し ，一つ以上の信号線に マルチプ レ クサを付加し ，_SoCの外部入力からの経路を実現す れば 十分である．_msを用いて ，_Y

q

c,k^{を次の式で 表現}

する． Y_c,k^q =

s∈S

ms (5)

次に_Yc,kについて 考え る．_{QJ= φ}のとき，_GJc,k は 正当化部分グ ラフであ る．_{QJ = φ|} のとき，_QJ の すべての要素に 関し て_GJ

c,k を 連続可制御とすれば ， GJ_c,kは 正当化部分グ ラフとなる．これ より，_Yc,k は Y_c,k^q を用いることで 以下の式で 表現できる．

Yc,k=







q∈Q_J

Y_c,k^q (QJ= φ| ^のとき)

1 (QJ= φ^のとき)

(6)

次に_Ycについて 考え る．_cが 連続可制御であるとは ， KJ_cの一つ以上の要素に対し て連続可制御であること

をいう．これ より，Yc^はYc,kを用いることで 以下の 式で 表現できる．

Yc= ^

k∈K_Jc

Yc,k (7)

以上より，すべてのコアが 連続可制御であるための必 要十分条件は

c∈C

Yc^>_{= 1} (8)

とな る．連続可検査_DFTの 最適化目標は ，付加する ハード ウェア量最小である．これは ，マルチプレ クサ が 付加され る信号線のビ ットの合計を最小化すること と 等 価で あ るので ，以 下の 関 数で 表 現 す るこ とが で きる．



e_i∈E_net

xe_i· width(ei) (9)

ただし ，_width(ei)は 信号線eiのビ ット 幅を表す． コアの 連続可制御性のための_DFTは ，条件式₍₈₎， 目的関数₍₉₎とする整数計画問題に 帰着することがで きる．この式₍₈₎，₍₉₎で表現され る整数計画問題を解 くことで ，マルチプレ クサを付加すべき信号線の集合 が 得られ る．この 集合の各要素ei^{に 対し て ，図} 8^の ようにマルチプレ クサを 用いて ，外部入力からの経路 を実現することで ，最小のハード ウェア量ですべての コアを連続可制御にすることができる．

4. 2. 2 コアの連続可観測性のための_DFT 具体的には以下の方法で 各コアに 対し て伝搬初期グ ラフ，伝搬中間グ ラフ，伝搬中間部分グ ラフを生成す る．その伝搬中間部分グ ラフが 伝搬部分グ ラフとなる ための 条件式を 導出し ，整数計画問題を 解くことで ，

図8 連続可制御性のためのマルチプレ クサ Fig. 8 Insert of multiplexer for consecutive

controllability.

最小の付加ハード ウェアですべてのコアを連続可観測 とする．

［_Step1］ 伝搬初期グ ラフの生成

コ ア 接続グ ラフ _Gか ら ，コ ア _{c∈ C} の 出 力 端子 o∈ Vout に 関する伝搬初期グ ラフ_GPc,o を 以下の 方 法で 生成する．図₉に ，図₄のコア接続グ ラフGに 対する，コア_c1の出 力端子_v2に 関する伝搬初期グ ラフ_GPc1,v2 を示す．

はじ めに ，_Gから_cの正当化部分グ ラフ _GJc を除 去する．更に ，_Gから_{P A}または_{P O}のラベルをも つ枝のみを 残し ，他の 枝を除去する．次に ，_c内の 連 続透明経路の枝をGから 除去し ，oをソースとする． その ソ ー スか ら 有 向 辺を たど るこ とで 到 達 可 能と な る枝 ，頂点の 集合を_cの_oに 関する伝搬初期グ ラフ GPc,o^{とする．G}Pc,o^{にoも含む．}

GPc,o に 含 まれ るコ ア の 集 合を_APc,o と す る ．コ アa∈ AP_c,o^{に 対し ，}GP_c,oに 含まれ る形状の集合を BP_a ^とする．a∈ AP_c,o^{に 対する}BP_a^{の直積集合を}

KPc,o=

a∈A_Pc,o

BP_a1

= BP_a1× BP_a2× BP_a3× . . . .

とする．伝搬初期グ ラフでは ，各コアには 複数の形状 識別番号が 存在し ，連続透明性が 実現され ていない．

［_Step2］ 伝搬中間グ ラフの生成

GP_c,o ^と k∈ KP_c,o ^{から ，}c^の o^{に 関する伝搬中} 間グ ラフ_GP

c,o,kを以下の方法で生成する．図₁₀に ，

図₉の_GP

c1,v2に対する，伝搬中間グ ラフ_GP

c1,v2,k1

を示す．

はじ めに ，AP_c,oに 属するコアにおいて ，kに 対応 する 形状を 選択し ，各コアの 連続透明性を 実現する ． このとき，新たにソースとなった頂点からのみ到達可

図9 伝搬初期グ ラフG_Pc1,v2 Fig. 9 Propagation initial graph.

能な枝，頂点をGP_c,oから除去することで得られ るグ ラフを 伝搬中間グ ラフGP_c,o,k^とする．GP_c,o,k^はG に 対し ，各頂点はすべての入射枝を含み，各コアにつ いて 一つの 形状に 関する枝のみを 残し た部分グ ラフで ある．

［_Step3］ 伝搬中間部分グ ラフの生成

GP_c,o,k ^{に 対し ，各頂点が}P Oのラベルをもつ出射

枝をただ 一つもつという条件のもとで ，_oから 到達可 能な枝，頂点からなる部分グ ラフ_G

f

P_c,o,k^{を伝搬中間}

部分グラフとし ，伝搬中間部分グ ラフの集合を_G^F_P

c,o,k

と す る ．_G

f

P_c,o,k ^{に は P O} の ラベ ル を もつ 出 射 枝を 二つ 以 上もつ 頂 点は 存在し な い ．図_{10 (a)}に 対す る G^f_P

c1,v2,k1 ^{を図10 (b)に 示す．}

G^f_P

c,o,k の うち，以下のいずれ かの 条件に 当ては ま

る頂点_qの集合を_QP とする．

（₁）_qはシン クであり，_{VP O}に 属さない

（₂）qを含む閉路が 存在 QP ^はG^f_P

c,o,kの頂点の中で ，伝搬部分グ ラフの条件

（［ 定義₄］）にあては まらない頂点の集合となる．

［_Step4］ 整数計画問題への帰着

コア _cの 出力端子 _oに 関する連続可観測性の 評価 変数とし て ，以下の整数変数を定義する．

Zc,o ^：c^のoに 関する連続可観測性 Zc,o,k^：c^のo^{の形状集合}k^{に 関する}

連続可観測性 Z_c,o,k^{f,q ：}G^f_P

c,o,k ^{におけ る頂点qに 関する}

連続可観測性

各変数は₁以上のとき，その性質を満たすものとする．

図10 (a) G_Pc1,v2,k1, (b) G^f

Pc1,v2,k1

Fig. 10 Propagation middle graph.

式₍₂₎を用いて Z_c,o,k^f,q をqが 満たす条件によって， 以下の（₁），（₂）ように 定義する．qが（₁），（₂） の 条 件を 同 時に 満た す 場 合は ，各 条 件で 定 義され る Y_c,k^{q の積を} q^のY_c,k^{q とし て定義する．}

（₁）_qが_G

f

P_c,o,k^{のシン クであり，VP Oに属さな}

い場合

qとo間の単純経路の集合をSとする．qに関し て G^f_P

c,o,kを 連続可観測とするためには ，_Sに 属する各

単純経路_sに対し て，_sの一つ以上の信号線から_SoC の外部出力までの経路をマルチプレ クサを 用いて 実現 すれば 十分である．_sに 存在する信号線に 対応する枝 の集合を Es^{とすると ，}sに 対し ，一つ以上の信号線 から_SoCの 外 部出力まで の 経 路を マル チプ レ クサを 用いて実現するとは ，以下の式で 表され る_m

′ s^が1^以 上となることをいう．

m^′_s= ^

e_i∈Es

xe_i (10)

この_m

′

s^{を用いて，}Y_c,k^{q を次の式で表現する．}m^′s^を

用いて ，_Z

f,q

c,o,k を次の式で 表現する．

Z_c,o,k^f,q =

s∈S

m^′s (11)

（₂）_qを含む閉路が 存在する場合 G^f_P

c,o,k^{において ，qを含む閉路の集合をSとする．}

q^{に 関し て}G^f_P

c,o,k を連続可観測とするためには ，_S

に属する各閉路_sに対し ，一つ以上の信号線から_SoC の外部出力への経路をマルチプレ クサを 用いて実現す れば 十分である ．_m

′

s ^{を 用いて ，}Z^f,q_c,o,k^{を 次の 式で 表} 現する．

Z_c,o,k^f,q =

s∈S

m^′s (12)

次 に _Z

f

c,o,k に つ い て 考 え る ．_{QP = φ} の と き ， G^f_P

c,o,k

は 伝 搬 部 分グ ラフで あ る ．_{QP = φ|} の と き ， QP の すべ て の 要 素に 関し て G^f_P

c,o,k を 連 続 可 観 測 とすれば ，G^f_P

c,o,k は 伝搬部分グ ラフとな る．これ よ

り，_Z

f c,o,k^はZ

f,q

c,o,kを用いることで以下の式で表現で

きる．

Z_c,o,k^f =







q∈Q_P

Z_c,o,k^f,q (QP = φ| ^のとき)

1 (QP = φ^のとき) (13)

G^F_Pc,o,k ^{に 属する一つ以上の}G^f_P

c,o,k ^{に 関し て 連続}

可観測で あれば ，_GP

c,o,k は 連続可観測で あ る．これ

より，Zc,o,k^はZ_c,o,k^f を用いることで以下の式で表現 できる．

Zc,o,k= ^

G^f

Pc,o,k^∈GFPc,o,k

Z_c,o,k^f (14)

次にZc,o^{に ついて考え る．}cのoが 連続可観測で あるとは ，KP_c,o の一つ以上の要素に 対し て連続可観 測で あ るこ とをい う．これ より，_Zc,o は_Zc,o,k を 用 いることで 以下の式で 表現できる．

Zc,o= ^

k∈K_Pc,o

Zc,o,k (15)

コア_cの出力端子に対応する頂点の集合を_Ocとす ると ，すべてのコアが 連続可観測であるための必要十 分条件は

c∈C

o∈O_c

Zc,o

>= 1 ⁽¹⁶⁾

とな る．連続可検査_DFTの 最適化目標は ，付加する ハード ウェア量最小である．これは ，マルチプレ クサ を 用いて_SoCの 外部出力まで の 経路を 実現すべ き信 号線のビ ットの合計を最小化することと等価であるの で ，以下の関数で 表現することができる．



e_i∈Enet

xe_i· width(ei) (17)

ただし ，_width(ei)は 信号線_eiのビ ット 幅を表す． コアの連続可観測性のための_DFTは ，条件式₍₁₆₎， 目的関数₍₁₇₎と する整数計画問題に 帰着することが できる．この式₍₁₆₎，₍₁₇₎で表現され る整数計画問題 を解くことで ，マルチプレ クサを 用いて 外部出力への 経路を付加すべき信号線の集合が 得られ る．この集合

図11 連続可観測性のためのマルチプレ クサ Fig. 11 Insert of multiplexer for consecutive

obserbability.

の各要素ei^{に対し て，図}11のようにマルチプレ クサ を用いて ，外部出力への経路を実現することで ，最小 のハード ウェア量ですべてのコアを連続可観測にする ことができる．

4. 2. 3 信号線の連続可制御性，連続可観測性のた めの_DFT

連続可制御性のため の_DFTは4.2.1，連続可観測 性のための_DFTは4.2.2と同様の手続きで 行うこと ができる．

5. む す び

本論文では 連続可検査性に 基づ く_SoCのテ スト 容 易化設計法を提案し た ．本論文で 提案し た連続可検査 性を満たす_SoCは ，すべてのコアとすべての信号線に 対する連続テストアクセスが可能である．これにより， 各コアに提供され る任意のテスト 系列を_SoCの外部入 力から 実動作速度で 連続し てコアへ印加し ，その応答 を_SoCの外部出力で連続し て観測することが 可能とな り，コア単体に対し てテスト 可能な故障は ，_SoCに組 み込まれた後でもテスト 可能であることが 保証できる． 信号線も同様に ，任意のテ スト 系列を実動作速度で 連 続し て_SoC外部入力から 印加し ，その 応答を_SoCの 外部出力で 連続し て観測することが 可能である．

コアの入力端子から 出力端子へマルチプレ クサを 用 いてバ イパス経路を付加することにより，コア内部を 変更することなく連続透明性を実現可能であるが ，各 端子ご とに マルチプレ クサが 必要となり，面積オーバ ヘッド が 大きくなる．今後の課題とし ては ，コアの内 部構造や通常動作を利用し ，低い面積オーバヘッド で 連続透明性を実現するコアに対するテ スト 容易化設計 法の開発が 挙げ られ る．また，本論文ではコアのテ ス ト 方式とし て外部テ スト 方式のみを 対象とし たが ，組 込み自己テ スト 可能なコアを含む場合への拡張も今後 の課題である．

謝辞 本研究に 際し ，多くの貴重な意見を頂いた 大 阪大学の増澤利光教授，本学の井上美智子助教授，大 竹哲史助手はじ め情報論理学講座の諸氏に 深く感謝し ます．本研究は 一部，奈良先端科学技術大学院大学支 援財団教育研究活動支援による研究助成，及び 新エネ ルギ ー・産業技術総合開発機構（_NEDO）から 半導体 理工学研 究セン ター（_STARC）に 委託され た「_SoC 先端設計技術の研究開発 」の一部とし て奈良先端科学 技術大学院大学に 再委託され 実施され ています．

文 献

[1] Y. Zorian, E.J. Marinissen, and S. Dey, “Testing embedded-core based system chips,” Proc. 1998 Int. Test Conf., pp.130–143, Oct. 1998.

[2] S. Bhatia, T. Gheewala, and P. Varma, “A unify- ing methodology for intellectual property and custom logic testing,” Proc. 1996 Int. Test Conf., pp.639–648, Oct. 1996.

[3] T. Ono, K. Wakui, H. Hikima, Y. Nakamura, and M. Yoshida, “Integrated and automated design-for- testability implementation for cell-based ICs,” Proc. 6th Asian Test Symp., pp.122–125, Nov. 1997. [4] N.A. Touba and B. Pouya, “Testing embedded cores

using partial isolation rings,” Proc. 15th VLSI Test Symp., pp.10–16, May 1997.

[5] L. Whetsel, “An IEEE 1149.1 based test access ar- chitecture for ICs with embedded cores,” Proc. 1997 Int. Test Conf., pp.69–78, Nov. 1997.

[6] M. Nourani and C.A. Papachristou, “Structural fault testing of embedded cores using pipelining,” Journal of Electronic Testing: Theory and Applications 15, pp.129–144, 1999.

[7] I. Ghosh, N.K. Jha, and S. Dey, “A low overhead de- sign for testability and test generation technique for core-based systems-on-a-chip,” IEEE Trans. CAD, vol.18, no.11, p.1661, Nov. 1999.

[8] I. Ghosh, S. Dey, and N.K. Jha, “A fast and low cost testing technique for core-based system-on- chip,” Proc. 35th Design Automation Conf., pp.542– 547, June 1998.

（ 平成13 年 5 月 2 日受付，9 月 4 日再受付）

米田 友和 （ 学生員 ）

平10 阪大・工・情報システム卒．平 13 奈良先端科学技術大学院大学博士前期課程 了．現在，同博士後期課程に 在学中．現在， テスト 容易化設計の研究に 従事．

藤原 秀雄 （ 正員：フェロー ） 昭44 阪大・工・電子卒．昭 49 同大大学 院博士課程了．同大・工・電子助手，明治 大・工・電子通信助教授，情報科学教授を経 て，現在奈良先端大・情報科学教授．昭56 ウォータールー大客員助教授．昭59 マッギ ル大客員準教授．論理設計論，フォールト トレ ラン ス，設計自動化，テスト 容易化設計，テスト 生成，並 列処理，計算複雑度に関する研究に従事．著書「Logic Testing and Design for Testability」（MIT Press）など ．大川出版 賞．IEEE Computer Society Meritorious Service Award． 情報 処理学 会会員 ，IEEE Computer Society Golden Core Member，IEEE Fellow．