J71 j IEICE 1999 2 最近の更新履歴 Hideo Fujiwara J71 j IEICE 1999 2

弱可検査性のための設計目標抽出を 利用し たデ ータパ ス高位合成

東村 剛嗣

井上美智子

藤原 秀雄

High-Level Synthesis for Weakly Testable Data Paths Using Design Objective

Extraction

Takeshi HIGASHIMURA^†∗, Michiko INOUE^†, and Hideo FUJIWARA^†

あらまし 非スキャン 設計のためのテ スト 容易性尺度である弱可検査性を考慮し たデ ータパス高位合成手法を 提案する．筆者らはこれ まで ，弱可検査なデ ータパスの高位合成に 関し ，合成後のデ ータパスが 弱可検査となる ような，ハード ウェア 要素共有に 対する制約に 関する十分性を示し ，この十分性を満たす制約を設計目標とし て 考慮する高位合成法を提案し ている．本研究では ，まず 合成前の動作記述であるデ ータフローグ ラフから 合成後 のデ ータパスが 弱可検査となるための十分条件である設計目標の抽出手法を提案し ，高位合成の主な処理である スケジューリング，バ インデ ィングに 関し て ，設計目標と面積をともに 考慮する発見的手法を 提案する．提案し た手法を繰り返し 適用することで時間制約のもとで面積が 小さくかつ弱可検査なデータパスを合成する手法を提 案する．

キーワード 高位合成，弱可検査性，デ ータフローグ ラフ，デ ータパス，_{VLSI テスト}

1. ま え がき

近年の_VLSIの高集積化，大規模化に 伴い，回路の テ ストは ますます重要かつ困難な問題となってきてい る．テストのための費用を削減する有効な手段とし て， 設計の初期段階からテ スト 容易性を考慮することが 考 えられ る．また ，_VLSIの 大規模化に 対応で きる支援 技術とし て ，抽象度の高い動作記述からレジ スタ転送 レ ベル（_RTL）の回路を合成する高位合成の研究が 盛 んに 行われている．本論文では ，テ スト 容易性を考慮 し た高位合成法を考察する．

テ スト 容易性とし て ，本論文ではデ ータパ スの弱可 検査性_[1]を考える．弱可検査なデータパスでは，デー タパス中の各レジ スタに 対し て ，外部入力から何らか の値が 設定できること ，外部出力で 何らかの値が 観測 できることが 保証され る．このテ スト 容易性は順序回 路テ スト 生成アルゴ リズム（_ATPG）を用いてテ スト 生成を行うデータパスの非スキャン 設計のためのもの である．

順序回路_ATPGのための テ スト 容易性を 考慮し た

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

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

∗

現在，日本IBM株式会社

高 位 合 成 法とし ては ，これ まで 部 分 スキャン 設 計の ための手法が 多く提案され ている_[5]∼_[9]．これらは ， デ ータパ ス中のフ ィード バックループ を スキャンレジ スタを 用いて切断し ，テ スト 容易性を向上させるもの あり，スキャンレジ スタ数を最小化するための多くの 発見的手法が 提案され ている．し かし ，スキャン 設計 では ，面積オーバヘッド が 大きい，テ スト 実行時間が 長い，回路の通常動作時のクロック速度でのテスト 実 行（_at-speedテ スト ）が で きな いなど の 問題が あ り， 近年，スキャン 設計を行わないテ スト 容易化設計法が 提案され ている_{[1], [10]}．

筆者らはこれ まで ，_RTLデ ータパスの非スキャン設 計のためのテスト 容易性尺度とし て弱可検査性を提案 し ，弱可検査なデ ータパ スが 高故障検出効率を得るこ とを実験的に示し ている．また，小さな ハード ウェア オーバヘッド で 与えられたデ ータパスを弱可検査にす るテ スト 容易化設計法を提案し ている_[1]．

文献_[2]では ，動作記述であ るデ ータフ ローグ ラフ

（_DFG）を 解析し ，_DFG上で 可制御な 要 素と 可制御 でない要素をデ ータパスで ハード ウェア共有させるこ とでデ ー タ パ ス 全 体を 弱 可 検 査に す る 手 法を 提 案し ている．この中では ，合成後のデ ータパスが 弱可検査 となるために十分なハード ウェア要素共有に 関する条

D– Vol. J82–D– No. 2 pp. 401–409 1999 2 401

電子情報通信学会論文誌’99/2 Vol. J82–D–I No. 2

件が 示され ，更に 高位合成の基本的な処理であるスケ ジューリング，バ インデ ィングに 関し ，弱可検査性の ための十分条件を設計目標とし て考慮する手法を提案 し ている．しかし ，設計目標の具体的な抽出法は 提案 し ていなか った．

本論文では ，まず，_DFGから 設計目標を 抽出する 方法を新たに提案する．更に ，高位合成手法について は 文献_[2]で 提案され た スケジュー リング 手法とバ イ ンデ ィング 手法を改善し ，動作速度の制約下で設計目 標と 演算器，レ ジ スタなど の リソー スの 個数（ 面積 ） をともに 考慮する発見的手法を提案する．本論文で 提 案する手法では ，設計目標の抽出と抽出され た設計目 標を設計制約とする合成を繰り返し 行うことによって， 動作速度，リソース数，弱可検査性を設計制約とし て 同時に 考慮し ，動作速度，リソー ス数の最適性を損な わず に テ スト 容 易 性の 向 上を 行 うこ と を 目 的とし て いる．

