博士（工学）林 世紀 学位論文題名
高速 VLSI の設計におけるメモリアクセス依存性と 多 相 ラ ッ チ の 配 置 に 関 す る 研 究
学位論文内容の要旨
ASIC需要の急増とその 基盤技術の進歩の中，近年，ASICの設計は，高速化設計，設計時間 の短縮と大規模回路設計という大きな問題を抱えている。ASICの設計は通常，複数の設計階層 に分けて考えられる。システムレベルでは，回路はCPUやメモりなどの部品で構成されている と見なす。機能レベルでは，回路は記憶素子と機能素子とにより構成されているものと見なす。
本研究はASICの設計にお いて現在多くの問題を抱えているこの2っのレベルでの設計支援に 関する研究を行ったものである。
システムレベル設計に関してはその研究が最近開始されたばかりであり，いくっかの設計技法 が個別に知られているのみである。将来のシステムレベルでの設計支援を考えた場合，設計支援 システムに求められる機能が何であるかを明かにする必要がある。
機能設計に関しては， 80年代から多くの研究がなされてきている。ASICの設計を考えた場合，
高速性に特長を持つ多相方式に着目する必要がある。従来よく用いられてきた単相方式では1つ の相信号しか用いないのに対し，多相方式では複数の相信号を用いる。これにより，より精細な タイミング制御が可能になり，高速な回路が実現される。
多相方式の同期回路を設計対象とする設計アルゴリズムに関する研究は1980年代後半に開始さ れた。ステージ分割法と呼ばれるパイプラインを設計対象とした設計手法に関する研究が行われ た。この方法はパイプラインを対象としたために，ル―プを含む回路の設計に用いることはでき ない。ASICでは，ループを持つ回路はしばしば現れるため，この欠点を無視することはできな い。
1991年には，多相方式を用いた動的回路の制御系設計ツールにっいて発表されている。機能設 計では，通常，回路をデータパスと制御部とに分離して設計が行われる。デ一夕パスはデ―夕に 処理を施し，制御部はデータパス中の各処理素子の制御を行う。上記の研究はその内の制御部の み に 関 す る 研 究 で あ り ， デ ー タ パ ス の 設 計 に 対 処 す る こ と は で き な い 。
本論 文で は，シ ステム レベル での 設計支 援シス テムに 望まれ る機 能を明 かにす ること を目的と して ，シス テム レベル 設計の 事例研 究にっ いて 述べて おり， さらに ，多 相方式 のデ一 夕パスの機 能設 計を支 援す ること を目的 として ，その ため の設計 手法に っいて 述べ ている 。本論 文は，以下 のよ うに構 成さ れる。
2章 で は ，ASICの設 計 の 支 援 が必 要 に な っ て きた 背 景 に っ いて 述 べ る 。 最初 に ，ASICが 持 つ 特 徴 から ， 設 計 支 援の 必 要 性 が 大き い こ と を 述べ る 。ASICを 支 え る 基礎 技 術 と して重 要な VLSIテ ク ノ 口 ジ一 ， 回 路 構 成方 式 ， 設 計 階層 の 説 明 を 行 った 後 ， 現 在 まで に 歩 ん できたVLSI 設 計 の 歴 史 を ， 本論 文 で 扱 っ た2っ の 研 究 と関 連 さ せ な がら 論 じ る 。 現在ASIC設計 が 直 面 し てい る問題 点を 検討し た後， これか らの設 計支援システムがどうあるべきかを描き出す。最後に，
本論 文で扱 う設 計の範 囲を明 確にす る。
3章 で は ， シ ステ ム レ ベ ル での 事 例 研 究 を ，Vソ ー ト エ ンジ ンを設 計対 象に選 んで行 った。V ソー トエン ジン は可変 長文字 列をソ ート可 能な 専用ハ ードウ エアで あり ，最初 にその 概略を説明 す る 。 シス テ ム レベル での設 計の 際に用 いた， 主な設 計技法 にっ いて説 明する 。Vソート エンジ ンに 関して ，既 に得ら れてい た動作 レベル での 設計結 果にっ いて述 べる 。この 後，順 を追って詳 細な 設計過 程に っいて 説明す る。Vソー トエン ジンの 設計 は，動 作レベルの設計結果を出発点に，
3っ の段 階 を 経 て行 われて いる。 すなわ ち， 機能レ ペルの 初期設 計，シ ステ ムレベ ルでの 改良，
機 能 レ ベル の 最 終設計 という3段 階を経 てい る。最 初に， 初期設 計とし て行 われた 機能レ ベルの スケ ジュー リン グにっ いて述 べる。 この段 階では，十分な速度を得ることはできなかった。次に，
シス テムレ ベル で加え られた 改良点 にっい て説 明する 。その 際，メ モリ 分割， キャッ シュ，フオ ワ ー デ ィン グ と 呼 ば れる3っ の 設 計技 法を 用いた 。再 度機能 設計を 行うこ とによ り，Vソー トエ ンジ ンの機 能設 計は完 了した 。完成 した機 能レ ベルで の設計 結果は ，デ 一夕パ スの構 成とその土 での 操作と に分 けて記 述され ている 。最後 に， この事 例研究 を通じ て得 られた 、シス テムレベル の 設 計 支援 に 求 められ る機能 にっ いて述 べる。 ここで 行った 設計 では，3っ の設計 技法を 組み合 せる ことに より 始めて ，十分 な速度 を得る こと ができ た。複 数技法 の援 用を支 援でき ることは，
設 計 支 援 シ ス テ ム に お け る 重 要 な 機 能 の1っ で あ る こ と が 明 ら か に な っ た 。 4章 で は ， 多 相方式 のディ ジタル 回路 を設計 対象と した設 計手 法にっ いて述 べる。 最初に ，多 相 方 式 が持 つ 高 速 性 とい う 特 徴 か ら，ASIC設計 におい て多 相方式 を設計 対象と した 設計支 援が 望ま れるこ とを 述べる 。次に ，従来 行われ てき た関連 する研 究にっ いて ，ここ で提案 される設計 手法 との比 較を 行いな がら述 べる。 多相方 式に っいて 詳しく 説明し た後 ，多相 方式を 対象とした 設計 手法の 提案 を行う 。この 設計手 法は， 単相 の回路 を設計 入カと し， それを 多相の 回路に自動
443
変換 するも のであ る。 変換と 同時に 高速化 設計が 施さ れる。 次に， 設計対 象となる多相方式の回 路に 対し， 数学的 に厳 密なモ デル化 を行う 。提案 され た手法 を実現 するに は，多栢最適化問題を 角罕 く必要 がある 。回 路モデ ルを用いて多相最適化問題を厳密に述べる。この問題を解くための最 適化 アルゴ リズム を考 案し， その導 出過程 を詳細 に説 明する 。この アルゴ リズムは発児的手法を 用い ており ，多項 式時 間で終 了する ことが できる 。用 いた発 見的手 法の基 本的な考え方にっいて も説 明を加 える。 最後 に，簡 単な設計例にアルゴリズムを適用し，アルゴリズムの評価を試みた。
こ こで 述べた 最適 化アル ゴリズ ムで設 計され た回 路は， 従来手 法によ る設 計結果 と比べ て，1割 程度 の高速 化がな され ていた 。この 設計例 により ，ア ルゴリ ズムの 有効性 を示すことができた。
最後に5章 では， 本研 究で得 られた 結果の まと めを行 うとと もに， 残され た研 究課題 にっい て 述べ る。
本研 究 で は ，ASICを 設計 対象 とした システ ムレベ ル設計 の支 援シス テムを 構築す る際 ，複数 設計 技法の 援用を 支援 する機 能が必 要不可 欠であ るこ とを明 かにし た。ま た，多相方式のデ一夕 パス の設計 を行う 際に 必要と なる設 計手法 を提案 し， その手 法を実 現する 最適化アルゴリズムを 開 発 した 。 設 計 例 によ り ， ア ル ゴ リズ ム がASIC設 計 に 際し て 有 効 で ある ことを 明かに した。
学位論文審査の要旨 主査
副査 副査 副査
教授 教授 教授 教授
田中 青木 栃内 三好
譲 由 直 香 次 克 彦
シ ス テ ム レ ベル で の専 用VLSIの 設計 は，現 在，設 計者の 経験と 知識 に大き く依存 してい る。
ま た， 専 用VLSIの 機 能 設 計でfま ， 高 速な 回 路を 短期間 で設計 できる よう に，よ り高品 質な自 動設 計手法 の開発 が望ま れてい る。
本 論 文 は ， 高速 な 専 用VLSIを 設 計 する た め の 手 法を ， シ ス テ ムレ ペルお よび機 能レベ ルで 研究 したも のであ り，動 作速度 を決 定する 因子が システ ム・ レベル の設計ではメモリ・アクセス
システ ムレベ ル設計 に関 しては その研 究が最 近開 始され たばか りであ り，い くっ かの設計技法 が 個弓iJに知ら れてい るの みであ る。本 論文で 著者 は，設 計事例としてVソ―トエンジンと呼ばれ る 可変 長文字 列集合 のソー ティ ング・ ハ―ドウェアを取上げ，その高速動作に関してメモリ分割，
キ ャ ッ シ ュ・ メモ りの採 用，フ エワー ディン グの3っの 高速 化手法 を提案 し，そ れら の適用 を試 み てい る。こ の事例 研究に より ，シス テムレ ベル設 計にお ける 動作速 度を決 定する 主要因子がメ モ りの アクセ ス動作 間の依 存性 である ことを明らかにしている。さらに，メモIJ分割，キャッシュ
・ メ モ り の採 用， フォワ ーディ ングの3っ の高速 化手法 がす べてメ モりの アクセ ス動 作間の 依存 性 を表 すグラ フの変 換操作 とし て定式 化でき ること を明ら かに してい る。そ こで著 者は，メモリ
・ アク セスの 依存関 係のみ を考 慮した 場合の 最適設 計問題 をシ グナル ・フ口 ーグラ フを用いて定 式 化 し ， 準 最 適 設 計 を 与 え る 変 換 操 作 を 求 め る 発 見 的 ア ル ゴ リ ズ ム を 提 案 し て い る 。 機能設 計に関 してfま，80年代 から多 くの研 究がな され てきているが，高速性に優れた多相回路 の 設計 に関し ては，1980年代 後半に なって 研究 が開始 された ばかり で， パイプ ライン処理を設計 対 象と したス テージ 分割法 と， チェイ ニング とマル チサイ クル を考慮 に入れ たスケ ジューリング
・ ア ル ゴ リズ ムと ，制御 信号生 成部を 対象と した アルゴ ルズム との3種の 手法が 提案 されて いる の みで あった 。ステ ージ分 割法 はルー プを含 む回路 の設計 には 適用で きない 。スケ ジュールング 法 はチ ェイニ ングと マルチ サイ クルを 同時に 適用す ること がで きない という 制限を 持つ。制御信 号 生成 部を対 象とし たアル ゴル ズムで は基本素子はゲートであり，マクロ．機能素子を基本要素と し て用 いる回 路の設 計には 適さ ない。
これに 対し本 論文は ，マ ク口機 能素子 を基本 要素 として 用い， ループ も許し た多 相回路におい て ，チ ェイニ ングと マルチ サイ クルの 同時適 用も許 した際 の準 最適設 計を求 めるア ルゴリズムを 提 案し ている 。著者 は多相 方式 回路の 設計入 カとし て単相 方式 で設計 された 回路を 用いることを 提 案し ている 。この 単相方 式回 路は最 適設計 されて いる必 要は ない。 著者は 単相方 式回路と多相 方 式 回 路 との 間の 等動作 関係の 概念を 新たに 導入 し，こ れを2っの 条件で 表現し て定 式化し てい る 。さ らにこ の定式 化に基 づい て，回 路の経 路に沿 ったポ テン シャル 関数を 新たに 定義すること に よっ て，ラ ッチが ある位 置に 挿入さ れる際のラッチのポテンシャルを定義した。このポテンシャ ル を用 いるこ とによ って， 等動 作条件 と回路 の実現 条件と を関 連付け ている 。この ような定式化 に よっ て，実 現可能 な準最 適多 相回路 を求め るアル ゴリズ ムが ，最短 経路問 題を解 くためのアル ゴ リ ズ ム で あ るBellman‑Fordア ルゴ リズム を拡張 するこ とによ り得 られる ことを 示して いる 。 こ の ア ル ゴリ ズム を実例 に適用 した結 果，近 年提 案され た準最 適設計 手法 に比し てもさ らに1割 程 度高 速な回 路が実 現でき たこ とが報 告され ている 。
445
こ れを要するに，著者は，高速な専用VLSIを設計する際に重要となる設計支援に関して，
シス テムレベルおよび機能レベルにおける設計手法の提案を行い，専用VLSI設計に関する有 益 な 知 見 を 得 て お り ， 計 算 機 工 学 の 進 歩 に 貢 献 す る と こ ろ 大 な る も の が あ る 。 よ っ て 著 者 は 博 士 （ 工 学 ） の 学 位 を 授 与 さ れ る 資 格 あ る も の と 認 め る 。
