博士論文審査結果報告書

1

早稲田大学大学院情報生産システム研究科

博士論文審査結果報告書

論 文 題 目

Ge ner ati on an d Opt imi za tio n of Da ta Pa th in Hi gh-L e ve l S yn thes is

申 請 者 GE 、 Liangwei

情報生産システム工学専攻 最適化技術研究

2009 年 2 月

2

半 導 体 技 術 の 進 歩 に 伴 い 、L SI の 大 規 模 化 ・ 高 速 化 が 進 行 し 、 そ の 設 計 が ま す ま す 複 雑 化 し て い る 。 更 に 、L SI を 組 込 ん だ 製 品 の ラ イ フ サ イ ク ル 短 縮 に 伴 い 、L SI の 設 計 期 間 の 短 縮 と 設 計 コ ス ト の 低 減 が 求 め ら れ て い る 。 こ れ ら の 解 決 策 と し て 近 年 有 力 視 さ れ て い る の が 高 位 合 成 、 す な わ ち 、C 言 語 等 の 高 級 言 語 で 記 述 さ れ た 仕 様 か ら L SI の 回 路 を 自 動 生 成 す る 手 法 で あ る 。こ の 手 法 を 用 い た 設 計 で は 、L SI の 動 作 を 表 わ す 記 述 の み を 作 成 す れ ば よ い こ と か ら 、 設 計 者 が 創 造 力 を 発 揮 し や す く な る 他 、 設 計 期 間 、 設 計 コ ス ト の 大 幅 な 低 減 が 可 能 と な る 等 、 多 大 な メ リ ッ ト が あ る 。 し か し 、 そ の 一 方 で 現 在 の 技 術 で は 、 高 位 合 成 シ ス テ ム に よ っ て 自 動 設 計 さ れ た 回 路 の 品 質 は 、 熟 練 設 計 者 が 十 分 時 間 を か け て 設 計 し た 回 路 と 比 較 す る と 、 ど う し て も 劣 る こ と が 避 け ら れ な い 。 ま た 、 ナ ノ ス ケ ー ル 時 代 の L SI 設 計 に お い て は 、 設 計 の 上 流 工 程 で あ る 高 位 合 成 の 時 点 で 、 設 計 下 流 工 程 の 種 々 の 条 件 ま で 考 慮 す る こ と が 求 め ら れ て い る 。 一 方 、 フ ロ ア プ ラ ン と よ ば れ る 技 術 が 、 近 年 、 急 速 に 進 展 し 、 高 位 合 成 で も 配 線 長 な ど 設 計 下 流 工 程 に 関 す る 概 略 の 情 報 が 利 用 可 能 と な り つ つ あ る 。 し か し 高 位 合 成 の 問 題 の 多 く は NP 困 難 で あ る こ と が 知 ら れ て お り 、 従 来 の グ リ ー デ ィ ア ル ゴ リ ズ ム に 基 づ く 単 純 な 手 法 で は 、 こ れ ら の 条 件 を 考 慮 す る こ と は 難 し い の が 現 状 で あ る 。 そ の た め 、 高 位 合 成 シ ス テ ム は 一 部 の 先 進 企 業 で は 社 内 的 に は 広 く 使 用 さ れ 、 自 動 設 計 ツ ー ル と し て 商 品 化 も さ れ て い る が 、 一 般 の 企 業 に 広 く 普 及 す る ま で に は 至 っ て い な い 。 し か し な が ら 、高 位 合 成 は 将 来 の L SI 設 計 に お け る 中 核 シ ス テ ム と な る こ と は 確 実 で あ り 、 高 位 合 成 で 高 品 質 な 回 路 を 自 動 設 計 す る た め の 新 ら た な 技 術 開 発 が 望 ま れ て い る 。

一 般 に 、 高 位 合 成 の 処 理 は ① 翻 訳 ：C 言 語 な ど 高 級 言 語 に よ る 仕 様 記 述 を 内 部 デ ー タ 構 造 に 変 換 す る 処 理 、 ② ス ケ ジ ュ ー リ ン グ ： 各 演 算 の 実 行 の タ イ ミ ン グ を 決 定 す る 処 理 、 ③ デ ー タ パ ス 合 成 ： デ ー タ を 処 理 す る た め の バ ス を 生 成 す る 処 理 、 ④ 制 御 回 路 合 成 ： 演 算 回 路 の 制 御 信 号 を 発 生 す る 回 路 を 生 成 す る 処 理 、 お よ び ⑤ 演 算 モ ジ ュ ー ル 合 成 ： 回 路 で 使 用 す る 各 種 演 算 モ ジ ュ ー ル を 生 成 す る 処 理 、 か ら な る 。