2. 諸 定 義

合成前の回路の動作記述であるデ ータフローグ ラフ 及び 合成後のデ ータパスの弱可検査性_{[1], [2]}について 定義する．

2. 1 データフローグ ラフ（DFG）

デ ー タ フ ロ ーグ ラ フ（_DFG）は 有 向グ ラ フ _{G =} (V, E)で あ る．節点は ，外部入力，外部出力 ，演算，

変数，又は ，遅延である．遅延は ，外部入力の系列に 対し 繰り返し て処理を行うような動作を記述する際に ， ある入力に 対し て計算され た値を次の入力に 対する処 理で 用いるときに 値を保持することを意味する．有向 枝_{(vi, vj) ∈ E} は 演算あるいは 遅延_viが 変数 _vj を 生成する，変数_viを演算_vjが 利用する，又は演算_vi の結果を遅延vjが 保持することを表す．_DFGに対し て ，外部入力節点を除く任意の節点はそれに 入射する 辺をもつこと，任意の変数から 外部出力までの経路が 存在することを 仮定する ．図₁に3rd Lattice Wave Filter^のDFG^{を示す．節点}PI^，PO^{はそれぞれ 外部}

入力，外部出力を，＊，₊でラベル 付けされた節点は ， それぞれ 乗算，加算を ，節点_Dは 遅延を 表し ている ． また ，黒で 示し た節点は 変数を表し ている．

2. 2 データパスの弱可検査性

デ ータパスは外部入力，外部出力，レジ スタ，マル チプレ クサ，演算器からなるハード ウェア要素と ，こ れらを 接続する接続信号線から 構成され る

（ 注_1）

．ハー ド ウェア要素_H1の出力とハード ウェア要素_H2の入

図1 3rd lattice wave filter の DFG Fig. 1 DFG of 3rd lattice wave filter.

力_X 間に 接 続 信号 線が あ る 場 合 ，_{H1 → X}，又は ， H1 → H2 と 表記する．また ，演算器_M の 入力の集 合を_INM と表し ，演算器_M が _M の入力_X の値 をそのまま出力する関数をもつとき，_X をスルー可能 入力と呼び ，_thru(X)と記す．

デ ータパ ス中の各ハード ウェア要素について，弱可 制御性，弱可観測性，及びデ ータパスについて弱可検 査性を定義する．直観的には ，ハード ウェア要素_Hの 出力に ，何らかの 値を 正当化するこ とが で きると き ， H は 弱可制御であるといい ，また ，H の出力の何ら

かの値は外部出力に伝搬することができるとき，_H は 弱可観測であるという．

［ 定義₁］デ ータパスの弱可制御性_[1]

弱可制御なハード ウェア要素の集合は 以下の条件を 満たすハード ウェア要素の最小集合_Hwcである．

（₁）任意の外部入力_{P I}は 弱可制御である．すな わち，_{P I∈ Hwc}．

（₂）任意のレジ スタ，又は，マルチプレ クサ_Hは， ある入力が 弱可制御なハード ウェアと接続し ていれば 弱 可 制 御で あ る ．すな わ ち ，_{∃Hwc ∈ Hwc[ Hwc →} H] ⇒ H ∈ Hwc^．

（₃）任 意 の 演 算 器 _M は ，す べ て の 入 力 ，又 は ，あ る ス ル ー 可 能 入 力 が 弱 可 制 御 な ハ ード ウェ ア 要 素 と 接 続し て い れ ば 弱 可 制 御 で あ る ．す な わ ち ，_{(∀X ∈ INM [∃Hwc ∈ Hwc, Hwc → X]) ∨}

（ 注1）：定数は 演算器等の組 合せモジ ュールに 含まれ ると 考え ，ハード ウェ ア要素と 考えな い．

(∃X ∈ INM [thru(X) ∧ ∃Hwc∈ Hwc, Hwc→ X])

⇒ M ∈ Hwc. _✷

［ 定義₂］デ ータパスの弱可観測性_[1]

弱可観測なハード ウェア要素の集合は 以下の条件を 満たすハード ウェア 要素の 最小集合_Hwoであ る．演 算器の集合を_Mとする．

（₁）任意の 外部出 力_{P O} は 弱可観測で あ る ．す なわち，_{P O∈ Hwo}．

（₂）任 意 の ハ ード ウェア 要 素 _H に 対し ，そ の 出 力が 演 算 器 以 外の 弱 可 観 測な ハ ード ウェア 要 素と 接 続し て いれ ば ，_H は 弱 可 観 測で あ る ．すな わ ち ，

∃Hwo∈ (Hwo− M)[ H → Hwo] ⇒ H ∈ Hwo^．

（₃）任意の ハード ウェア 要素_H に 対し ，その 出 力が 弱可観測な演算器_M の入力_X と接続し ており， X が スルー可能入力，又は ，_X 以外の _M の入力が すべて 弱可 制御で あれば ，_H は 弱可 観測で あ る ．す なわ ち ，_{∃M ∈ Hwo}∩ M [∃X ∈ INM [H → X]∧ (∀X^′ ∈ (INM− X)[∃Hwc ∈ Hwc [Hwc → X^′]] ∨

thru(X))] ⇒ H ∈ Hwo. _✷

［ 定義₃］デ ータパスの弱可検査性_[1]

デ ー タ パ ス 中の す べ て のレ ジ スタが 弱 可 制 御 ，か つ，弱可観測ならば ，そのデ ータパスは弱可検査であ