本 論 文 で は こ れ ら の 処 理 の う ち 、 ② の ス ケ ジ ュ ー リ ン グ に 関 し て 、 新 し い 解 空 間 探 索 法 に 基 づ く ス ケ ジ ュ ー リ ン グ 手 法 お よ び ス ケ ジ ュ ー リ ン グ 結 果 の 高 品 質 化 を 図 る た め の 手 法 、 ⑤ の 演 算 モ ジ ュ ー ル 合 成 に 関 し て 、 特 定 用 途 の 各 種 関 数 に 対 す る 浮 動 小 数 点 演 算 回 路 の 自 動 合 成 手 法 を 提 案 し て い る 。

以 下 に 、 本 論 文 の 各 章 毎 の 概 要 を 述 べ 、 評 価 を 加 え る こ と と す る 。

第 一 章 は 序 論 で あ り 、 高 位 合 成 に 関 す る 背 景 と 高 位 合 成 で 鍵 と な る 技 術 を 紹 介 し 、 本 研 究 の 目 的 、 意 義 を 明 ら か に し て い る 。

第 二 章 で は 高 位 合 成 の 重 要 課 題 の 一 つ で あ る ス ケ ジ ュ ー リ ン グ 問 題 に 関 し

3

て 、 新 し い 解 空 間 探 索 法 に 基 づ く ス ケ ジ ュ ー リ ン グ 手 法 を 提 案 し て い る 。 本 章 で 提 案 す る 手 法 は 通 常 の 、 解 空 間 全 体 の 中 か ら 解 を 直 接 探 索 す る 方 法 と 異 な り 、 ま ず 、 ク ラ ス P の 部 分 解 空 間 、 す な わ ち 、 そ の 空 間 内 の 最 適 解 を 多 項 式 時 間 で 発 見 で き る よ う な 部 分 解 空 間 を 抽 出 し 、 次 の ス テ ッ プ で そ の 部 分 解 空 間 内 の 最 適 解 を 計 算 す る 方 法 を 採 用 し て い る 。ス ケ ジ ュ ー リ ン グ 問 題 で は 、 こ の 部 分 解 空 間 は 、実 行 す べ き 演 算 の 集 合 お よ び そ れ ら を 実 行 す る 時 刻(コ ン ト ロ ー ル ス テ ッ プ)の 集 合 を 節 点 で 表 現 し 、割 当 て 可 能 な 両 者 の 組 み 合 わ せ を 枝 で 表 現 し た 二 部 グ ラ フ に よ っ て 定 義 す る こ と が で き る 。 そ こ で 、 各 種 条 件 を 各 枝 の 重 み と し て 定 義 し 、 最 大 フ ロ ー ア ル ゴ リ ズ ム に 基 づ い て 最 適 な マ ッ チ ン グ を 計 算 す る こ と で 、 設 計 下 流 工 程 で の 種 々 の 条 件 等 を 考 慮 す る こ と を 可 能 と し て い る 。 本 論 文 で は こ れ ら の 条 件 の 例 と し て 、 時 刻 毎 の 電 流 の 変 化 量 を 抑 え る よ う 枝 の 重 み を 設 定 し 、 評 価 を 行 っ て い る 。 こ れ は 従 来 、 設 計 下 流 工 程 で 、 デ カ ッ プ リ ン グ 容 量 の 挿 入 、 配 線 幅 の 調 整 な ど で 対 処 さ れ て き た 問 題 で あ る 。 実 験 結 果 に よ る と 、 提 案 手 法 は 、 多 量 の 電 流 を 使 用 す る 乗 算 器 の 時 刻 毎 の 使 用 頻 度 を 均 一 化 し 、 従 来 手 法 に 比 べ 電 流 の 変 化 量 を 最 大 ６ ５% 削 減 し て い る 。 本 論 文 で は 評 価 関 数 と し て 電 流 量 の 均 一 化 を 取 り 上 げ た が 、 本 手 法 自 体 は 、 枝 の 重 み と し て 表 現 可 能 な 任 意 の 評 価 関 数 を 扱 う こ と が で き る 。 す な わ ち 、 本 手 法 は 実 際 の 設 計 に お け る 種 々 の 条 件 を 扱 か う こ と を 可 能 と し て お り 、 高 位 合 成 の 実 用 性 向 上 に 貢 献 す る も の と 期 待 さ れ る 。