る． _✷

デ ータパ スに対し ，任意のレジ スタから 外部出力ま での経路が 存在すると仮定する．このとき，定義より 明らかに ，デ ータパス中のすべてのレジ スタが 弱可制 御ならば ，すべてのレジ スタは 弱可観測となり，デ ー タパスは弱可検査である．よって ，以下ではレジ スタ の弱可制御性のみを 考え る．

2. 3 高 位合 成

デ ータパス高位合成とは ，動作記述である_DFGを RTLの記述であ るデ ータパスに変換することであ る．

具体的には 以下の部分問題を解く．

（₁）スケジュー リング ：_DFG中の 各 演算を それ が 実行され る制御ステップ に 割り当てる．

（₂）バ インデ ィング ：_DFG中の演算を演算器に ， 変数をレジ スタに 割り当てる．演算器とレジ スタ間の 相互接続関係を決定し ，必要があれば マルチプレ クサ の割当てを行う．

3. 弱可検査性を考慮し た高位合成

3. 1 概 略

本論文では ，与えられ た_DFGと 動作速度に 関する 時間制約から ，少ないハード ウェアで ，かつ弱可検査

図2 弱可検査なデ ータパスの合成

Fig. 2 High-level synthesis for weakly testable data path.

なデ ータパ スを実現する高位合成法を提案する．ここ では ，簡単のため ，各演算の実行遅延は₁制御ステッ プ とする．また，ある演算に割り当てることので きる 演算器の種類は 一意に 決定できるものとし ，各遅延に はそれぞれ 専用のレジ スタを割り当てる．デ ータパス を構成するハード ウェア要素の うち演算器とレジ スタ を リソースと呼ぶ．デ ータパスの面積は ，それに 含ま れ るリソースに要する面積に支配され ると考え ，以降 では 各リソース数を最小にすることを考え る．

本手法のフローを 図₂に 示し ，その 概要を 述べ る． まず 最 初に 必 要な 各 リソー ス 数を 見 積も る ．これ に は 時 間 制 約の も とで リソ ー ス 数を 最 小に す る 既 存の スケジ ューリング 法であるフォースデ ィレ クテ ィッド 法_[3]（_FD法 ）を利用する．スケジュールされた_DFG

（_SDFG）に 対し ては ，ハード ウェア 要素の 各型に 対 し ，₁制御ステップ で 同時に 必要とされ る個数の 最大 値が ，その_SDFGから合成され るデ ータパスでの，そ の型のハード ウェア要素の必要最小数である．

次に ，合成後のデ ータパ スが 弱可検査となるための リソー ス共有に 関する十分条件であ る設計目標_[2]を DFGから 抽出する ．ここでは ，設計目標の 実現可能

性を表す評価尺度を導入し ，評価値の高い順に設計目 標を抽出する．

次に ，抽 出され た 設 計 目 標を 設 計 制 約と す る スケ ジューリング，バ インデ ィング を 行 う．スケジ ューリ

電子情報通信学会論文誌’99/2 Vol. J82–D–I No. 2

ング 完了後とバ インデ ィング 完了後に ，それぞれ 必要 な リソース数を求め ，先に 求めた見積り値を超え る場 合には ，再び 設計目標を 抽出する．ただし ，このバッ クト ラックの回数には 上限値を設け，上限値を超え る 場合は ，設計目標から 要素をいくつか 削除し ，縮小し た割当て情報に 対し て合成を 行う．合成され たデ ータ パスが 弱可検査でない場合は ，文献_[1]で 提案され た ， テ スト 容易化設計手法を用いてデ ータパスを弱可検査 にする．以下では ，まず，設計目標を定義し ，設計目 標の抽 出，スケジュー リング，バ インデ ィング，設計 目標の縮小を説明する．

3. 2 設 計目 標

DFGの 要素に 対し て ，デ ータパ スのハード ウェア

要素と 同様の 弱 可制御 性を 考え る ．すな わ ち ，_DFG の 要 素に 外部入力から 何らか の 値を 設定で き ると き ， その 要 素は 弱可 制御で あ ると す る ．このと き ，_DFG の要素が 弱可制御であれば ，その要素が 割り当てられ た リソースも必ず 弱可制御とな る．また ，_DFGのあ る要素が 弱可制御であれば ，その要素と リソースを共 有する要素もまた弱可制御であると考え る．リソース の共有に 関するあ る条件の もとで ，_DFGのすべての 変数節点が 弱可制御であれば ，その条件を満たすデ ー タパ スのすべて のレ ジ スタは すべ て 弱可制御とな り， デ ータパ スは弱可検査となる．このよ うな，リソース の共有に 関する弱可検査性のための十分条件を設計目 標といい以下のよ うに 定義する_[2]．

割り当てられ るリソースの型が 同一である演算又は 変数からなる集合を共有集合と呼ぶ．また ，共有集合 の集合を割当て情報と呼ぶ ．割当て情報は ，それに 属 する各共有集合に 対し ，共有集合内のすべての要素が 同じ 演算器又はレジ スタを共有する条件を表す．ある 割当て 情報に 対し て ，ある_DFGの要素が 二つ以上の 共有集合に 属するならば ，それらは 一つの 共有集合に すべきである．このことから ，割当て情報に 属する共 有集合は 互いに 素であるとする．

［ 定義₄］_DFGの弱可制御性_[2]

DFGG = (V, E)^{と割当て情報}B^{に対し ，以下の条} 件を満たす節点の最小集合を_Gwcとする．