第 三 章 で は 上 記 手 法 の 解 の 品 質 向 上 を 行 う 手 法 を 提 案 し て い る 。 ス ケ ジ ュ ー リ ン グ 問 題 は NP 困 難 で あ り 種 々 の 近 似 解 法 が 提 案 さ れ て い る が 、 い ず れ も 得 ら れ る 解 の 品 質 は 十 分 で は な か っ た 。 第 二 章 で 提 案 し た 手 法 で も 、 基 本 的 に は 、 一 つ の 部 分 解 空 間 の み を 抽 出 し て 、 そ の 中 で の 最 適 解 を 求 め て い る 。 そ の た め 、 本 章 で は こ の 部 分 解 空 間 を 逐 次 更 新 し て い く こ と で 解 の 改 良 を 行 う こ と を 考 え る. NP 困 難 な 問 題 に 対 し て 高 品 質 の 解 を 求 め る 手 法 と し て 、SA( S i m u l a t e d A n n e a l i n g )、GA( G e n e t i c A l g o r i t h m )、T S( T a b u S e a r c h )等 が あ る 。 し か し 、 こ こ で は 解 そ の も の で は な く 、 部 分 解 空 間 を 逐 次 更 新 す る こ と で 解 の 改 良 を 行 う こ と を 考 え 、 Ra ndo m Wa lk を 応 用 し た 手 法 を 提 案 し て い る 。 す な わ ち 、 一 つ の 部 分 解 空 間 か ら 次 の 部 分 解 空 間 へ と 次 々 と ラ ン ダ ム に 移 動 し 、 最 終 的 に 、 通 過 し た 各 部 分 解 空 間 の 最 適 解 の 内 で 最 良 な も の を 解 と し て 採 用 す る 。 た だ し 、 そ の 際 、 移 動 を 完 全 に ラ ン ダ ム に 行 う の は 効 率 が 悪 い た め 、 各 部 分 解 空 間 を 表 現 す る 二 部 グ ラ フ の 構 造 か ら 遷 移 確 率 を 計 算 し 、 そ の 確 率 に 基 づ い て 移 動 を 行 っ て い る 。 実 験 結 果 に よ る と 、 小 規 模 な 例 題 で は 、I L P で 計 算 し た 最 適 解 と 一 致 し て お り 、 大 規 模 な 例 題 で も 、 第 二 章 の ス ケ ジ ュ ー リ ン グ 手 法 と く ら べ 、 回 路 の 速 度 性 能 を 約 1 0 %改 善 す る 結 果 が 得 ら れ て い る 。 こ れ ら の 結 果 か ら 、 本 手 法 で 得 ら れ る 解 の 品 質 は 最 適 解 に 近 い こ と が 予 想 さ れ 、 高 位 合 成 で 生 成 さ れ る 解 の 品 質 向 上 に 貢 献 で き る も の と 評 価 で き る 。

4