（₁）任意の 外部入力_Ig は 弱可制御である ．すな わち，_{Ig ∈ Gwc}．

（₂）任意の節点_vに対し ，入射辺で隣接するすべ ての 節 点が 弱可制 御で あれば ，_vは 弱可制 御で あ る ． すなわち，{u ∈ V |(u, v) ∈ E}⊂_=Gwc⇒ v ∈ Gwc.

（₃）割当て 情報_Bに 属するあ る 共有集合 _B に ，

弱可制御な 要素が 存在すれば B に 属するすべての 要 素も弱可制御である．すなわち，∃B ∈ B[∃v ∈ B[v ∈ Gwc] ⇒ B⊂_=Gwc.

このとき，_{g∈ Gwc}なる要素_gは 弱可制御である．

✷

［ 定義₅］_DFGの弱可検査性_[2]

DFG G^{と 割当て 情報}B^{に 対し ，}G^{のすべて の 変} 数節点が 弱可制御であ ると き，₂項組_{(G, B)}は 弱可

検査であるという． _✷

DFG G^{に対し ，}(G, B)が弱可検査となる割当て情 報_Bを 満た すデ ータパ スは 必ず 弱可検査とな る．こ のよ うに ，合成後のデ ータパスが 弱可検査となるため の十分条件である割当て情報を設計目標と呼ぶ．

3. 3 設計目標の抽出

一般に ，与えられた_DFGに 対し て設計目標とな る ような割当て情報は 複数存在する．リソース数を最小 に 抑えながら弱可検査性を達成するには ，実現され や すい設計目標を抽出する必要がある．本論文では ，設 計目標の実現の容易さを 示す尺度である重複可能度を 導入し ，重複可能度の小さい，すなわち，実現の容易 な設計目標を順に 抽出する発見的手法を提案する．

3. 3. 1 割当て情報の重複可能度

2^{演算，又は}2変数が リソースを共有するためには ，

それらが 同じ 制御ステップ を利用し ないことが 必要と なる．ここでは ，時間制約から 演算，変数が 割り当て 可能な制御ステップ の範囲を求め ，同じ 制御ステップ を利用する可能性を考え る．

時間制約及びデ ータの依存関係を守りながら ，_DFG 上の演算をできるだけ 早い時刻の制御ステップ へ割り 当てるスケジ ューリング（_ASAP）と ，できるだけ 遅 い時刻の制御ステップ へ割り当てるスケジ ューリング

（_ALAP）から ，演算が 実行可能な 制御 ステップ の 範 囲が 求められ る．_ASAPで 割り当てられ る制御ステッ プ から_ALAPで 割り当てられ る制御ステップ まで を 演算の割当て可能範囲と呼ぶ．ある変数が 生成され る 制御ステップ（ 生成時刻 ）から ，その 変数が 最後に 使 用され る制御ステップ（ 消滅時刻 ）までの範囲をその 変数のラ イフタ イムという．ただし ，変数が 生成され る制御ステップ とは ，その変数を生成する演算が 実行 され た次の制御ステップ とする．また ，_ASAPによっ て 求まるラ イフ タ イムを _LTASAP，_ALAPに よって 求まるラ イフタ イムを_LTALAP と表す．_LTASAP の 生成時刻から ，_LTALAP の消滅時刻までを変数の割当 て可能範囲と呼ぶ．

2演算あるいは 変数が ，同じ 制御ステップ に 割り当

てられ る可能性を 重複可能性と 呼ぶ ．₂演算に 関する 重複可能性は ，割当て 可能範囲が 重複すれば₁，重複 し なければ₀である．ただし ，両₂演算の割当て可能 範囲の大きさがともに₁で重複する場合は_∞とする． 2変数に 関する重複可能性は ，割当て可能範囲が 重複

すれば₁，割当て可能範囲が 重複し なければ₀である． ただし ，両₂変数それぞれ の _LTASAP，_LTALAP の 四つのライフタイムに共通の重複部分があれば ，_∞と する．重複可能性の 値は ，₂演算又は₂変数の 利用す る制御ステップ が ，₁のと き重複する可能性があ るこ と，₀のとき必ず重複し ないこと，_∞のとき必ず重複 することを表す．

共 有 集 合 _Bi に 対し て ，_Bi 中 の す べ て の 要 素 対 {vp, vq}⊂₌Biの重複可能性の和を共有集合の重複可能

度とする．また，割当て情報中のすべての共有集合の 重複可能度の和を割当て情報の重複可能度と呼ぶ．

［ 例 ］ 演 算 ₁，₂，₃ に 対 し て ，割 当 て 可 能 範 囲 が それ ぞ れ ，_{[1, 3]}，_{[2, 4]}，_{[4, 5]} で あ る と す る ．変 数 _a，_b，_c に 対 し て ，割 当 て 可 能 範 囲 が そ れ ぞ れ ，_{[1, 3] (LTASAP = [1, 2]}，_{LTALAP = [2, 3])}， [3, 5] (LTASAP = [3, 4],LTALAP = [4, 5])^，[4, 5] (LTASAP = [4, 5],LTALAP = [4, 5])で あ ると す る ．

このとき，演算₁，₂，演算₂，₃の重複可能性はとも に₁，演算₁，₃の重複可能性は ₀であり，共有集合 (1, 2, 3)^{の 重複可能度は} 2であ る ．また ，変数 _a，_b

の重複可能性は _1,変数_b，_cの重複可能性は _∞であ る．よって ，割当て情報{(1, 2, 3), (a, b)}^{の重複可能} 度は₃，割当て情報{(1, 2, 3), (b, c)}^{の 重複可能度は}

∞^となる．

3. 3. 2 設計目標抽出法

重複可能度が 小さい順に 設計目標を抽出する発見的 手法を提案する．まず，重複可能度が 最小の設計目標 を抽出するグ リーデ ィな発見的手法を示す．設計目標 の抽出は ，初期値が 空集合である割当て情報が 設計目 標とな るまで ，すなわ ち，割当て 情報に 対し て_DFG が 弱可検 査とな るまで ，以下に 示す 拡 大を 繰り返す． こ こで ，割 当て 情 報の 拡 大と は 以 下の いず れ か で あ る ．現在の 割当て 情報を_{B = {B1,· · · , Bi,· · · , Bm}} とする．

• ^あるBi∈ Bに 要素を追加し て ，_Bi+{v}に 置 き換え る．ここで ，_vは 現在の割当て情報に 対し て弱 可制御でなく，かつ，割り当てられ るリソースの型が Bi 中のすべての要素と同一である．

• B^{に 共有集合}(vi, vj)を追加する．ここで ，現 在の割当て情報_Bに対し ，_viは 弱可制御あり，_vjは 弱可制御でない要素である．また，_vi，_vjが 割り当て られ るリソースの型は 同一である．

可能な拡大の中から ，以下の拡大を選択する．

（₁）拡大後の重複可能度が 最小であるものを 選択 する．複数ある場合は ，

（₂）新たに 弱可制御となるリソースの型の個数が 最多であるものを 選択する．複数ある場合は ，

（₃）新し く弱可制御となる節点数が 最多であるも のの 中から 任意の拡大を選択する．

設 計 目 標 抽 出 後 ，それ に 続き く スケジ ュー リング， バ インデ ィングで リソース数見積りを 達成できない場 合，次の設計目標を抽出する．この場合，前回の抽出 での最後の拡大を取り消し て，次に 優先度の高い拡大 を行い，設計目標が 得られ るまで 拡大を繰り返す．

3. 4 スケジ ューリング

設 計 目 標を 考 慮し た スケジュー リング 法を 提 案す る．遅延節点を 削除し た無閉路な_DFGに 対するスケ ジューリング を行う．提案手法では 設計目標が 設計制 約とな るよ う_DFGを 拡張し ，次に ，この 拡 張_DFG に 対し て_FD法を拡張し た手法で スケジ ューリング を 行 う．以降，_DFG及び 拡張_DFG上の 経路の 長さを ， その 経路上に現れ る演算数とする．

設計目標中の共有集合に 属する₂要素が ハード ウェ ア要素を共有するためには，₂要素を異なる制御ステッ プ に 割り当て ることが 必要で あ る．そこで ，_DFG上 の演算間に 有向枝を追加し て，演算の実行順序に 制約 を加え ，共有集合に 属する₂要素が 必ず異なる制御ス テップ に 割り当てられ るよ うにする．各共有集合に 対 し ，以下のように 有向枝の追加を行う．

共有集合が 演算からな る場合，共有集合に 属する₂ 演 算で ，重 複 可 能 性が₁で あ る 演 算 間の 一 方の 向 き に 演 算 制 約 枝と 呼ぶ 有 向 枝を 追 加す る ．演 算 制 約 枝 (vi, vj)^{は ，演算}viが 実行され る制御ステップ より後 の制御ステップで演算_vjが 実行され ることを示し ，₂ 演算_vi，_vjは 必ず 異な る制御ステップ に 割り当てら れ る．演算制約枝の向きは 両方向を考慮する必要があ るが ，ここでは 簡単のため ，₂演算の うち，外部出力 までの最長経路長が 大きい方を始点とする．

共有集合が 変数からな る場合，共有集合に 属する₂ 変 数で ，重複 可 能 性が₁で あ る₂変 数に 対し ，一 方 の変数を利用する各演算と他方の変数を生成する演算 間に 変数制約枝と呼ぶ有向枝を追加する．変数制約枝

電子情報通信学会論文誌’99/2 Vol. J82–D–I No. 2

図3 拡張DFG Fig. 3 Extended DFG.

(vk, vl)^{は ，演算}vkが 実行され る制御ステップ 以降の

制御 ステップ で 演算_vlが 実行され ることを 示す．変 数_vkを利用する各演算と変数_vlを生成する演算間に 変数制約枝を追加すると ，_vlは_vkが 消滅し た以降に 生成され るので ，_vkと_vlは 必ず 異なる制御ステップ に 割り当てられ る．変数制約枝の向きに 関し ても，簡 単のため ，₂変数の うち，外部出力までの最長経路長 が 大きい方の変数を利用する演算が 始点となる向きと する．

［ 例 ］ 図₃に設計目標{{1,4},{b,f}}^{に対する例を示} す．演算に関する共有集合_{1,4}に 対し ては演算制約 枝（_1,4）を，変数に関する共有集合_{b,f}に対し ては 変数制約枝（_2,1）を追加する．

FD^{法では ，}DFG又は部分的にスケジュールされた DFGに 対し て ，ある 演算をある制御ステップ に 割り

当てる処理を繰り返し 行う．各繰返し では ，_ASAPと ALAPを もとに フォー スと い う 尺度を 演算と 制 御 ス

テップ の各対に 対し て計算する．本手法では ，_ASAP と_ALAPを 求め る際に ，演算制約枝 ，変数制約枝を 考慮するよ うに 拡張する ．_ASAPと_ALAPが 求まっ た後のフォースの算出方法は 同様である．

3. 5 バ インデ ィング

レジ スタバ インデ ィング，演算器バ インデ ィングで は 設計目標を最優先し て行う．演算器バ インデ ィング では 内部接続コ スト も考慮する．

まず，各遅延にそれぞれ 専用のレジ スタを 割り当て る．次に ，変数をレジ スタに 割り当てる．変数を頂点 とし ，ラ イフ タ イムが 重複し な い変 数間 ，すな わ ち ， 同一のレジ スタに 割当て可能な変数間に 辺を設けたグ ラフをレジ スタコンパテ ィビ リティグ ラフ（_RCG）と

呼ぶ ．レジ スタバ インデ ィング は ，_RCGに 対するク リーク分割とし て解くことができる．ここでは ，まず， 変数に 関する共有集合に 対し ，その共有集合に属する すべての変数をマージし て一つの頂点とする．ここで ， マージとは ，隣接する₂頂点_u，_vを一つの頂点_wに 置き換え ，u，vがともに 隣接する頂点とw間に 辺を 加え る操作である．スケジ ューリング の結果，設計目 標中の同じ 共有集合に 現れ る変数のラ イフタ イムは 必 ず 重複し ないので ，_RCGでは 同じ 共有集合内の 任意 の₂変数間に 必ず 辺が 存在する．最後に ，マージ 後の RCGに対し て最小クリーク分割_[4]を行い，分割後の

各クリークに対し ，レジ スタを割り当てる．

演算器バ インデ ィングでは ，まず，演算器の型ご と に 変 数と 同 様にし て 演 算コン パテ ィビ リテ ィグ ラフ

（_OCG）を作成する．次に ，設計目標中の演算に 関す る共有集合に 対し ，_RCGと 同様のマージ を 行 う．演 算に関する共有集合に対するマージ 後の_OCGに対し ， 以下のようにクリーク分割をし て演算器バ インデ ィン グ を行う．クリーク分割は_OCGから 極大なクリーク を逐次的に 選択することで 行う．極大クリークの選択 では ，マルチプレ クサなど の内部接続コ スト を抑え る ために ，入力又は 出力となるレジ スタを 共有するよう な演算が 同じ クリークに 属することを優先する．

3. 6 設計目標の縮小

設計目標の変更回数が 制限回数を超えた場合に 設計 目標を縮小する．ここでは ，既に 抽出され た設計目標 から ，最小個の要素を削除し て実現可能な割当て情報 を得ることを目標とする．まず，最初に 抽出され た設 計目標に 対し ，以下で 述べる縮小を行い割当て情報を 得る．ここで ，縮小とは ，設計目標に 属するある共有 集合から 要素を一つ削除することである．得られた割 当て情報に 対し 合成を行い，合成結果が リソース数見 積りを 達成できなか った場合，更に 次に 抽出され た設 計目標に 対し て縮小を試みる．これを ，リソース数見 積りを 達成するまで 繰り返す．リソース数見積りが 達 成できない場合は ，既に 縮小され た割当て情報を更に 縮小する．割当て情報が 空集合となるまで 縮小されれ ば ，見積もられた リソース数で 合成できるので ，必ず リソース数見積り内での合成が 行え る．

設計目標の縮小法を説明する．まず，縮小前の設計 目標（ 又は 割当て情報 ）に 対し て ，リソース数見積り を達成できない原因となる演算制約枝，又は 変数制約 枝を求める．このよ うな制約枝は ，リソース制約のも とで スケジ ューリング を行った場合，時間制約を超え

るスケジ ューリング 結果の原因となるような経路上に あると考えられ る．このような経路を探すために ，リ ソース制約のもとで 時間を最小化する発見的手法であ る リ スト スケジ ュー リング 法_[11]（_LS法 ）を 利 用す る．_LS法は ，リソース制約に矛盾し ない範囲で ，第₁ 制御ステップ から 順に 演算を割り当てていく．ある制 御ステップ に_DFGで 定める依存関係に 矛盾せずに 割 当て可能な演算数が ，リソース制約を超え る場合，あ る優先度に 従って ，優先度の高い演算から 順に割当て を行う．このとき ，リソー ス制約による演算間の依存 関係を表す有向枝（ 制約依存枝と呼ぶ ）をその制御ス テップ に 割り当てられ た演算から 割り当てられ なか っ た演算への向きに 挿入する．スケジ ューリング され た DFGから ，経路上のど の演算もリソー ス制約に 矛盾

し ない範囲で他の制御ステップに 割当てを変更するこ とができないようなクリティカル経路を求める．以下， 便宜上，第₁ステップ の前に 外部入力節点が 割り当て られ ，最終ステップ の後に 外部出力節点が 割り当てら れ ると考え る．具体的には ，クリテ ィカル 経路は ，外 部入力を始点とし 外部出力に至る以下の有向枝だけか らなる経路である．

• 制御ステップ の境界をたかだか 一つし か超えな い有向枝，又は ，

• 制 御 ステップ の 境 界を 二 つ 以 上 超え る 有 向 枝 (v1, v2)^であり，v1^とv2の間の制御ステップ には 必 ず_v2を終点とする制約依存枝の始点が 存在するもの ．

［ 例 ］ 図_{4 (a)}は ，時間制約₄で スケジ ューリング さ れた_DFGが ，加算器のリソース数見積り₁を達成し ていない例である．有向枝_{(3, 5)}は演算制約枝である． 変数節点は 簡単のため省略し ている．同図_(b)は 同じ DFGをリソース制約のもとで スケジューリングし ，制

約依存枝_{(4, 5)}を追加した結果である．ここで，有向枝 (3, 5)^の終点5^{は ，制約依存枝}(4, 5)^{の終点であり上}

記のクリテ ィカル 経路上の有向枝の条件を満たし てい る．この例では ，二つの 経路(P I1, 1, 3, 4, 5, 6, P O1) と (P I1, 1, 3, 5, 6, P O1)が ク リティカル 経路とな り， 演算制約枝_{(3, 5)}が リソース数見積りを達成できない 原因となる制約枝であると考えられ る．

クリテ ィカルパス経路上の制約枝に 対応する演算及 び 変数の中から ，設計目標から 削除し た場合重複可能 度が 最小となる要素を削除する．条件を満たす制約枝 がない場合は ，設計制約に現れ るすべての要素のうち， それ を削除することにより重複可能度が 最小となるも のを 削除する．

図4 スケジューリング 例：(a) 時間制約下，(b) リソース 制約下

Fig. 4 Example of scheduling: (a) under time constraint, (b) under resource constraint.

4. 実 験 結 果

提案し た 高位合成手法の 有効性を 評価す るために ， 提 案 手 法 を 高 位 合 成 シ ス テ ム の 評 価 用 ベ ン チ マ ー ク とし て 利 用 さ れ て い る₄種 類 の デ ィジ タ ル 信 号 処理プ ロセッサ3rd Lattice Wave Filter^（3rdLWF^）

（ 図₁），4th IIR Cascade Filter^（4thIIR^），4th Jau- mann Wave Filter^（4thJWF^），5th Elliptic Wave Filter^（5thEWF^）のDFGに 対する 適 用結 果を 表₁

に示す．表₁のtime constraint^{は時間制約となる制} 御ステップ 数，design objectiveは 本手法で合成し た 場合を○，設計目標抽出を行わずに合成した場合を×で 表す．_#reg，_#add，_#mulは 各_DFGの合成結果に おけるレジ スタ，加算器，乗算器の個数，_#backtrack はバックト ラックが 起こり設計目標を変更し た回数で ある．weak testabilityは 合成し たデ ータパスが 弱可 検査である場合を○，そ うでない場合を×で 表す．

ま た ，合 成し たデ ー タ パ ス（ ビ ット 幅：_{8 bit}）の VHDL^記述をMentor Graphics^{社の論理合成ツール} AutoLogic IIでゲ ートレ ベル ネット リストに 変換し ， Sunrise社の順序回路テ スト 生成ツール_TestGenを用

いてテスト生成を行った．表₁のf ault eff .^，CP U^は それぞれ ，故障検出効率，テスト生成時間を表す．使用 し た計算機は_SunUltra2（CPU: 300 MHz×2^，Mem- ory: 256 MB^{）である．}

高位合成に要する時間は ，設計目標抽出に 要する時 間を含めてすべて 数秒以内であった ．実験結果による

電子情報通信学会論文誌’99/2 Vol. J82–D–I No. 2 表1 実験 結果

Table 1 Experimental result.

circuit time design data path #back- weak fault CPU

constraint objective #reg #add #mult track testability eff.[％] [s]

3rdLWF 4 × 4 2 1 – × 23.29 17754

○ 4 2 1 0 ○ 99.88 44

5 × 4 1 1 – × 24.44 15988

○ 4 1 1 0 ○ 99.93 13

4thIIR 6 × 7 2 3 – × 24.48 36725

○ 7 2 3 0 ○ 99.74 385

8 × 7 2 2 – × 39.35 29164

○ 7 2 2 0 ○ 99.88 117

4thJWF 8 × 8 2 2 – × 18.38 33158

○ 8 2 2 1 ○ 99.93 49

11 × 8 2 1 – × 20.08 33120

○ 8 2 1 0 ○ 99.90 221

5thEWF 15 × 10 4 2 – × 15.11 60212

○ 10 4 2 0 ○ 99.38 1057

20 × 10 3 1 – × 15.55 50502

○ 10 3 1 0 ○ 99.77 30

(a) 設計目標を考慮しない場合 (b) 設計目標：{{in,c},{1,5}}

図5 合成され た3rd lattice wave filter のデータパス Fig. 5 RT-level data path of 3rd lattice wave filter.

と ，すべての回路において ，本手法により，設計目標 を抽出し ない場合と同数の演算器数及びレジ スタ数で 弱可検査性を満たす合成が 可能となっている．ほとん ど の場合において ，最初に 抽出され た設計目標を用い た合成が 可能となっており，抽出され る設計目標の実 現可能性は 高いものであると考えられ る．設計目標変 更のバックト ラックが 生じ ているのは 時間制約が₈制 御ステップ のときの_4thJWFの合成時で ，そのバック ト ラック回数は₁回のみである．

弱可検査でないデ ータパ スでは 故障検出効率が 総じ て低い値であるのに 対し ，弱可検査なデ ータパスの故

障検出効率はいずれも₉₉％台であり，テスト 容易性と し て弱可検査性の有効性が 示され ている．

よって ，本手法により，リソース数の 最適性を損な わないよ うな設計目標が 抽出され ，その 設計目標によ り，弱可検査なデ ータパ スが 合成できていることが 示 され ているといえ る．

また ，_3rdLWF（ 図₁）に 対し ，時間制約が₄制御 ステップ の場合の本手法による結果，設計目標を考慮 し ない場合の結果を図₅に示す．抽出された設計目標 は {{in,c},{1,5}}^{で あ る ．図} 5で 黒色の ハード ウェ ア 要素は 弱 可制 御な ハード ウェア 要素を 表す．また ，

A^，M^，R^（D^）でラベル 付けされたハード ウェア要素

はそれぞれ 加算器，乗算器，レジ スタを 表す． 5. む す び

本論文では ，与えられたデ ータフローグ ラフと 動作 速度に 関す る時 間制約から ，少な いハード ウェアで ， かつ弱可検査なデ ータパスを実現する高位合成法を提 案し た ．また，本論文で 提案し た高位合成手法をベン チマークに 適用し ，本手法の有効性を示し た ．

実験に 用いたベン チマーク回路では ，設計目標の縮 小を行わずに合成を行うことができたが ，設計目標の 縮小が 必要となるような規模の大きい回路での実験的 評価が 今後の 課 題で あ る ．更に ，今後の 課題とし て ， 条件分岐構造を含むコント ロールデ ータフローグ ラフ に 対する弱可検査性を考慮し た高位合成法の提案も挙 げ られ る．

謝辞 本研究に 際し ，多くの貴重な意見をいただ い た本学の増澤利光助教授，井上智生助手，並びに ，情 報論理学講座の諸氏に深く感謝し ます．本研究は一部，

（ 株 ）半導体理工学研究センター（_STARC）との共同 研究，及び ，文部省科学技術研究費補助金・基盤研究 B(2)（ 代表者：藤原秀雄 ，課題番号_09480054）の 研

究助成による．

文 献

[1] K. Takabatake, M. Inoue, T. Masuzawa, and H. Fuji- wara, “Non-scan design for testable data paths using thru operation,” Proc. Asia and South Pacific Design Automation Conf., pp.313–318, 1997.

[2] M. Inoue, K. Noda, T. Higashimura, T. Masuzawa, and H. Fujiwara, “High-Level Synthesis for Weakly Testable Data Paths,” IEICE Trans. on Information and Systems, vol.E81-D, no.7, pp.645–653, 1998. [3] P.G. Paulin and J.P. Knight, “Force-directed schedul-

ing for the behavioral synthesis of ASIC’s,” IEEE Trans. on CAD, vol.8, no.6, pp.661–679, 1989. [4] C. Tseng and D.P. Siewiorek, “Automated synthesis

of data paths in digital systems,” IEEE Trans. CAD, vol.5, no.3, pp.379–395, 1986.

[5] D.H. Lee and S.M. Reddy, “On determining scan flip- flops in partial-scan designs,” Proc. Intl. Conf. on CAD, pp.322–325, 1990.

[6] T.-C. Lee, W. Wolf, and N.K. Jha, “Behavioral syn- thesis for easy testability in data path scheduling,” Proc. Intl. Conf. on Computer Design, pp.616–619, 1992.

[7] S. Dey, M. Potkonjak, and R. Roy, “Exploiting hard- ware sharing in high-level synthesis for partial scan optimization,” Proc. Intl. Conf. on Computer-Aided- Design, pp.20–25, 1993.

[8] M. Potkonjak, S. Dey, and R. Roy, “Behavioral syn- thesis of area-efficient testable designs using inter- action between hardware sharing and partial scan,” IEEE. Trans. on CAD, vol.14, no.5, pp.1141–1154, 1995.

[9] V. Fernandez and P. Sanchez, “Partial scan high-level synthesis,” Proc. European Design and Test Conf., 1996.

[10] S. Dey and M. Potkonjak, “Non-scan design-for- testability of RT-level data paths,” Proc. Intl. Conf. on Computer-Aided-Design, pp.640–645, 1994. [11] M.C. McFarland, A.C. Parker, and R. Camposano,

“Tutorial on high-level synthesis,” Proc. Design Au- tomation Conf., pp.330–336, 1988.

（ 平成10 年 3 月 30 日受付，7 月 27 日再受付）

東村 剛嗣 （ 学生員 ）

平5 阪大・工・生産加工卒．同年（ 株 ） リコー 入社．平10 奈良先端科学技術大学 院大学博士前期課程了．同年日本IBM(株） 入社．テスト 容易化設計，高位合成の研究 に 従事．

井上美智子 （ 正員 ）

昭62 阪大・基礎工・情報卒．平 1 同大 大学院博士前期課程了．同年（ 株 ）富士通 研究所入社．平7 阪大大学院博士後期課程 了．同年奈良先端科学技術大学院大学助手， 現在に 至る．分散アルゴ リズム，グ ラフ理 論，テスト 容易化設計，高位合成の研究に 従事．工博．IEEE，情報処理学会，人工知能学会各会員．

藤原 秀雄 （ 正員 ）

昭44 阪大・工・電子卒．昭 49 同大大学 院博士課程了．阪大工学部助手，明治大理 工学部教授を経て，現在，奈良先端科学技 術大学院大学教授．論理設計，テスト 容易 化設計，テスト 生成，高位合成，フォール トトレ ラン スの研 究に 従事．著書「Logic Testing and Design for Testability」（MIT Press）など ．工 博．IEEE，情報処理学会各会員，IEEE Fellow，IEEE Golden Core Member．