第 四 章 で は 高 位 合 成 の 主 要 な ス テ ッ プ で あ る 演 算 器 の 自 動 合 成 の う ち 、 仕 様 記 述 中 に 現 れ る 1 /x、 √x、 l o g (x)、 s i n (x)な ど の 浮 動 小 数 点 関 数 の 回 路 を 自 動 生 成 す る 手 法 を 提 案 し て い る 。 現 在 、 最 も 広 く 使 わ れ て い る 浮 動 小 数 点 関 数 の 実 現 法 は 変 数 値 の 取 り 得 る 範 囲(変 域)を 小 区 間 に 分 割 し 、 そ れ ぞ れ の 区 間 内 の 関 数 を 多 項 式 で 近 似 す る 方 法 で あ る 。 し か し 、既 存 の 手 法 で は 分 割 数 を 大 き く す る と 回 路 が 複 雑 と な り 、 回 路 の 速 度 低 下 を ま ね く こ と か ら 、 区 間 数 は 1 0 程 度 に 留 ま り 、 精 度 を 保 ち つ つ 変 域 を 広 く と る こ と は 困 難 で あ っ た 。 本 論 文 で は 、 浮 動 小 数 点 の 表 現 形 式 に 着 目 し 、a l ig ned pa rtition 法 と よ ば れ る 区 間 分 割 手 法 を 提 案 し て い る 。 こ れ に よ り 、 回 路 規 模 を 大 き く 増 加 さ せ る こ と な く 、 区 間 の 分 割 数 を 2 00 0 程 度 ま で 増 加 さ せ る こ と を 可 能 と し 、 広 い 変 域 に 対 し て 、 関 数 値 の 高 精 度 な 計 算 を 実 現 し て い る 。 ま た 、 本 論 文 で は 用 途 に よ っ て 使 い 分 け る た め 、 速 度 、 精 度 お よ び 回 路 規 模 の 異 な る 二 つ の パ イ プ ラ イ ン ア ー キ テ ク チ ャ を 提 案 し て い る 。 実 験 結 果 で は 人 手 設 計 に く ら べ 、 は る か に 広 い 変 域 に 対 し て 、 関 数 値 の 計 算 誤 差 を 最 大 1 /20 00 に ま で 削 減 で き る こ と が 示 さ れ て い る 。 本 論 文 で 提 案 し た 自 動 生 成 手 法 は 従 来 人 手 で 行 わ れ て い た 演 算 回 路 の 設 計 に と っ て 代 わ る も の で あ り 、 高 位 合 成 を 用 い た 設 計 効 率 化 に 大 き く 貢 献 す る も の で あ る と 評 価 で き る 。

第 五 章 は 結 論 で あ り 、本 研 究 で 行 っ た 、「 最 大 フ ロ ー ア ル ゴ リ ズ ム に 基 づ く ス ケ ジ ュ ー リ ン グ 手 法 」、「Ra ndom Wa lk に よ る ス ケ ジ ュ ー リ ン グ の 最 適 化 手 法 」「 特 定 用 途 の 浮 動 小 数 点 関 数 演 算 回 路 の 自 動 生 成 手 法 」に 関 す る 成 果 を 総 括 し 、最 後 に 、今 後 の 高 位 合 成 手 法の 実 用 化 に 向 け た 課 題 に つ い て 述 べ て い る。

以 上 が 本 論 文 の 概 要 で あ る が 、 要 約 す れ ば 、 本 論 文 は 高 位 合 成 シ ス テ ム に 関 す る 技 術 開 発 を 目 指 し 、 種 々 の 制 約 を 考 慮 し た ス ケ ジ ュ ー リ ン グ 、 ス ケ ジ ュ ー リ ン グ の 高 品 質 化 、 浮 動 小 数 点 演 算 回 路 の 自 動 構 成 と い う 重 要 課 題 に 対 し て 、 多 く の 独 創 的 な 設 計 自 動 化 手 法 を 提 案 し 、 計 算 機 実 験 で そ の 有 効 性 を 実 証 す る こ と で 、 高 位 合 成 シ ス テ ム 高 度 化 へ の 道 を 開 い た も の で あ る 。 こ れ ら の 大 半 は 企 業 に お け る 最 先 端 の 高 位 合 成 シ ス テ ム 開 発 者 と 情 報 交 換 を し な が ら 研 究 し た 成 果 で あ り 、今 後 ま す ま す 重 要 と な る 大 規 模 L SI 向 け の 設 計 自 動 化 技 術 の 発 展 に 大 き く 貢 献 し た と い う こ と が で き る 。 よ っ て 本 論 文 は 、 博 士(工 学)学 位 論 文 と し て 価 値 の あ る も の と 認 め る 。

200 9 年 1 月 1 6 日 審 査 員

主 査 早稲田大学・教授 博士(工学)(大阪大学) 吉村 猛 早稲田大学・教授 工学博士(東北大学) 渡邊 孝博 早稲田大学・教授 工学博士(京都大学) 木村 晋二